Find Minimum in Rotated Sorted Array

📋

Problem

Imagine a circularly shifted sorted list of timestamps from a server log, and you need to find the earliest event quickly.

Given an integer array nums sorted in ascending order, rotated at some pivot unknown to you beforehand (e.g., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]), find the minimum element in O(log n) time. You may assume no duplicate exists in the array.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4All integers in nums are unique.nums is rotated at some pivot.

Edge cases: Array of length 1 → returns the single elementArray not rotated (fully sorted) → returns first elementRotation at last element → minimum is last element

</>

IDE

def find_min(nums: list[int]) -> int:public int findMin(int[] nums)int findMin(vector<int>& nums)function findMin(nums)

def find_min(nums):
    # Write your solution here
    pass

class Solution {
    public int findMin(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function findMin(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: nums[0]Always returning first element without checking rotation or pivot.✅ Add binary search to find pivot where nums[mid] > nums[right], then update pointers accordingly.

Wrong: nums[mid]Returning middle element without comparing to right element to find pivot.✅ Compare nums[mid] with nums[right] to decide which half to search next.

Wrong: IndexError or infinite loopIncorrect mid calculation or pointer updates causing out-of-bound access or no progress.✅ Calculate mid as left + (right - left) // 2 and update pointers carefully to avoid infinite loops.

Wrong: TimeoutUsing linear scan instead of binary search for large inputs.✅ Implement binary search approach to achieve O(log n) time complexity.

✓

Test Cases

Focus on handling arrays with minimal or no rotation and single element arrays.

Watch out for subtle binary search boundary errors and greedy traps.

Optimize your solution to O(log n) to handle large inputs efficiently.

t1_01basic

Input{"nums":[3,4,5,1,2]}

Expected1

⏱ Performance - must finish in 2000ms

The array was rotated at index 3, so the minimum element is 1.

💡 Think about how rotation affects the sorted order and where the smallest element lies.

💡 Use modified binary search to find the pivot point where order breaks.

💡 Compare middle element with rightmost to decide which half to search next.

Why it failed: Returned wrong minimum; likely binary search boundaries or mid calculation incorrect. Fix by ensuring mid comparison with right element and adjusting left/right pointers accordingly.

✓ Correctly identified minimum using modified binary search.

t1_02basic

Input{"nums":[4,5,6,7,0,1,2]}

Expected0

⏱ Performance - must finish in 2000ms

The array was rotated at index 4, minimum element is 0.

💡 Check if middle element is greater than rightmost to find pivot.

💡 Binary search pivot detection helps find minimum in O(log n).

💡 Adjust search space based on comparison between mid and right elements.

Why it failed: Incorrect minimum found; likely failed to update search bounds properly when mid > right. Fix by moving left pointer to mid + 1 in that case.

✓ Minimum found correctly using pivot-based binary search.

t2_01edge

Input{"nums":[1]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array returns that element as minimum.

💡 Consider arrays with only one element as a base case.

💡 Binary search should handle left == right scenario gracefully.

💡 Return nums[0] immediately if length is 1 or left == right.

Why it failed: Fails on single element input; likely no base case for length 1. Fix by returning nums[0] if array length is 1 or left == right.

✓ Handles single element arrays correctly.

t2_02edge

Input{"nums":[1,2,3,4,5]}

Expected1

⏱ Performance - must finish in 2000ms

Array not rotated, minimum is first element.

💡 Check if array is already sorted without rotation.

💡 If nums[left] < nums[right], minimum is nums[left].

💡 Add condition to return nums[left] early if array is sorted.

Why it failed: Fails to detect non-rotated array; returns wrong minimum. Fix by adding check if nums[left] < nums[right], then return nums[left].

✓ Correctly returns minimum for non-rotated arrays.

t2_03edge

Input{"nums":[2,3,4,5,1]}

Expected1

⏱ Performance - must finish in 2000ms

Rotation at last element, minimum is last element.

💡 Consider rotation where minimum is at the end of array.

💡 Binary search must correctly identify pivot even if near array end.

💡 Ensure search space updates correctly when mid element is less than right.

Why it failed: Fails when minimum is last element; likely incorrect pointer updates. Fix by adjusting right pointer to mid when nums[mid] < nums[right].

✓ Correctly finds minimum at array end.

t3_01corner

Input{"nums":[2,1]}

Expected1

⏱ Performance - must finish in 2000ms

Small array with two elements rotated; minimum is 1.

💡 Small arrays can expose off-by-one errors in binary search.

💡 Check boundary conditions when left and right pointers are adjacent.

💡 Ensure mid calculation and pointer updates handle small arrays correctly.

Why it failed: Fails on two-element rotated array; off-by-one error in mid or pointer updates. Fix by using mid = left + (right - left) // 2 and careful pointer adjustments.

✓ Handles small rotated arrays correctly.

t3_02corner

Input{"nums":[5,6,7,8,9,1,2,3,4]}

Expected1

⏱ Performance - must finish in 2000ms

Rotation near middle; tests correct pivot detection.

💡 Greedy approach picking mid without comparing to right can fail here.

💡 Always compare nums[mid] with nums[right] to decide search half.

💡 Adjust left or right pointer based on comparison to find pivot.

Why it failed: Fails due to greedy approach ignoring right comparison; returns wrong minimum. Fix by comparing nums[mid] and nums[right] to decide search direction.

✓ Correctly finds minimum despite rotation near middle.

t3_03corner

Input{"nums":[1,2,3,4,5,6,7]}

Expected1

⏱ Performance - must finish in 2000ms

Array fully sorted, no rotation; tests early exit condition.

💡 Check if nums[left] < nums[right] to detect no rotation.

💡 Avoid unnecessary binary search if array is sorted.

💡 Return nums[left] immediately if no rotation detected.

Why it failed: Fails to detect no rotation; performs unnecessary search and returns wrong minimum. Fix by adding early return if nums[left] < nums[right].

✓ Efficiently handles fully sorted arrays.

t4_01performance

Input{"nums":[5001,5002,5003,5004,5005,5006,5007,5008,5009,5010,5011,5012,5013,5014,5015,5016,5017,5018,5019,5020,5021,5022,5023,5024,5025,5026,5027,5028,5029,5030,5031,5032,5033,5034,5035,5036,5037,5038,5039,5040,5041,5042,5043,5044,5045,5046,5047,5048,5049,5050,5051,5052,5053,5054,5055,5056,5057,5058,5059,5060,5061,5062,5063,5064,5065,5066,5067,5068,5069,5070,5071,5072,5073,5074,5075,5076,5077,5078,5079,5080,5081,5082,5083,5084,5085,5086,5087,5088,5089,5090,5091,5092,5093,5094,5095,5096,5097,5098,5099,5100,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]}

Expectednull

⏱ Performance - must finish in 2000ms

Array of length 100 rotated near middle; algorithm must run in O(log n) time within 2 seconds.

💡 Linear scan O(n) will time out for large n.

💡 Use binary search to achieve O(log n) time complexity.

💡 Compare mid and right elements to narrow search space efficiently.

Why it failed: Algorithm timed out due to O(n) linear scan; fix by implementing O(log n) binary search approach.

✓ Algorithm runs within time limits using O(log n) binary search.

Practice

1. Given the following code for finding a peak element, what is the final output when the input array is [1, 3, 2]?

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid + 1]:
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

print(findPeakElement([1, 3, 2]))

easy

A. None of the above

B. 0

C. 2

D. 1

Solution

1. Step 1: Trace first call binarySearch(0, 2)

   mid = (0+2)//2 = 1; nums[1]=3, nums[2]=2; since 3 > 2, recurse binarySearch(0,1)

2. Step 2: Trace second call binarySearch(0, 1)

   mid = (0+1)//2 = 0; nums[0]=1, nums[1]=3; since 1 < 3, recurse binarySearch(1,1)

3. Step 3: Trace third call binarySearch(1, 1)

   low == high, return 1

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Returned index 1 corresponds to peak element 3 [OK]

Hint: Check mid and mid+1 comparison carefully [OK]

Common Mistakes:

• Returning mid instead of low/high
• Off-by-one in mid calculation
• Confusing which half to recurse

2. Consider the following code snippet that searches for a target in a 2D matrix using binary search treating it as a 1D array. Given the matrix = [[1,4],[6,8]] and target = 6, what is the value of mid and the corresponding row, col during the first iteration of the while loop?

easy

A. mid = 1, row = 0, col = 1

B. mid = 2, row = 1, col = 0

C. mid = 0, row = 0, col = 0

D. mid = 3, row = 1, col = 1

Solution

1. Step 1: Calculate initial boundaries and mid

   m=2, n=2, left=0, right=3, so mid=(0+3)//2=1.

2. Step 2: Map mid to 2D indices

   row, col = divmod(1, 2) -> row=0, col=1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   mid=1 corresponds to matrix[0][1]=4, correct mapping [OK]

Hint: mid index maps to row,col via divmod(mid, n) [OK]

Common Mistakes:

• Off-by-one in mid calculation
• Confusing row and col indices
• Using mid as direct index without divmod

3. You need to find the largest integer r such that r * r ≤ x for a given non-negative integer x. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Sorting all numbers and selecting the closest square root

B. Greedy approach incrementing from 0 until r * r > x

C. Dynamic programming to build up solutions for all numbers up to x

D. Modified binary search narrowing down the range of possible roots

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the integer square root efficiently without checking all numbers linearly.

2. Step 2: Identify the suitable algorithm

   Modified binary search efficiently narrows down the search space by comparing mid*mid with x, guaranteeing logarithmic time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search halves the search space each iteration [OK]

Hint: Binary search efficiently narrows down integer roots [OK]

Common Mistakes:

• Assuming greedy linear search is efficient
• Confusing DP with this problem
• Using sorting which is irrelevant

4. What is the space complexity of the recursive binary search algorithm on an array of size n, considering the recursion call stack?

medium

A. O(log n) due to recursion call stack depth proportional to halving steps

B. O(1) constant space because no extra data structures are used

C. O(n) because each recursive call creates a new subarray copy

D. O(n log n) combining recursion depth and array size

Solution

1. Step 1: Identify recursion depth

   Binary search halves the search space each call, so max recursion depth is O(log n).

2. Step 2: Analyze space usage per call

   Each call uses constant space; no new arrays are created, so total space is O(log n) for the call stack.

3. Step 3: Clarify space complexity definition

   Since no additional data structures are created and only a fixed number of variables are used per call, the extra space excluding call stack is O(1).

4. Step 4: Distinguish between auxiliary space and call stack

   Auxiliary space is O(1), but total space including call stack is O(log n).

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Recursive calls stack up to log n depth, no extra arrays [OK]

Hint: Recursion depth = log n -> space O(log n) [OK]

Common Mistakes:

• Assuming O(1) ignoring recursion stack
• Thinking new arrays are created each call
• Confusing time and space complexity

5. Suppose the problem is modified so that the input array arr can contain negative numbers and zero, and you still need to find the kth positive missing number (positive integers missing from the array). Which of the following changes to the optimal binary search approach is correct?

hard

A. Modify the missing count calculation to be arr[mid] - (mid + 1) + offset, where offset accounts for negative numbers.

B. No change needed; the existing binary search works as is because it only depends on indices and values.

C. Filter out non-positive numbers first, then apply the binary search approach on the filtered positive array.

D. Use the brute force linear scan approach instead, as binary search cannot handle negative numbers.

Solution

1. Step 1: Understand the problem modification

   Negative numbers and zero do not affect the count of missing positive integers, but they disrupt the assumption that arr contains only positive sorted numbers.

2. Step 2: Adjust the input for binary search

   Filtering out non-positive numbers creates a sorted array of positive integers, restoring the problem's original assumptions and enabling correct binary search.

3. Step 3: Reject other options

   No change (B) fails because negative numbers break missing count logic; offset (C) is ambiguous and error-prone; brute force (D) is inefficient and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Filtering preserves correctness and efficiency [OK]

Hint: Filter positives before binary search [OK]

Common Mistakes:

• Assuming binary search works without filtering
• Trying to adjust missing count with offsets
• Switching to brute force unnecessarily