How do you solve Find Minimum in Rotated Sorted Array?

Use a binary search with pointers l and r. If nums[l] < nums[r], the subarray is sorted and nums[l] is the minimum. Otherwise, calculate mid m, update the result with nums[m], and decide which half to search next based on the comparison between nums[m] and nums[l]. This approach guarantees O(log n) time complexity.

Find Minimum in Rotated Sorted Array

Q: What is the time complexity of Find Minimum in Rotated Sorted Array?

O(log n). Each iteration halves the search space by discarding one half of the array based on comparisons, leading to logarithmic time complexity.

Q: What pattern does Find Minimum in Rotated Sorted Array use?

The Pattern: Modified Binary Search (Rotated Sorted Array) The Heuristic: When searching in a rotated sorted array, use the property that one half is always sorted to discard half the search space by comparing boundary and middle elements, enabling O(log n) search for the minimum.

Medium Modified Binary Search

Problem

Given an array nums that is sorted in ascending order and is rotated at an unknown pivot, return the minimum element in nums. You may assume no duplicate exists in the array.

1 ≤ nums.length ≤ 5000
−5000 ≤ nums[i] ≤ 5000
All integers of nums are unique
nums is sorted and rotated between 1 and nums.length times

Example

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

Output: 0

A brute-force approach would scan the entire array to find the minimum, which is inefficient for large inputs. The optimal approach uses a modified binary search to exploit the rotated sorted property. Starting with pointers at the array's ends, the algorithm compares values to determine which half contains the minimum. For example, at the first iteration, the algorithm compares nums[l]=4 and nums[r]=2. Since nums[l] > nums[r], the minimum must be in the right half. It calculates the middle index m=3, nums[m]=7, updates the result to min(4,7)=4, and moves the left pointer to m+1=4. The process repeats until the minimum is found at index 4 with value 0.

Approach

Straightforward Solution

A linear scan through the array to find the minimum element, which takes O(n) time and is inefficient for large arrays.

Core Observation

The rotated sorted array consists of two sorted subarrays. The minimum element is the only element where the previous element is greater, or it is the smallest element in the array. The key property is that if nums[l] < nums[r], the subarray is already sorted, and nums[l] is the minimum.

Path to Optimal

Preview

The key recognition signals are 'rotated sorted array' and 'find minimum' which indicate a modified binary search. The algorithm exploits the fact that one half of the array is always sorted…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a binary search with pointers l and r. If nums[l] < nums[r], the subarray is sorted and nums[l] is the minimum…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n)

Each iteration halves the search space by discarding one half of the array based on comparisons, leading to logarithmic time complexity.

Space

O(1)

Only a fixed number of variables (pointers and result) are used, requiring constant auxiliary space.

Pattern Spotlight

Modified Binary Search (Rotated Sorted Array)

When searching in a rotated sorted array, use the property that one half is always sorted to discard half the search space by comparing boundary and middle elements, enabling O(log n) search for the minimum.

Solution

Python

1class Solution:
  def findMin(self, nums: list[int]) -> int:
      res = nums[0]
      l, r = 0, len(nums) - 1
5
      while l <= r:
          if nums[l] < nums[r]:
              res = min(res, nums[l])
              break
          
          m = (l + r) // 2
          res = min(res, nums[m])
          if nums[m] >= nums[l]:
              l = m + 1
          else:
              r = m - 1
      
      return res

Step-by-Step Solution

Initialize Result and Search Boundaries

3res = nums[0]
4l, r = 0, len(nums) - 1

Objective

To set up the initial minimum candidate and pointers for the binary search over the rotated array.

Key Insight

Starting with res as nums[0] ensures the algorithm always has a baseline minimum to compare against. Initializing pointers l and r at the array boundaries sets the stage for a binary search that progressively narrows the search space to find the minimum element.

Interview Quick-Check

Core Logic

Initialize res with nums[0] to track the minimum found so far during the binary search.

State & Boundaries

Set l and r to the start and end indices of the array to cover the entire search space initially.

Iteratively Narrow Search Space Using Modified Binary Search

To repeatedly halve the search space by comparing boundary and middle elements, updating the minimum candidate accordingly.

Return the Minimum Element Found

To output the smallest element found after the binary search completes.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 7 Critical

if nums[l] < nums[r]:

Check if the current subarray is already sorted.

If nums[l] < nums[r], the subarray is sorted and nums[l] is the minimum, allowing early termination and optimization.

Line 12 Critical

res = min(res, nums[m])

Update the minimum result with the middle element.

Including nums[m] in the minimum check ensures the algorithm does not miss the minimum if it lies at mid.

Line 13 Critical

if nums[m] >= nums[l]:

Check if the middle element is greater than or equal to the left boundary element.

If nums[m] >= nums[l], the left half is sorted, so the minimum must be in the right half, guiding the search direction.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why does comparing nums[m] with nums[l] allow us to discard half of the search space?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find Minimum in Rotated Sorted Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find Minimum in Rotated Sorted Array drill

or drill a free problem

1	`class Solution:`
2	`def findMin(self, nums: list[int]) -> int:`
3	`res = nums[0]`
4	`l, r = 0, len(nums) - 1`
5
6	`while l <= r:`
7	`if nums[l] < nums[r]:`
8	`res = min(res, nums[l])`
9	`break`
10
11	`m = (l + r) // 2`
12	`res = min(res, nums[m])`
13	`if nums[m] >= nums[l]:`
14	`l = m + 1`
15	`else:`
16	`r = m - 1`
17
18	`return res`