algoadvance

Leetcode 153. Find Minimum in Rotated Sorted Array

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n (inclusive) times. For example, the array nums = [0,1,2,4,5,6,7] might become:

You are given a rotated sorted array nums of unique elements and need to return the minimum element of this array.

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

Clarifying Questions

  1. Can the array be empty?
    • No, the array will have at least one element.
  2. Are there any duplicates in the array?
    • No, the array contains unique elements.

Strategy

Given the constraints and the requirement for logarithmic time complexity, a binary search approach is suitable. Here’s the strategy:

  1. Use two pointers, left and right, to perform the binary search.
  2. Calculate the middle index as mid = left + (right - left) / 2.
  3. Compare nums[mid] with nums[right] to determine which part of the array to search next:
    • If nums[mid] > nums[right], then the smallest value must be to the right of mid (including right itself).
    • If nums[mid] <= nums[right], then the smallest value is to the left of mid, including the middle element itself.
  4. Adjust the pointers accordingly and repeat the process until left equals right, where the minimum element will be located at index left.

Code

public class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

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

            if (nums[mid] > nums[right]) {
                // Minimum must be in the right part
                left = mid + 1;
            } else {
                // Minimum could be at mid or in the left part
                right = mid;
            }
        }
        
        return nums[left];
    }
}

Time Complexity

The time complexity of this solution is O(log n), where n is the number of elements in the array. This is due to the binary search approach that reduces the search space by approximately half in each iteration.

The space complexity is O(1) since no extra space is used besides a few variables.

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