Find Minimum in Rotated Sorted Array

LeetCode 153: Find Minimum in Rotated Sorted Array Solution & Explanation

Problem Overview

TL;DR: Use a modified binary search to locate the "pivot" point where the array order resets, comparing the middle element against the right boundary to determine which half contains the minimum.

The problem asks us to find the minimum element in an array of unique integers that was originally sorted in ascending order but has been rotated between 1 and n times. For example, [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. We must return the smallest value. This is a classic interview question, and the optimal LeetCode 153 solution requires an algorithm with logarithmic time complexity.

Brute Force Approach for Find Minimum in Rotated Sorted Array

The most straightforward way to solve "Find Minimum in Rotated Sorted Array" is to iterate through the entire array and track the minimum value found so far.

Naive Algorithm:

1. Initialize a variable min_val to infinity or the first element of the array.
2. Traverse every element in the array.
3. If the current element is smaller than min_val, update min_val.
4. Return min_val.

Pseudo-code:

function findMin(nums):
    min_val = nums[0]
    for x in nums:
        if x < min_val:
            min_val = x
    return min_val

Time Complexity Analysis: The time complexity is O(N), where N is the length of the array, because we must inspect every element once.

Why it fails: While this approach produces the correct result, the problem explicitly mandates an O(log n) time complexity. A linear scan is too slow to satisfy the constraints of the optimal solution, particularly for large datasets where binary search is expected.

Algorithm Strategy: Binary Search Patterns

We implement the Binary Search - Find Min/Max in Rotated Sorted Array strategy as follows:

1. Initialization: Set two pointers, left at index 0 and right at index n - 1.
2. Loop Condition: Continue the search while left < right. We stop when left == right, at which point we have converged on the single minimum element.
3. Midpoint Calculation: Calculate mid to avoid overflow: left + (right - left) / 2.
4. Decision Logic:
   • Compare nums[mid] with nums[right].
   • If nums[mid] > nums[right], the minimum is in the right half. Move left to mid + 1.
   • If nums[mid] < nums[right], the minimum is in the left half or is mid itself. Move right to mid.
5. Result: When the loop terminates, nums[left] (or nums[right]) is the minimum.

Note that we do not check nums[mid] == nums[right] because the problem guarantees unique elements.

Execution Flow

Let's trace the algorithm with the input nums = [4, 5, 6, 7, 0, 1, 2].

1. Initial State:

   • left = 0, right = 6.
   • Array range: [4, 5, 6, 7, 0, 1, 2].

2. Iteration 1:

   • mid = 0 + (6 - 0) / 2 = 3.
   • nums[mid] is 7. nums[right] is 2.
   • Comparison: 7 > 2 is True.
   • Logic: The left part [4, 5, 6, 7] consists of large values. The minimum is to the right.
   • Update: left = mid + 1 = 4.

3. Iteration 2:

   • Current range: indices [4, 6]. Values: [0, 1, 2].
   • mid = 4 + (6 - 4) / 2 = 5.
   • nums[mid] is 1. nums[right] is 2.
   • Comparison: 1 > 2 is False.
   • Logic: nums[mid] < nums[right] means the range [mid, right] is sorted. The minimum is at mid or to its left.
   • Update: right = mid = 5.

4. Iteration 3:

   • Current range: indices [4, 5]. Values: [0, 1].
   • mid = 4 + (5 - 4) / 2 = 4.
   • nums[mid] is 0. nums[right] (index 5) is 1.
   • Comparison: 0 > 1 is False.
   • Logic: nums[mid] < nums[right].
   • Update: right = mid = 4.

5. Termination:

   • left (4) is no longer less than right (4).
   • Loop ends. Return nums[4], which is 0.

Proof of Correctness

The correctness relies on the invariant that the minimum element is always within the search range [left, right].

1. Base Case: Initially, the minimum is somewhere in the full array.
2. Inductive Step:
   • If nums[mid] > nums[right], the pivot (minimum) must be in the index range (mid, right]. By setting left = mid + 1, we preserve the minimum in the new range.
   • If nums[mid] < nums[right], the sequence from mid to right is ascending. The minimum cannot be in (mid, right]. Thus, it must be in [left, mid]. By setting right = mid, we preserve the minimum in the new range.
3. Termination: The range size decreases by at least 1 in each step (since mid < right is guaranteed by the floor division). Eventually, left == right, pointing to the single remaining candidate, which must be the minimum.

Pattern Reuse Notes

The Binary Search - Find Min/Max in Rotated Sorted Array pattern is versatile. Understanding how to use the array's structure to guide the binary search steps is applicable to several other problems:

• LeetCode 33: Search in Rotated Sorted Array - Uses similar logic to find a specific target rather than the minimum.
• LeetCode 81: Search in Rotated Sorted Array II - Handles duplicates, adding a step to handle cases where nums[mid] == nums[right].
• LeetCode 162: Find Peak Element - Uses a similar local slope check to find a peak in logarithmic time.
• LeetCode 852: Peak Index in a Mountain Array - Finds the maximum in a bitonic array using binary search.

Reference Implementation

C++ Solution for LeetCode 153

1class Solution {
2public:
3    int findMin(vector<int>& nums) {
4        int left = 0;
5        int right = nums.size() - 1;
6
7        // Loop until the search space converges to a single element
8        while (left < right) {
9            int mid = left + (right - left) / 2;
10
11            // If mid element is greater than right element,
12            // the minimum is in the right half (excluding mid)
13            if (nums[mid] > nums[right]) {
14                left = mid + 1;
15            } 
16            // If mid element is less than right element,
17            // the minimum is in the left half (including mid)
18            else {
19                right = mid;
20            }
21        }
22
23        // When left == right, we have found the minimum
24        return nums[left];
25    }
26};

Java Solution for LeetCode 153

1class Solution {
2    public int findMin(int[] nums) {
3        int left = 0;
4        int right = nums.length - 1;
5
6        // Loop until pointers meet
7        while (left < right) {
8            int mid = left + (right - left) / 2;
9
10            // Compare mid with the right boundary
11            if (nums[mid] > nums[right]) {
12                // Minimum is to the right
13                left = mid + 1;
14            } else {
15                // Minimum is at mid or to the left
16                right = mid;
17            }
18        }
19
20        return nums[left];
21    }
22}

Python Solution for LeetCode 153

1class Solution:
2    def findMin(self, nums: List[int]) -> int:
3        left, right = 0, len(nums) - 1
4        
5        while left < right:
6            mid = left + (right - left) // 2
7            
8            # If the middle element is greater than the rightmost element,
9            # the minimum value must be in the right portion.
10            if nums[mid] > nums[right]:
11                left = mid + 1
12            else:
13                # Otherwise, the minimum is at mid or in the left portion.
14                right = mid
15                
16        return nums[left]