Find Minimum in Rotated Sorted Array | Leetcode 153 | Optimal Binary Search

The “Find Minimum in Rotated Sorted Array” problem is a classic question that tests your understanding of binary search and array manipulation. In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

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.

Here’s the [Problem Link] to begin with.

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.

Brute Force Solution (Linear Scan)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Scan Each Element:
   Go through the array from start to end.
2. Track the Minimum:
   Keep updating a variable with the smallest value found so far.
3. Why does this work?
   We check every element, so we’re sure to find the minimum.

This approach is easy to understand but not efficient for large arrays.

Code Implementation

class Solution:
    def findMin(self, nums: List[int]) -> int:
        minimum = float("inf")                # Initialize minimum as infinity
        for i in range(len(nums)):            # Iterate through the array
            minimum = min(minimum, nums[i])   # Update minimum if needed
        return minimum                        # Return the smallest element

Code Explanation

• We initialize minimum as infinity.
• We loop through each element in the array.
• If we find a smaller value, we update minimum.
• After checking all elements, we return minimum.

Dry Run

Input:
nums = [1]

• minimum = inf
• Compare 4 → minimum = 4
• Compare 5 → minimum = 4
• Compare 6 → minimum = 4
• Compare 7 → minimum = 4
• Compare 0 → minimum = 0 (updated)
• Compare 1 → minimum = 0
• Compare 2 → minimum = 0

Final Output:
0

Time and Space Complexity

• Time Complexity: O(n)
  We may have to check every element.
• Space Complexity: O(1)
  Only a variable for the minimum.

Conclusion

The brute force approach is simple and works for small arrays, but it’s too slow for large inputs.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search:
   Use two pointers (low and high) to perform binary search.
2. Check Sorted Halves:
   • If the left half is sorted, the minimum is either at low or in the right half.
   • If the right half is sorted, the minimum is either at mid or in the left half.
3. Why does this work?
   In a rotated sorted array, the minimum element is the only element where the previous element is greater than it. Binary search helps us find this quickly.

Code Implementation

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        low = 0
        high = n - 1
        minimum = float("inf")

        while low <= high:
            mid = (low + high) // 2            # Find the middle index

            # If left half is sorted
            if nums[low] <= nums[mid]:
                minimum = min(minimum, nums[low])  # Update minimum
                low = mid + 1                      # Search in the right half
            else:                                  # Right half is sorted
                minimum = min(minimum, nums[mid])  # Update minimum
                high = mid - 1                     # Search in the left half

        return minimum                             # Return the smallest element

Code Explanation

• We use binary search with pointers low and high.
• If the left half is sorted, the minimum must be at low or in the right half.
• If the right half is sorted, the minimum must be at mid or in the left half.
• We keep updating minimum and narrowing our search window.
• When the search is done, we return minimum.

Dry Run

Input:
nums = [1]

• low = 0, high = 6
• mid = 3 (nums = 7)
• Left half is sorted (nums=4 <= nums=7)
• minimum = min(inf, 4) = 4
• Move low to mid + 1 = 4
• low = 4, high = 6
• mid = 5 (nums = 1)
• Left half is sorted (nums=0 <= nums=1)
• minimum = min(4, 0) = 0
• Move low to mid + 1 = 6
• low = 6, high = 6
• mid = 6 (nums = 2)
• Left half is sorted (nums=2 <= nums=2)
• minimum = min(0, 2) = 0
• Move low to mid + 1 = 7
• low > high, exit loop.

Final Output:
0

Time and Space Complexity

• Time Complexity: O(log n)
  Binary search divides the array each time.
• Space Complexity: O(1)
  Only a few pointers and a variable for the minimum.

Conclusion

The optimal solution is efficient and works well for large arrays. It’s the best approach for interviews and practical use.

Final Thoughts

The “Find Minimum in Rotated Sorted Array” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.