153. Find Minimum In Rotated Sorted Array - Explanation

Description

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

[3,4,5,6,1,2] if it was rotated 4 times.
[1,2,3,4,5,6] if it was rotated 6 times.

Notice that rotating the array 4 times moves the last four elements of the array to the beginning. Rotating the array 6 times produces the original array.

Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.

A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?

Example 1:

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

Output: 1

Example 2:

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

Output: 0

Example 3:

Input: nums = [4,5,6,7]

Output: 4

Constraints:

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000

Topics

Array Binary Search

Recommended Time & Space Complexity

You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to do a linear search on the array to find the minimum element. This would be an O(n) solution. Can you think of a better way? Maybe an efficient searching algorithm is helpful.

Hint 2

Given that the array is rotated after sorting, elements from the right end are moved to the left end one by one. This creates two parts of a sorted array, separated by a deflection point caused by the rotation. For example, consider the array [3, 4, 1, 2]. Here, the array is rotated twice, resulting in two sorted segments: [3, 4] and [1, 2]. And the minimum element will be the first element of the right segment. Can you do a binary search to find this cut?

Hint 3

We perform a binary search on the array with pointers l and r, which belong to two different sorted segments. For example, in [3, 4, 5, 6, 1, 2], l = 0, r = 5, and mid = 2. At least two of l, mid, and r will always be in the same sorted segment. Can you find conditions to eliminate one half and continue the binary search? Perhaps analyzing all possible conditions for l, mid, and r would help.

Hint 4

There will be two conditions where l and mid will be in left sorted segment or mid and r will be in right sorted segement. If l and mid in sorted segement, then nums[l] < nums[mid] and the minimum element will be in the right part. If mid and r in sorted segment, then nums[mid] < nums[r] and the minimum element will be in the left part. After the binary search we end up finding the minimum element.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search - The optimal solution adapts binary search to work on a rotated array by determining which half contains the minimum
Array Rotation Concept - Understanding how rotation shifts elements helps identify the sorted and unsorted portions of the array

1. Brute Force

Intuition

A rotated sorted array still contains all its original values, just shifted.
So the simplest way to find the minimum is to look at every element and pick the smallest one.
This requires no special logic and works in all cases, but it is not the most efficient.

Algorithm

Scan through the entire array.
Track the smallest value seen so far.
After checking every element, return the minimum.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        return min(nums)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Binary Search

Intuition

A rotated sorted array has one special property:
one part is always sorted, and the other part contains the rotation (and the minimum element).

We can use binary search to identify which side is sorted:

If the left half is sorted, then the minimum cannot be there, so we search the right half.
If the right half is sorted, then the minimum must be in the left half (or at the midpoint).

This lets us eliminate half of the array each time and quickly narrow down to the smallest value.

Algorithm

Initialize left = 0, right = n - 1, and store the first element as the current answer.
While left <= right:
- If the current window is already sorted, update the answer with nums[left] and stop.
- Compute mid.
- Update the answer with nums[mid].
- If the left half is sorted:
  - Move search to the right half.
- Otherwise:
  - Search in the left half.
Return the smallest value found.

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

        while l <= r:
            if nums[l] < nums[r]:
                res = min(res, nums[l])
                break

            m = (l + r) // 2
            res = min(res, nums[m])
            if nums[m] >= nums[l]:
                l = m + 1
            else:
                r = m - 1
        return res

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

        while (l <= r) {
            if (nums[l] < nums[r]) {
                res = Math.min(res, nums[l]);
                break;
            }

            int m = l + (r - l) / 2;
            res = Math.min(res, nums[m]);
            if (nums[m] >= nums[l]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return res;
    }
}

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

        while (l <= r) {
            if (nums[l] < nums[r]) {
                res = min(res, nums[l]);
                break;
            }
            int m = l + (r - l) / 2;
            res = min(res, nums[m]);

            if (nums[m] >= nums[l]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return res;
    }
};

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

        while (l <= r) {
            if (nums[l] <= nums[r]) {
                res = Math.min(res, nums[l]);
                break;
            }

            let m = l + Math.floor((r - l) / 2);
            res = Math.min(res, nums[m]);
            if (nums[m] >= nums[l]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return res;
    }
}

public class Solution {
    public int FindMin(int[] nums) {
        int l = 0, r = nums.Length - 1;
        int res = nums[0];

        while (l <= r) {
            if (nums[l] < nums[r]) {
                res = Math.Min(res, nums[l]);
                break;
            }

            int m = l + (r - l) / 2;
            res = Math.Min(res, nums[m]);
            if (nums[m] >= nums[l]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return res;
    }
}

func findMin(nums []int) int {
    res := nums[0]
    l, r := 0, len(nums)-1

    for l <= r {
        if nums[l] < nums[r] {
            if nums[l] < res {
                res = nums[l]
            }
            break
        }

        m := l + (r-l)/2
        if nums[m] < res {
            res = nums[m]
        }

        if nums[m] >= nums[l] {
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return res
}

class Solution {
    fun findMin(nums: IntArray): Int {
        var res = nums[0]
        var l = 0
        var r = nums.size - 1

        while (l <= r) {
            if (nums[l] < nums[r]) {
                res = minOf(res, nums[l])
                break
            }

            val m = l + (r - l) / 2
            res = minOf(res, nums[m])

            if (nums[m] >= nums[l]) {
                l = m + 1
            } else {
                r = m - 1
            }
        }
        return res
    }
}

class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var res = nums[0]
        var l = 0, r = nums.count - 1

        while l <= r {
            if nums[l] < nums[r] {
                res = min(res, nums[l])
                break
            }

            let m = (l + r) / 2
            res = min(res, nums[m])

            if nums[m] >= nums[l] {
                l = m + 1
            } else {
                r = m - 1
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Binary Search (Lower Bound)

Intuition

In a rotated sorted array, the minimum element is the first element of the rotated portion.
Using binary search, we compare the middle value with the rightmost value:

If nums[mid] < nums[right], then the minimum lies in the left half (including mid).
Otherwise, the minimum lies in the right half (excluding mid).

This behaves exactly like finding a lower bound, gradually shrinking the search space until only the minimum remains.

Algorithm

Set left = 0 and right = n - 1.
While left < right:
- Compute mid.
- If nums[mid] is less than nums[right], move right to mid (minimum is on the left).
- Otherwise, move left to mid + 1 (minimum is on the right).
When the loop ends, left points to the smallest element.
Return nums[left].

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[m] < nums[r]:
                r = m
            else:
                l = m + 1
        return nums[l]

public 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[m] < nums[r]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findMin(nums) {
        let l = 0,
            r = nums.length - 1;
        while (l < r) {
            let m = l + Math.floor((r - l) / 2);
            if (nums[m] < nums[r]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }
}

public 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[m] < nums[r]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }
}

func findMin(nums []int) int {
    l, r := 0, len(nums)-1
    for l < r {
        m := l + (r-l)/2
        if nums[m] < nums[r] {
            r = m
        } else {
            l = m + 1
        }
    }
    return nums[l]
}

class Solution {
    fun findMin(nums: IntArray): Int {
        var l = 0
        var r = nums.size - 1
        while (l < r) {
            val m = l + (r - l) / 2
            if (nums[m] < nums[r]) {
                r = m
            } else {
                l = m + 1
            }
        }
        return nums[l]
    }
}

class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var l = 0, r = nums.count - 1
        while l < r {
            let m = l + (r - l) / 2
            if nums[m] < nums[r] {
                r = m
            } else {
                l = m + 1
            }
        }
        return nums[l]
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

Comparing Mid with Left Instead of Right

In the lower bound approach, comparing nums[mid] with nums[left] instead of nums[right] can lead to incorrect boundary updates, especially when the array is not rotated or rotated by n positions. Comparing with the rightmost element consistently determines which half contains the minimum.

Off-by-One Errors in Boundary Updates

When nums[mid] < nums[right], the minimum could be at mid itself, so set right = mid (not mid - 1). When nums[mid] >= nums[right], the minimum must be in the right half, so set left = mid + 1. Using wrong update logic either skips the minimum or causes infinite loops.

Not Handling the Non-Rotated Case

A sorted array with no rotation (or rotated by n positions) is still valid input. The minimum is simply the first element. Some binary search implementations fail on this edge case by not recognizing that the entire array is already sorted. Always check if nums[left] < nums[right] to detect this case early.