LeetCode 153 - Find Minimum in Rotated Sorted Array

LeetCode Problem 153

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

This problem asks us to find the smallest element in a sorted array that has been rotated some number of times.

A sorted array in ascending order might originally look like this:

[1,2,3,4,5,6,7]

After rotation, it could become:

[4,5,6,7,1,2,3]

or remain unchanged:

[1,2,3,4,5,6,7]

The important observation is that the array was originally sorted, and after rotation it still preserves a specific structure. There are effectively two sorted portions, and the minimum value marks the point where the rotation occurred.

The input is an integer array nums containing unique values, meaning no duplicates exist. The array is guaranteed to have been sorted in ascending order before rotation. The output should be the minimum element in the array.

The constraint that matters most is the requirement to solve the problem in O(log n) time. Since a linear scan through the array takes O(n) time, we immediately know that a straightforward iteration is not acceptable as the optimal solution. The sorted nature of the input strongly suggests using binary search, since binary search naturally achieves logarithmic performance.

The constraints also tell us that:

• The array size ranges from 1 to 5000.
• Values are unique, which simplifies comparisons because there is never ambiguity between equal elements.
• The array is always valid and rotated between 1 and n times.

Several edge cases deserve attention:

• A single-element array such as [5], where the answer is trivially the only element.
• An already sorted array such as [11,13,15,17], where no effective rotation exists and the first element is already the minimum.
• A rotation near the beginning or end of the array, such as [5,1,2,3,4] or [2,3,4,5,1].
• Very small arrays like [2,1], where off-by-one mistakes in binary search are common.

Because the array contains unique values and always follows the rotated sorted structure, we can rely on ordering relationships to eliminate half of the search space at every step.

Approaches

Brute Force Approach

The most direct solution is to scan through the entire array and keep track of the smallest value encountered.

We initialize a variable to the first element and compare every number in the array against it. Whenever we encounter a smaller number, we update our minimum.

This works because checking every element guarantees that we eventually see the smallest value.

However, this approach takes O(n) time because every element may need to be examined. Since the problem explicitly requires an O(log n) solution, brute force is not sufficient.

Optimal Approach, Binary Search

The key insight is that the array is mostly sorted, except for the rotation point.

In a normal sorted array:

[1,2,3,4,5]

the smallest element is always at index 0.

In a rotated array:

[4,5,6,7,1,2,3]

the minimum appears exactly where the ordering breaks.

The important observation is this:

• If the middle element is greater than the rightmost element, the minimum must lie in the right half.
• Otherwise, the minimum lies in the left half, including the middle element itself.

For example:

[4,5,6,7,1,2,3]

If mid = 7 and right = 3:

7 > 3

This tells us the minimum cannot be on the left side, because the left portion is still increasing. Therefore, we search the right half.

Binary search works here because each comparison eliminates half of the search space, producing O(log n) performance.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scan entire array to find minimum
Optimal	O(log n)	O(1)	Binary search using sorted-region properties

Algorithm Walkthrough

1. Initialize two pointers, left and right, to the beginning and end of the array.

These pointers define the current search space where the minimum might exist. 2. Continue searching while left < right.

When both pointers meet, we know only one candidate remains, which must be the minimum. 3. Compute the middle index:

mid = left + (right - left) // 2

This safely finds the midpoint and avoids overflow concerns in languages like Go. 4. Compare nums[mid] with nums[right].

This comparison tells us which side contains the rotation point.

• If nums[mid] > nums[right], the minimum must be in the right half.

Since mid itself cannot be the minimum, move:

left = mid + 1

• Otherwise, the minimum lies in the left half, including mid.

Move:

right = mid

We keep mid because it could still be the smallest value. 5. Repeat until left == right.

At this point, both pointers identify the minimum element. 6. Return nums[left].

Why it works

The algorithm maintains the invariant that the minimum element is always inside the search range [left, right].

When nums[mid] > nums[right], the left side up to mid is properly sorted and larger than the right portion, meaning the rotation point must be to the right.

When nums[mid] <= nums[right], the right half is sorted, so the minimum cannot be beyond mid, and we safely keep searching left.

Since each iteration removes half the remaining range while preserving the minimum inside the search interval, the algorithm always converges to the correct answer.

Python Solution

from typing import List

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

        while left < right:
            mid = left + (right - left) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]

The implementation begins by defining the search boundaries with left and right.

The while left < right loop continues shrinking the search interval until only one element remains.

At each iteration, we compute mid and compare nums[mid] with nums[right].

If nums[mid] is greater than nums[right], the minimum must lie to the right of mid, so we move left forward.

Otherwise, the minimum lies at mid or to its left, so we move right to mid.

Eventually, the pointers converge to the minimum element, which we return.

This implementation directly follows the algorithm described earlier and satisfies the required O(log n) runtime.

Go Solution

func findMin(nums []int) int {
	left := 0
	right := 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]
}

The Go implementation follows exactly the same binary search logic as the Python version.

One small implementation detail is the midpoint calculation:

mid := left + (right-left)/2

This form avoids potential integer overflow, which is considered good practice in Go and many other languages.

Since the problem guarantees at least one element in the array, there is no need for additional empty-slice handling. Go slices are used directly, and indexing semantics are straightforward.

Worked Examples

Example 1

Input:

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

Iteration	left	right	mid	nums[mid]	nums[right]	Action
1	0	4	2	5	2	5 > 2, search right half
2	3	4	3	1	2	1 <= 2, search left half
End	3	3	-	-	-	Return nums[3] = 1

Answer:

1

Example 2

Input:

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

Iteration	left	right	mid	nums[mid]	nums[right]	Action
1	0	6	3	7	2	7 > 2, move right
2	4	6	5	1	2	1 <= 2, search left
3	4	5	4	0	1	0 <= 1, search left
End	4	4	-	-	-	Return nums[4] = 0

Answer:

0

Example 3

Input:

nums = [11,13,15,17]

Iteration	left	right	mid	nums[mid]	nums[right]	Action
1	0	3	1	13	17	13 <= 17, search left
2	0	1	0	11	13	11 <= 13, search left
End	0	0	-	-	-	Return nums[0] = 11

Answer:

11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search halves the search space at every iteration
Space	O(1)	Only a few variables are used regardless of input size

The logarithmic runtime comes from repeatedly cutting the search interval in half. Since only constant extra memory is used for pointers and the midpoint variable, the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.findMin([3, 4, 5, 1, 2]) == 1  # rotated in middle
assert solution.findMin([4, 5, 6, 7, 0, 1, 2]) == 0  # larger rotation
assert solution.findMin([11, 13, 15, 17]) == 11  # already sorted

assert solution.findMin([1]) == 1  # single element
assert solution.findMin([2, 1]) == 1  # two elements rotated
assert solution.findMin([1, 2]) == 1  # two elements sorted

assert solution.findMin([5, 1, 2, 3, 4]) == 1  # rotation near beginning
assert solution.findMin([2, 3, 4, 5, 1]) == 1  # rotation near end

assert solution.findMin([-4, -3, -2, -1, -10]) == -10  # negative values
assert solution.findMin([30, 40, 50, 10, 20]) == 10  # generic rotation
assert solution.findMin([6, 7, 1, 2, 3, 4, 5]) == 1  # pivot near center

Test	Why
[3,4,5,1,2]	Standard rotated array
[4,5,6,7,0,1,2]	Larger array with pivot near middle
[11,13,15,17]	Already sorted input
[1]	Minimum size constraint
[2,1]	Small rotated array
[1,2]	Small sorted array
[5,1,2,3,4]	Rotation near front
[2,3,4,5,1]	Rotation near end
[-4,-3,-2,-1,-10]	Handles negative values
[30,40,50,10,20]	Typical rotated ordering
[6,7,1,2,3,4,5]	Pivot near center

Edge Cases

Single Element Array

An input like:

[7]

can be a source of bugs because binary search loops often assume multiple elements exist. In this case, left == right immediately, so the loop never executes. The implementation correctly returns nums[left], which is the only element.

Already Sorted Array

An array such as:

[11,13,15,17]

contains no meaningful rotation point. A naive implementation might incorrectly assume rotation always exists and fail to return the first element. In our solution, comparisons consistently move right toward left, eventually converging at index 0, which correctly contains the minimum.

Rotation at the Boundary

Cases like:

[5,1,2,3,4]

or

[2,3,4,5,1]

are common sources of off-by-one mistakes. The pivot occurs at the beginning or end, making incorrect midpoint updates easy to introduce. Our implementation carefully preserves mid when necessary by using:

right = mid

instead of:

right = mid - 1

This ensures that a valid minimum candidate is never accidentally discarded.