LeetCode 153. Find Minimum in Rotated Sorted Array

Question

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.

Example

• Input: nums = [3,4,5,1,2]

• Output: 1

• Explanation: The original array was [1,2,3,4,5] rotated 3 times.

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

        while (left < right) {
            mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
            else if (nums[mid] <= nums[right]) {
                right = mid;
            }
        }
        return nums[left];
    }
};

Problem Summary

Given a sorted array of a unique elements that has been rotated, find the minimum element in the array. The algorithm must have a time complexity of O(logn).

Core Idea

The key constraints is the O(logn) time complexity, which stongly suggests a Binary Search approach.

Although the entire array is not sorted, it is composed of two sorted subarrays. The minimum element is the “pivot” point where the rotation occurs (i.e., the first element of the second sorted array.)

The strategy is to use binary search to efficiently find this pivot point. We can determine which of the two sorted subarrays our mid pointer is in by comparing nums[mid] with the element at the right boundary, nums[right] .

Algorithm Logic

1. Initialize two pinters: left = 0 and right = num.size() - 1 .

2. Loop as long as left < right.

3. Calculate middle index using left + (right - left) / 2 . This formula is preferred over (left + right) / 2 to prevent potential integer overflow if the numbers are very large.

4. Compare num[mid] with nums[right] to decide which half of the array to discard:

   • If nums[mid] > nums[right] : This indicates that the mid element is in the larger, left sorted subarray. Therefore, the pivot must be in the right half. We discard the left half by setting left = mid + 1 .

   • If num[mid] ≤ nums[right] : This indicates that the segment from mid to right is sorted. The minimum element must be in the left half, and it’s possible that nums[mid] is the minimum itself. We discard the right half by setting right = mid .

5. The loop terminates when left and right converge to the same index. This index holds the minimum element in the array.

6. Return nums[left]

7. if nums[mid] > nums[right], then make the left flag be mid + 1.

8. else if nums[mid] ≤ nums[right], make the right flag be mid.

Example Walkthrough

Let's trace the algorithm with nums = [3, 4, 5, 1, 2].

• Initial State: left = 0, right = 4

• Iteration 1:

  • mid = 0 + (4 - 0) / 2 = 2

  • nums[mid] is nums[2], which is 5.

  • nums[right] is nums[4], which is 2.

  • Condition nums[mid] > nums[right] (5 > 2) is true.

  • The minimum must be to the right of mid. We update left = mid + 1 = 3.

  • New search space: [3, 4] (elements [1, 2]).

• Iteration 2:

  • left = 3, right = 4.

  • mid = 3 + (4 - 3) / 2 = 3.

  • nums[mid] is nums[3], which is 1.

  • nums[right] is nums[4], which is 2.

  • Condition nums[mid] > nums[right] (1 > 2) is false. We use the else block.

  • The minimum is in the left half (or mid is the minimum). We update right = mid = 3.

  • New search space: [3, 3] (element [1]).

• Termination:

  • Now, left = 3 and right = 3. The while (left < right) condition is false. The loop ends.

• Result:

  • Return nums[left], which is nums[3], giving us the answer 1.