Design Gurus Logo
Solution: Find Minimum in Rotated Sorted Array
Go Back

Problem Statement

You have an array of length n, which was initially sorted in ascending order. This array was then rotated x times. It is given that 1 <= x <= n. For example, if you rotate [1, 2, 3, 4] array 3 times, resultant array is [2, 3, 4, 1].

Your task is to find the minimum element from this array. Note that the array contains unique elements.

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

Example 1:

  • Input: [8, 1, 3, 4, 5]
  • Expected Output: 1
  • Justification: The smallest number in the array is 1.

Example 2:

  • Input: [4, 5, 7, 8, 0, 2, 3]
  • Expected Output: 0
  • Justification: The smallest number in the array is 0.

Example 3:

  • Input: [7, 9, 12, 3, 4, 5]
  • Expected Output: 3
  • Justification: In this rotated array, the smallest number present is 3.

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.

Solution

To determine the minimum element in a rotated sorted array, we'll leverage the binary search method.

In a standard sorted array, the elements increase (or remain the same) from left to right. But in our rotated sorted array, at some point, there will be a sudden drop, which indicates the start of the original sorted sequence and, hence, the minimum element. This drop will be our guide during the search. With binary search, we'll repeatedly halve our search range until we pinpoint the location of this sudden drop or the smallest element.

  1. Initialization: Start with two pointers, left and right, set at the beginning and the end of the array, respectively.

  2. Binary Search Process:

    • Calculate the middle index, mid.
    • If the element at mid is greater than the element at right, this indicates that the minimum element is somewhere to the right of mid. Hence, update left to mid + 1.
    • Otherwise, the minimum element is to the left, so update right to mid.

  3. Termination: The loop will eventually lead left to point to the minimum element. This happens when left equals right.

  4. Edge Case Handling: If the array isn't rotated at all, the smallest element will be the first. Our binary search process accounts for this scenario.

Algorithm Walkthrough

Consider the array [4, 5, 7, 8, 0, 2, 3]:

  • Start with left = 0 and right = 6.
  • Calculate mid = (0 + 6) / 2 = 3. The array element at index 3 is 8.
  • Since 8 > 3 (element at right), update left to mid + 1 = 4.
  • Now, left = 4 and right = 6. Calculate mid = (4 + 6) / 2 = 5.
  • Element at index 5 is 2. Since 2 < 3, update right to mid = 5.
  • Now, left = 4 and right = 5. Calculate mid = (4 + 5) / 2 = 4.
  • Element at index 4 is 0. Since 0 < 2, update right to mid = 4.
  • left is now equal to right, both pointing at index 4, where the minimum element 0 is present.

Code

Python3
Python3

Complexity Analysis

Time Complexity: O(log n) because we are using a binary search approach, which reduces the problem size by half in each step.

Space Complexity: O(1) as we are using a constant amount of space regardless of the input size.