DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Find Minimum in Rotated Sorted Array

Problem statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times.
For example, the array nums = [0, 1, 2, 4, 5, 6, 7] might become:

[4, 5, 6, 7, 0, 1, 2] if it was rotated 4 times.
[0, 1, 2, 4, 5, 6, 7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results
in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Problem statement taken from: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/.

Example 1:

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1, 2, 3, 4, 5] rotated 3 times.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 5, 6, 7] and it was rotated 4 times.
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: nums = [11, 13, 15, 17]
Output: 11
Explanation: The original array was [11, 13, 15, 17] and it was rotated 4 times.
Enter fullscreen mode Exit fullscreen mode

Constraints:

- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All the integers of nums are unique
- nums is sorted and rotated between 1 and n times
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute force approach

The naive approach is to do a linear search which takes O(N) time. We need to find the ith index where a smaller number appears after (i - 1)th index.

Binary search

Since the array is rotated but sorted, we can modify our binary search implementation. The rotated array has two segments that are sorted. The index where the sorting is disturbed occurs at the smallest element in the array.

Let's check the algorithm:

- set low = 0
      high = nums.size() - 1

- loop while low < high
  - set mid = low + (high - low) / 2

  - if nums[low] <= nums[mid] && nums[high] >= nums[mid]
    - set high = mid - 1
  - else if nums[low] <= nums[mid] && nums[high] <= nums[mid]
    - set low = mid + 1
  - else if nums[mid] <= nums[low]
    - set high = mid

- return nums[low]
Enter fullscreen mode Exit fullscreen mode

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;

        while(low < high) {
            int mid = low + (high - low) / 2;

            if(nums[low] <= nums[mid] && nums[high] >= nums[mid])
                high = mid - 1;
            else if(nums[low] <= nums[mid] && nums[high] <= nums[mid])
                low = mid + 1;
            else if(nums[mid] <= nums[low])
                high = mid;
        }

        return nums[low];
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func findMin(nums []int) int {
    low, mid := 0, 0
    high := len(nums) - 1

    for low < high {
        mid = low + (high - low) / 2

        if nums[low] <= nums[mid] && nums[high] >= nums[mid] {
            high = mid - 1
        } else if nums[low] <= nums[mid] && nums[high] <= nums[mid] {
            low = mid + 1
        } else if nums[mid] <= nums[low] {
            high = mid
        }
    }

    return nums[low];
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var findMin = function(nums) {
    let low = 0;
    let high = nums.length - 1;

    while(low < high) {
        let mid = low + Math.floor((high - low) / 2);

        if(nums[low] <= nums[mid] && nums[high] >= nums[mid])
            high = mid - 1;
        else if(nums[low] <= nums[mid] && nums[high] <= nums[mid])
            low = mid + 1;
        else if(nums[mid] <= nums[low])
            high = mid;
    }

    return nums[low];
};
Enter fullscreen mode Exit fullscreen mode

Let's dry run our algorithm.

Input: nums = [4, 5, 6, 7, 0, 1, 2]

Step 1: low = 0
        high = nums.size() - 1
             = 7 - 1
             = 6

Step 2: loop while low < high
          0 < 6
          true

          mid = low + (high - low) / 2
              = 0 + (6 - 0) / 2
              = 3

          if nums[low] <= nums[mid] && nums[high] >= nums[mid]
             nums[0] <= nums[3] && nums[6] >= nums[3]
             4 <= 7 && 2 >= 7
             false

          else if nums[low] <= nums[mid] && nums[high] >= nums[mid]
                  nums[0] <= nums[3] && nums[6] <= nums[3]
                  4 <= 7 && 2 <= 7
                  true

                  low = mid + 1
                      = 3 + 1
                      = 4

Step 3: loop while low < high
          4 < 6
          true

          mid = low + (high - low) / 2
              = 4 + (6 - 4) / 2
              = 4 + 1
              = 5

          if nums[low] <= nums[mid] && nums[high] >= nums[mid]
             nums[4] <= nums[5] && nums[6] >= nums[5]
             0 <= 1 && 2 >= 1
             true

             high = mid - 1
                  = 5 - 1
                  = 4

Step 4: loop while low < high
          4 < 4
          false

Step 5: return nums[low]
               nums[4]
               0

We return the answer as 0.
Enter fullscreen mode Exit fullscreen mode

Top comments (0)