algoadvance

Leetcode 153. Find Minimum in Rotated Sorted Array

Problem Statement

You are given an integer array nums sorted in ascending order (with distinct values), and a rotation of nums, where nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

For example, the array nums = [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Return the minimum element of this rotated array.

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

Example 1:

Example 2:

Example 3:

Clarifying Questions

  1. Q1: Are there any constraints on the size of the array?
    • A1: The array will have at least one element and can be as large as (10^5).
  2. Q2: Can the array contain duplicate elements?
    • A2: No, all elements are distinct as per the problem statement.
  3. Q3: Can the initial sorted array be rotated zero times (i.e., still sorted)?
    • A3: Yes, that’s a possibility. In this case, the smallest element will be the first element.

Strategy

To find the minimum element in a rotated sorted array in (O(\log n)) time, we can utilize a modified binary search approach:

  1. Identifying the Minimum Element:
    • The minimum element is the only one which is smaller than its previous neighbor (considering array in circular way).
    • We need to find the point where the sorted order breaks, which is exactly the minimum element.
  2. Binary Search:
    • Initialize left to 0 and right to n-1.
    • While left < right, compute the mid index.
    • If nums[mid] > nums[right], it means the smallest value is to the right of mid, so move left to mid + 1.
    • If nums[mid] < nums[right], it means the smallest value is to the left of mid (including mid itself), so move right to mid.
    • When left == right, the smallest value is found.

Time Complexity

The algorithm performs binary search, so the time complexity is (O(\log n)).

Code

#include <vector>
#include <iostream>

class Solution {
public:
    int findMin(std::vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        // Binary search for the smallest element
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] > nums[right]) {
                // The minimum is to the right of mid
                left = mid + 1;
            } else {
                // The minimum can be at mid or to the left of mid
                right = mid;
            }
        }
        
        return nums[left];
    }
};

int main() {
    Solution sol;
    
    // Test Cases
    std::vector<int> nums1 = {3, 4, 5, 1, 2};
    std::vector<int> nums2 = {4, 5, 6, 7, 0, 1, 2};
    std::vector<int> nums3 = {11, 13, 15, 17};

    std::cout << sol.findMin(nums1) << std::endl; // Output: 1
    std::cout << sol.findMin(nums2) << std::endl; // Output: 0
    std::cout << sol.findMin(nums3) << std::endl; // Output: 11

    return 0;
}

This solution successfully finds the minimum element in a rotated sorted array using an efficient (O(\log n)) approach with binary search.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI