153. Find Minimum in Rotated Sorted Array

In this tutorial we will solve 153. Find Minimum in Rotated Sorted Array from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 153. Find Minimum in Rotated Sorted Array

Problem statement

In this problem statement we are asked to find the minimum value in a sorted array nums of length n. The array is sorted in ascending order. We are also told that the input array can be rotated 1 to n times.

For example if the input array is [1,2,3,4,5] and we rotate 1 time then the new array will be [5,1,2,3,4].

Similarly, if the input array is rotated 3 times then the new array will be [3,4,5,1,2].

Example from leetcode.

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

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.

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. 

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.

Approach

To solve this problem we will use Binary Search. We will start by pointing the start pointer to the 0th index and the end pointer to the last index of the array. Then we will loop as long as the start is less than or equal to the end. In each iteration we will find the middle index mid and check if the middle element is less than the end element. If it is then we will set the end to the mid index. Else, we will move the start index to mid + 1. After the loop ends we will have the minimum value at index start - 1.

Let us look at the first input [3,4,5,1,2].

n = 5

start = 0
end = 4
mid = floor((start + end) / 2)
    = floor((0+4)/2)
    = 2

index =  0  1  2  3  4
nums  = [3, 4, 5, 1, 2]
         ^     ^     ^
         s     m     e

is start <= end ? YES
is nums[m] < nums[e] ?
i.e., 5 < 2 ? NO
so, we move start


start = mid + 1
      = 2 + 1
      = 3
end = 4
mid = floor((start + end) / 2)
    = floor((3+4)/2)
    = 3

index =  0  1  2  3  4
nums  = [3, 4, 5, 1, 2]
                  ^  ^
                  s  e
                  m

is start <= end ? YES
is nums[m] < nums[e] ?
i.e., 1 < 2 ? YES
so, we move end


start = 3
end = mid
    = 3
mid = floor((start + end) / 2)
    = floor((3+3)/2)
    = 3

index =  0  1  2  3  4
nums  = [3, 4, 5, 1, 2]
                  ^
                  s
                  e
                  m

is start <= end ? YES
is nums[m] < nums[e] ?
i.e., 1 < 1 ? NO
so, we move start


start = mid + 1
      = 3 + 1
      = 4
end = 3

now start is greater than end so we stop here.

minimum value is at index = start - 1
= 4 - 1
= 3

i.e., nums[3] = 1

Code

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
  let start = 0;
  let end = nums.length - 1;
  while (start <= end) {
    const mid = Math.floor((start+end)/2);
    if (nums[mid] < nums[end]) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }
  return nums[start-1];
};

Complexity

Time complexity: O(n)

Binary Search is used here so the time complexity is O(logn).

Space complexity: O(n)

We are only using constant space so space complexity will be O(1).