← all entries
A-031● Day 312026.06.06mediumleetcode #153neetcode150

Find Minimum in Rotated Sorted Array

#array#binary-search
↗ leetcode #153 · find-minimum-in-rotated-sorted-array
01

Problem

· problem
P.031

Find Minimum in Rotated Sorted Array

↗ leetcode #153

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] if it was rotated 4 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. 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
  • · 1 ≤ n ≤ 5000
  • · -5000 ≤ nums[i] ≤ 5000
  • · All elements are unique
  • · Array is sorted and rotated between 1 and n times
// paraphrased summary — see source for full text
examples
example 1input → output
[3,4,5,1,2]
1
example 2input → output
[4,5,6,7,0,1,2]
0
example 3input → output
[11,13,15,17]
11
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Should we return the minimum value itself or its index?
  • ☐
    Do we need to handle the case where the array is not rotated (e.g., [11,13,15,17])?
  • ☐
    Can the array contain duplicate elements?
  • ☐
    Why can't we just use Python's built-in min() function?
  • ☐
    Can we achieve O(log n) with linear scanning?
  • ☐
    In a rotated sorted array, is one half always fully sorted?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize search boundaries and minimum tracker
○
start , end = 0, len(nums) - 1
○
start, end = 1, len(nums) - 2
○
start, end = 0, len(nums)
step 2· Binary search loop condition
○
while start  <  end :
○
while start <= end:
○
while start < end - 1:
step 3· Calculate midpoint and track minimum│ nested
○
mid = start + (end - start ) // 2
○
mid = (start + end) // 2
○
mid = start + (end - start) // 2
curr_min = nums[mid]
step 4· Determine which half contains minimum│ nested
○
if nums[mid] > nums[end]:
○
if nums[mid] > nums[start]:
○
if nums[mid] < nums[end]:
step 5· Move left boundary forward│ │ nested
○
start = mid + 1
○
start = mid
○
start = mid - 1
step 6· Move right boundary backward│ │ nested
○
end = mid - 1
○
end = mid
○
end = mid + 1
step 7· Return final minimum value
○
return min(curr_min,nums[start])
○
return curr_min
○
return nums[start]
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def findMin(self, nums: List[int]) -> int:
3
        start , end = 0, len(nums) - 1
4
        curr_min = float("inf")
5
6
        while start  <  end :
7
            mid = start + (end - start ) // 2
8
            curr_min = min(curr_min,nums[mid])
9
10
            # right has the min
11
            if nums[mid] > nums[end]:
12
                start = mid + 1
13
14
            # left has the  min
15
            else:
16
                end = mid - 1
17
18
        return min(curr_min,nums[start])
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[3,4,5,1,2]
→
1
case 2
[4,5,6,7,0,1,2]
→
0
case 3
[11,13,15,17]
→
11
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.