153. Find Minimum in Rotated Sorted Array

Description

Given a sorted array of unique elements that has been rotated at some pivot unknown to you beforehand, find the minimum element in the array. For example, the array [3, 4, 5, 1, 2] was originally [1, 2, 3, 4, 5] rotated at the pivot 3.

Intuition

The rotated sorted array has a property where the smallest element is the point where the array was rotated. This means that the smallest element is the point where the sequence changes from being larger to smaller.

Approach

1. Initialize Pointers: Start with two pointers, l (left) and r (right), representing the start and end of the array, respectively.
2. Binary Search: - Calculate the middle index m. - If the array is already sorted between l and r (i.e., nums[l] < nums[r]), then the smallest element is nums[l]. - If the left half is sorted (nums[l] <= nums[m]), move the left pointer to m + 1 to search in the right half. - Otherwise, the minimum element must be in the left half, so move the right pointer to m.
3. Return Result: Once the loop exits, l will point to the smallest element.

Complexity

Time Complexity:

(O(\log n)), where (n) is the number of elements in the array. This is because we are using binary search to find the minimum element.

Space Complexity:

(O(1)), as we are only using a constant amount of extra space for pointers and variables.

Code

C++

class Solution {
public:
    int findMin(vector& nums) {
        int l = 0;
        int r = nums.size() - 1;

        while (l < r) {
            int m = l + (r - l) / 2;

            if (nums[l] < nums[r]) return nums[l];

            if (nums[l] <= nums[m]) {
                l = m + 1;
            } else {
                r = m;
            }
        }

        return nums[l];
    }
};

Python

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = l + (r - l) // 2

            if nums[l] < nums[r]:
                return nums[l]

            if nums[l] <= nums[m]:
                l = m + 1
            else:
                r = m

        return nums[l]

Java

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

        while (l < r) {
            int m = l + (r - l) / 2;

            if (nums[l] < nums[r]) return nums[l];

            if (nums[l] <= nums[m]) {
                l = m + 1;
            } else {
                r = m;
            }
        }

        return nums[l];
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const findMin = function (nums) {
    let [l, r] = [0, nums.length - 1];

    while (l < r) {
        const m = Math.floor((l + r) / 2);

        if (nums[l] < nums[r]) return nums[l];

        if (nums[l] <= nums[m]) {
            l = m + 1;
        } else {
            r = m;
        }
    }

    return nums[l];
};

console.log(findMin([2, 3, 4, 5, 1]));