Find Min Rotated Array LeetCode 153

LeetCode 153, Find Minimum in Rotated Sorted Array, gives you a sorted array of unique integers that has been rotated at some unknown pivot index. For example, [3,4,5,1,2] was originally [1,2,3,4,5] rotated at index 3. Your task is to find and return the minimum element. A naive O(n) linear scan would work, but the problem requires an O(log n) solution.

The rotation creates a specific structure: one contiguous portion of the array is sorted in ascending order, and another portion is sorted in ascending order, but the two portions are out of global order relative to each other. The minimum element sits exactly at the rotation pivot — the point where the larger values end and the smaller values begin.

Key constraints to keep in mind: all elements in the array are unique, the array length is between 1 and 5000, and element values are in the range -5000 to 5000. The no-duplicates guarantee is important — it means comparing nums[mid] with nums[right] is always unambiguous and we never need a third case to handle equals.

Standard binary search works on a fully sorted array by comparing the target with nums[mid] and eliminating one half. A rotated array is not globally sorted, so we cannot directly compare against a target value. Instead, we need a different comparison to decide which half to search — one that exploits the structure that the rotation creates.

The key observation is that after any rotation, at least one half of the array is always sorted. If we split the array at mid, either the left half [lo..mid] is sorted or the right half [mid..hi] is sorted (or both if there is no rotation). We can use this invariant to determine which half contains the minimum.

The comparison to use is nums[mid] vs nums[right]. If nums[mid] > nums[right], the right half is not sorted — the minimum must be somewhere in the right half (after mid). If nums[mid] <= nums[right], the right half is sorted — the minimum is either mid itself or somewhere in the left half. This single comparison drives the entire algorithm.

The algorithm maintains two pointers, lo and hi, starting at the first and last indices. At each step, compute mid = lo + (hi - lo) // 2. Compare nums[mid] with nums[hi] (equivalently nums[right]) to decide which half to eliminate.

If nums[mid] > nums[hi], the pivot and minimum are in the right half. The left half from lo to mid is sorted and all its values are greater than nums[hi], so the minimum cannot be there. Set lo = mid + 1 to discard the left half including mid.

If nums[mid] <= nums[hi], the right half from mid to hi is sorted in order. The minimum is either at mid or in the left half. We cannot discard mid because it might be the minimum, so set hi = mid (not mid - 1). The loop continues until lo == hi, at which point nums[lo] is the minimum.

Comparing with nums[left] (nums[lo]) is ambiguous because of two scenarios that produce the same comparison result but require opposite actions. If nums[mid] > nums[lo], it could mean (a) the left half is fully sorted and the minimum is in the right half, or (b) the entire array is sorted with no rotation and the minimum is at lo. These two cases require lo = mid + 1 and hi = mid respectively, but the comparison alone cannot distinguish them.

Comparing with nums[right] (nums[hi]) avoids this ambiguity entirely. When nums[mid] > nums[hi], it is impossible for the array to be fully sorted — a sorted array always has nums[mid] <= nums[hi]. So if nums[mid] > nums[hi], we know for certain the rotation pivot is in the right half, and lo = mid + 1 is always correct.

The invariant "comparing with right correctly identifies the unsorted half" is the conceptual core of this problem. Once you internalize it, the algorithm follows directly: unsorted half contains the minimum, compare with right to find the unsorted half, eliminate the sorted half.

The loop terminates when lo == hi. At this point, both pointers have converged on the same index, and that index holds the minimum element. The loop invariant guarantees that the minimum is always within [lo, hi] — each step either moves lo up or hi down without ever excluding the minimum — so the final single element must be the minimum.

Edge cases are all handled naturally. A single-element array: lo == hi from the start, the loop never runs, and nums[0] is returned immediately. An already-sorted array with no rotation: every comparison is nums[mid] <= nums[hi], so hi moves left step by step until lo == hi == 0, returning the first element. A two-element array: mid == lo, one comparison determines the result in a single iteration.

The use of hi = mid (not mid - 1) is the subtle but critical detail that makes edge cases work. Since mid could be the minimum, we must keep it in the search range. The loop condition lo < hi (not lo <= hi) ensures we do not infinite-loop when lo == mid, because in that case nums[mid] <= nums[hi] always moves hi to mid == lo, terminating the loop.

Python implementation is about 5 lines of core logic. Define lo = 0 and hi = len(nums) - 1. Loop while lo < hi. Compute mid = lo + (hi - lo) // 2. If nums[mid] > nums[hi]: lo = mid + 1. Else: hi = mid. Return nums[lo]. Time complexity O(log n), space O(1). No auxiliary data structures, no recursion stack.

Java implementation is structurally identical. int lo = 0, hi = nums.length - 1. while (lo < hi): int mid = lo + (hi - lo) / 2. if (nums[mid] > nums[hi]): lo = mid + 1. else: hi = mid. return nums[lo]. The integer division in Java truncates toward zero just like Python floor division for positive numbers, so the behavior is identical.

Interview strategy: write the while lo < hi loop first, then fill in the two-branch comparison. Emphasize that hi = mid (not mid - 1) is intentional — explain why mid cannot be excluded. Mention the no-duplicates constraint as the reason the equal case goes into the else branch without ambiguity. Clean, confident explanation of these two points signals mastery of the problem.

Find Minimum in Rotated Sorted Array is the gateway to Search in Rotated Sorted Array (LeetCode 33), which adds a target value to find. LeetCode 33 builds directly on the same mid-vs-right comparison to determine which half is sorted, then adds a second check to decide whether the target falls in the sorted half. Mastering LeetCode 153 makes LeetCode 33 straightforward.

The compare-with-right technique is part of a broader family of modified binary search patterns. Problems like Find Peak Element (LeetCode 162) and Search a 2D Matrix (LeetCode 74) use the same principle: find a structural property at mid, use it to eliminate half the space, and maintain a tight invariant about where the answer must lie.

Binary search mastery requires understanding not just the template but the invariant each problem requires. For rotated arrays, the invariant is "minimum is always in the unsorted half." For other binary search problems, identify the analogous invariant first, then the comparison to enforce it follows naturally. Practicing the full binary search family — rotated arrays, peak finding, answer-space binary search — develops this invariant-first thinking.