153. Find Minimum in Rotated Sorted Array

Quick Identifier

• Topic: binary-search
• Pattern: Binary Search (Rotation / pivot)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: High
• LeetCode: 153

Quick Sights

• Time Complexity: O(log n) from the optimal approach.
• Space Complexity: O(1) from the optimal approach.
• Core Mechanism: Given a sorted array rotated once around an unknown pivot (all distinct), return the minimum element in O(log n) time.

Concept Explanation

Given a sorted array rotated once around an unknown pivot (all distinct), return the minimum element in O(log n) time.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

• Rotated sorted array, distinct values
• Minimum / pivot / “how many times rotated”
• Compare mid to right to decide which half contains the minimum

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — O(n) time / O(1) space — linear scan for minimum.
• Better — not applicable beyond BS.
• Optimal — O(log n) time / O(1) space — if nums[mid] > nums[right], minimum is right of mid; else left half including mid.

Optimal Solution

Go

func findMin(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] > nums[right] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return nums[left]
}

JavaScript

function findMin(nums) {
	let left = 0;
	let right = nums.length - 1;
	while (left < right) {
		const mid = left + Math.floor((right - left) / 2);
		if (nums[mid] > nums[right]) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	return nums[left];
}

Walkthrough

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

Stop at index 3, value 1. Invariant: minimum remains inside [left, right].

Edge Cases

• Not rotated at all (full ascending) — answer is nums[0].
• Length 1.
• Two elements — smaller one is min.

Pitfalls

• Comparing only to nums[left] — ambiguous with duplicates removed here but wrong instinct for variants.
• Using <= wrong with duplicate-inclusive variants (use problem 154 logic instead).

Similar Problems

• 33. Search in Rotated Sorted Array — adds target test inside partitions.
• 162. Find Peak Element — compare neighbors to shrink side.
• 704. Binary Search — baseline halving without rotation.

Variants

• Allow duplicates — may degrade to O(n) worst case; compare three-way with left/mid/right.
• Find rotation count — index of minimum.

Mind-Map Tags

#binary-search #rotated-array #pivot #compare-to-right