Blind 75 - problem 7 : Find Minimum in Rotated Sorted Array

Problem Statement

Find Minimum in Rotated Sorted Array

Suppose you have a sorted array of distinct integers and it has been rotated at some pivot. For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].

You need to find the minimum element in this rotated sorted array.

Example 1:

Input: [3,4,5,1,2]
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

Example 3:

Input: [11,13,15,17]
Output: 11

You must write a solution that has a time complexity of O(log n).

---

Optimal Approach

The most efficient way to solve this problem is by using binary search. The key idea is that in a rotated sorted array, one part of the array (either left or right) is still sorted. By using binary search, we can exploit this property to find the minimum element in O(log n) time.

Steps:

1. Initialization:
   • Start with two pointers: left at the beginning of the array and right at the end of the array.
2. Binary Search Logic:
   • Calculate the middle index: mid = (left + right) / 2.
   • If nums[mid] is greater than nums[right], the minimum element must be in the right half, so move the left pointer to mid + 1.
   • Otherwise, the minimum element must be in the left half, so move the right pointer to mid.
3. Termination:
   • The loop will terminate when left == right, at which point nums[left] will be the minimum element.

---

LeetCode-Compatible Code Implementations

C++ Solution (Optimal Approach)

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] > nums[right]) {
                // Minimum is in the right half
                left = mid + 1;
            } else {
                // Minimum is in the left half
                right = mid;
            }
        }
        
        return nums[left];  // or nums[right] since left == right here
    }
};

Regular C++ Solution with Use Cases

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return nums[left];
}

int main() {
    vector<int> nums = {3, 4, 5, 1, 2};
    cout << "Minimum Element: " << findMin(nums) << endl;
    
    vector<int> nums2 = {4, 5, 6, 7, 0, 1, 2};
    cout << "Minimum Element: " << findMin(nums2) << endl;
    
    return 0;
}

---

Step-by-Step Explanation of Code

1. Initialization:
   • Set left = 0 and right = nums.size() - 1.
2. Binary Search Loop:
   • In each iteration, calculate the middle index: mid = left + (right - left) / 2.
   • Compare nums[mid] with nums[right]:
     • If nums[mid] > nums[right], the minimum is on the right side of mid, so set left = mid + 1.
     • Otherwise, the minimum is on the left side, so set right = mid.
3. Termination:
   • The loop stops when left == right, which means we have found the minimum element at that index. Return nums[left].

---

Dry Run / Execution Steps

Input: [3, 4, 5, 1, 2]

1. Initial: left = 0, right = 4 (array length is 5).

2. First iteration:

   • mid = 2 (nums[2] = 5).
   • nums[mid] (5) > nums[right] (2), so we update left = mid + 1 = 3.

3. Second iteration:

   • mid = 3 (nums[3] = 1).
   • nums[mid] (1) < nums[right] (2), so we update right = mid = 3.

4. Termination:

   • Now left = 3, right = 3. The loop terminates, and the minimum is nums[3] = 1.

Output: 1

---

Alternative Approaches & Why Not?

1. Brute Force

• Description: Simply iterate over the array and find the minimum element.
• Time Complexity: O(n), where n is the number of elements in the array.
• Space Complexity: O(1).

Why Not?: While this approach is simple, it does not satisfy the problem's constraint of O(log n) time complexity.

2. Sorting

• Description: Sort the array and return the first element.
• Time Complexity: O(n log n) due to sorting.
• Space Complexity: O(n) for storing the sorted array.

Why Not?: This approach is less efficient than binary search because sorting the entire array takes O(n log n), which is slower than O(log n).

---

Best Solution & Why It’s Best

Optimal Solution with Binary Search

• Time Complexity: O(log n), where n is the number of elements in the array. Binary search allows us to narrow down the range in logarithmic time.
• Space Complexity: O(1), as we only use a few variables.

Binary search is the most efficient approach because it satisfies the problem's constraint of O(log n) time complexity, making it much faster than brute force or sorting.

Comparison Table:

Approach	Time Complexity	Space Complexity
Brute Force	O(n)	O(1)
Sorting	O(n log n)	O(n)
Binary Search (Best)	O(log n)	O(1)

---

Complexity Analysis

• Brute Force:

  • Time Complexity: O(n) because we iterate over the array.
  • Space Complexity: O(1).

• Sorting:

  • Time Complexity: O(n log n) due to sorting.
  • Space Complexity: O(n) for storing the sorted array.

• Binary Search:

  • Time Complexity: O(log n), as binary search only requires logarithmic iterations.
  • Space Complexity: O(1), since only a few pointers are used.

---

Conclusion

The binary search approach is the most efficient for solving the "Find Minimum in Rotated Sorted Array" problem. It runs in O(log n) time and uses O(1) space, making it the best solution. Avoid brute force and sorting methods, as they are not optimal for this problem.

For similar problems, you can practice with the following:

• LeetCode - Search in Rotated Sorted Array.
• LeetCode - Find Peak Element.