Find Minimum in Rotated Sorted Array — Locate the Pivot [LC 153, Google, Amazon]

Problem Statement#

LeetCode 153 — Find Minimum in Rotated Sorted Array · Difficulty: Medium

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array.

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

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All integers in nums are unique
• nums is sorted and rotated between 1 and n times

Example 1:

Input:  nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input:  nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0,1,2,3,4,5,6,7] rotated 4 times.

Example 3:

Input:  nums = [11, 13, 15, 17]
Output: 11
Explanation: The original array was [11,13,15,17] rotated 4 times (full rotation = no change).

Why This Problem Matters#

LC 153 is a foundational rotation problem that appears repeatedly in FAANG interviews, especially as a warm-up or follow-up to LC 33. It tests a clean, distinct insight: to find the minimum in a rotated array, you are really looking for the rotation pivot — the single point where the array drops from a large value to a small one.

The problem matters beyond the interview room because the pattern — comparing the midpoint to a boundary to determine which side of a structural discontinuity you are on — generalizes widely. It is exactly how you find the peak in a bitonic array (LC 852), the first bad version (LC 278), and the leftmost position satisfying a monotonic predicate in any binary search on answer problems.

Interviewers use LC 153 to verify two things: first, that you know to compare nums[mid] with nums[hi] (not nums[lo]) to determine which side the minimum is on; second, that you use the while lo < hi template with hi = mid (not hi = mid - 1) to avoid skipping the minimum when it happens to sit at mid.

The Core Insight#

A rotated sorted array looks like two ascending runs: a larger run on the left and a smaller run on the right, joined at the rotation point. The minimum element is at the start of the right (smaller) run — the first element after the single drop.

At any mid, compare nums[mid] with nums[hi]:

• If nums[mid] > nums[hi]: the minimum is in the right half (the drop happened to the right of mid). Set lo = mid + 1.
• If nums[mid] < nums[hi]: the minimum is in the left half including mid (the drop happened to the left of mid). Set hi = mid.

Because all values are unique, nums[mid] == nums[hi] only when lo == hi, which terminates the loop. When the loop ends, lo == hi and nums[lo] is the minimum.

Critical template choice: use while lo < hi with hi = mid (not hi = mid - 1). This preserves mid as a candidate for the minimum, which is necessary because the minimum itself sits exactly at the boundary.

Visual Dry Run#

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

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

Edge case — no rotation: nums = [1, 2, 3, 4, 5]

Common Mistakes#

1. Comparing nums[mid] with nums[lo] instead of nums[hi]. Comparing to lo works for LC 33 (searching for a target) but breaks here. The minimum is always on the side where values are smaller than nums[hi]. Comparing to lo creates an ambiguous case when the array is not rotated.

2. Using hi = mid - 1 instead of hi = mid. When nums[mid] < nums[hi], the minimum could be at mid itself. Using hi = mid - 1 skips mid and can miss the minimum entirely. This is the most common implementation bug on this problem.

3. Using while lo <= hi with the hi = mid update. That combination can cause an infinite loop when lo == hi. The hi = mid update is only safe with while lo < hi, which exits as soon as lo == hi.

4. Not handling the unrotated array. An array rotated n times (or 0 times) is just the original sorted array. The algorithm handles this correctly — nums[mid] < nums[hi] is always true and the search converges on nums[0] — but candidates often panic when they realize the "rotation" is zero and try to add special cases.

5. Returning nums[mid] inside the loop. Unlike LC 33 (where you return immediately when nums[mid] == target), here you never return inside the loop. The loop shrinks the range to a single element, and you return nums[lo] after the loop ends.

6. Confusing this with finding the maximum. The maximum is the element just before the minimum — at index (pivot_index - 1 + n) % n. Trying to find the maximum using the same template without adjustment gives wrong results.

Solutions#

Python#

def findMin(nums: list[int]) -> int:
    lo, hi = 0, len(nums) - 1          # inclusive bounds
 
    # Use lo < hi so the loop exits exactly when lo == hi (single candidate)
    while lo < hi:
        mid = lo + (hi - lo) // 2      # safe midpoint, avoids overflow
 
        if nums[mid] > nums[hi]:
            # nums[mid] is greater than the rightmost element.
            # The single drop (rotation point) must be to the RIGHT of mid.
            # The minimum is somewhere in (mid, hi].
            lo = mid + 1               # exclude mid — it is too large to be minimum
 
        else:
            # nums[mid] <= nums[hi].
            # The minimum is at mid or to the LEFT of mid.
            # Keep mid as a candidate by setting hi = mid (not mid - 1).
            hi = mid                   # include mid as a possible minimum
 
    # When lo == hi, both pointers converge on the minimum.
    return nums[lo]

JavaScript#

function findMin(nums) {
    let lo = 0;
    let hi = nums.length - 1;          // inclusive upper bound
 
    // Exit condition: lo < hi ensures we stop when range collapses to one element
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2); // safe midpoint
 
        if (nums[mid] > nums[hi]) {
            // The rotation drop is somewhere to the RIGHT of mid.
            // nums[mid] cannot be the minimum — safely exclude it.
            lo = mid + 1;
        } else {
            // nums[mid] <= nums[hi]: the minimum is at mid or to the left.
            // We must keep mid as a candidate, so set hi = mid (not mid - 1).
            hi = mid;
        }
    }
 
    // lo and hi have converged — nums[lo] is the minimum.
    return nums[lo];
}

Complexity Analysis#

Each iteration sets either lo = mid + 1 or hi = mid, always strictly shrinking the search space. After at most ceil(log₂(n)) iterations the loop exits. For n = 5000 this is at most 13 iterations. Only three integer variables are used — space is O(1).

Follow-up Questions#

Q: What if the array contains duplicates (LC 154)? When nums[mid] == nums[hi], you cannot determine which side the minimum is on. The safe fix: decrement hi by 1. This degrades worst-case to O(n) (e.g., all elements identical) but stays correct.

Q: After finding the minimum, how do you find the rotation pivot index? The minimum's index is the pivot index. Everything before it belongs to the left (larger) sorted run; everything from it onward belongs to the right (smaller) run.

Q: Can you use this result to binary search the rotated array efficiently? Yes. Find the pivot index p = lo after this algorithm. If target >= nums[0], binary search [0, p-1]. Otherwise binary search [p, n-1]. This is the two-pass alternative to LC 33's single-pass approach.

Q: How would you find the maximum element? Apply the same algorithm and return nums[(lo - 1 + n) % n] — the element just before the minimum in the circular order.

This Pattern Solves#

• LC 153 — Find Minimum in Rotated Sorted Array (this problem)
• LC 154 — Find Minimum in Rotated Sorted Array II (with duplicates)
• LC 33 — Search in Rotated Sorted Array (find pivot first, then binary search)
• LC 852 — Peak Index in a Mountain Array (same mid-vs-boundary comparison)
• Any problem where you must locate a structural boundary (peak, valley, pivot) in a transformed sorted array

Key Takeaway#

To find the minimum in a rotated sorted array, compare nums[mid] with nums[hi]. If nums[mid] > nums[hi], the rotation point is to the right — move lo up. Otherwise the minimum is at mid or to the left — move hi down to mid (not mid - 1). Use while lo < hi so the loop exits cleanly when both pointers meet. The final answer is nums[lo]. This mid-vs-hi comparison and the hi = mid update are the two details that distinguish this problem from every other binary search template.

Key Takeaways#

• LC 153 is a favourite follow-up to LC 33 at Google and Amazon; it tests whether you understand pivot-finding as a distinct binary search pattern.
• Compare nums[mid] with nums[hi] — not nums[lo] — to correctly identify which side of the rotation point you are on.
• When nums[mid] > nums[hi], the minimum is strictly to the right of mid, so lo = mid + 1 (safe to exclude mid).
• When nums[mid] <= nums[hi], the minimum is at mid or to the left, so hi = mid (never mid - 1 — mid is still a candidate).
• Use while lo < hi — the loop exits when lo == hi, and nums[lo] is the answer; never return inside the loop.
• The algorithm handles the unrotated case naturally: nums[mid] < nums[hi] always holds, converging to nums[0].
• The minimum's index is the pivot index; use it to split the array for a two-pass binary search alternative to LC 33.