LeetCode · #153

Find Minimum in Rotated Sorted Array Solution

Given a rotated sorted array of unique elements, find the minimum element in O(log n).

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #153

🏗️

Pattern

Binary Search — find pivot

A sorted array of unique elements was rotated between 1 and n times. Find the minimum element. The original array was sorted in ascending order.

Example

 Input: nums = [3,4,5,1,2]
Output: 1 // Originally [1,2,3,4,5], rotated 3 times 

Constraints

 • n == nums.length • 1 ≤ n ≤ 5000 • All elements unique • nums was sorted ascending then rotated 

Section Two · Approach 1

Linear Scan — O(n)

Scan the array and track the minimum. Or find the first element smaller than its predecessor — that's the rotation point.

Problem: O(n). Binary search on the rotation structure gives O(log n) — compare mid to the right boundary to decide which half contains the minimum.

Metric	Value
Time	O(n)
Space	O(1)

Section Three · Approach 2

Binary Search — O(log n)

Compare nums[mid] to nums[right]. If nums[mid] > nums[right], the minimum is in the right half (the rotation break is there). Otherwise, it's in the left half (including mid).

💡 Mental model: Imagine a hill with a cliff — the array ascends, then drops to the minimum. If you're standing on the left slope (mid > right), the cliff is to your right. If you're on the right slope (mid ≤ right), the cliff is to your left or you're already past it. Walk toward the cliff.

Algorithm

Step 1: left = 0, right = n - 1.
Step 2: While left < right:
Step 3: If nums[mid] > nums[right] → minimum is in [mid+1, right] → left = mid + 1.
Step 4: Else → minimum is in [left, mid] → right = mid.
Step 5: Return nums[left].

🎯 Why compare to right, not left?:

Comparing to left is ambiguous: nums[left] ≤ nums[mid] doesn't tell you if the minimum is left or right (could be an unrotated array).
Comparing to right is definitive: if nums[mid] > nums[right], there must be a drop between mid and right.

Section Four · Trace

Visual Walkthrough

Trace through nums = [3, 4, 5, 1, 2]:

Binary Search — find the rotation point (minimum)

Section Five · Implementation

Code — Java & Python

Java — Binary Search

 class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right])
                left = mid + 1; // min is in right half else
right = mid; // min is in left half (incl. mid)
}
return nums[left];
    }
}

Python — Binary Search

 class Solution:
def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1 while left < right:
            mid = (left + right) // 2 if nums[mid] > nums[right]:
                left = mid + 1 else:
                right = mid
return nums[left]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Linear Scan	O(n)	O(1)	Simple but slow
Binary Search ← optimal	O(log n)	O(1)	Compare mid to right boundary

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Not rotated	`[1, 2, 3, 4]`	nums[mid] always ≤ nums[right] → right converges to 0. Min = nums[0].
Single element	`[1]`	L==R immediately → return nums[0].
Two elements	`[2, 1]`	mid=0, nums[0]=2 > nums[1]=1 → L=1. Return nums[1]=1.
Fully rotated	`[2,3,4,5,1]`	Min at last position. Binary search converges there.

⚠ Common Mistake: Using left ≤ right instead of left < right. This is a "find boundary" search, not "find exact target." With ≤, the loop runs one extra time and can cause infinite loops when right = mid and left == right.

← Back to Binary Search problems

LearningTree

LC 153 · Find Minimum in Rotated Sorted Array — Solution & Explanation | DSA Guide