Find Minimum in Rotated Array II (With Duplicates)

📋

Problem

Imagine you have a circularly shifted sorted list of timestamps from a sensor, but some readings are duplicated due to noise. You need to quickly find the earliest timestamp to synchronize data streams.

Given an integer array nums sorted in non-decreasing order, which is rotated at an unknown pivot, possibly containing duplicates, return the minimum element of this array. You must minimize the number of operations.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4nums is rotated at some pivot unknown to you beforehandDuplicates are allowed

Edge cases: Array with all identical elements → minimum is that elementArray rotated at last element → minimum is first elementArray with two elements, rotated → minimum is smaller 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: 2Not shrinking high pointer when nums[mid] == nums[high], causing incorrect minimum selection.✅ Add condition to decrement high by one when nums[mid] == nums[high].

Wrong: 4Incorrectly choosing left half when nums[mid] > nums[high] without proper checks.✅ If nums[mid] > nums[high], search right half; else left half.

Wrong: 3Greedy approach picking half incorrectly when duplicates present, missing pivot.✅ When nums[mid] == nums[high], shrink high pointer by one instead of choosing half.

Wrong: IndexError or infinite loopMissing base case for single element or all identical elements causing infinite loop.✅ Add base case to return nums[0] if length is 1; shrink high pointer carefully for duplicates.

✓

Test Cases

Focus on handling small inputs and uniform arrays correctly to pass edge cases.

Avoid greedy assumptions and handle duplicates carefully to pass corner cases.

Optimize your solution to handle large inputs efficiently and avoid TLE.

t1_01basic

Input[2,2,2,0,1]

Expected0

⏱ Performance - must finish in 2000ms

The array was rotated and contains duplicates; the minimum element is 0.

💡 Consider how binary search can be adapted to handle duplicates in a rotated array.

💡 Use a modified binary search that shrinks the high pointer when duplicates are encountered.

💡 When nums[mid] == nums[high], reduce high by one to shrink the search space.

Why it failed: Incorrect minimum found due to not handling duplicates properly; fix by shrinking high pointer when nums[mid] == nums[high].

✓ Correctly handles duplicates and finds minimum using modified binary search.

t1_02basic

Input[4,5,6,7,0,1,2]

Expected0

⏱ Performance - must finish in 2000ms

Standard rotated array without duplicates; minimum element is 0 at pivot.

💡 Binary search can find the pivot point where order breaks.

💡 Compare mid element with high to decide which half to search.

💡 If nums[mid] > nums[high], search right half; else left half.

Why it failed: Failed to correctly identify pivot in rotated array without duplicates; fix by comparing nums[mid] and nums[high] properly.

✓ Correctly finds minimum in rotated array without duplicates.

t2_01edge

Input[1]

Expected1

⏱ Performance - must finish in 2000ms

Single element array; minimum is the only element.

💡 Check how your code handles arrays with only one element.

💡 Edge cases often fail due to missing base conditions.

💡 Return nums[0] immediately if array length is 1.

Why it failed: Fails on single element input due to missing base case; fix by returning nums[0] when length is 1.

✓ Handles single element arrays correctly.

t2_02edge

Input[2,2,2,2,2]

Expected2

⏱ Performance - must finish in 2000ms

All elements identical; minimum is that element.

💡 Duplicates can cause high pointer shrinking to degrade to linear scan.

💡 Ensure your algorithm handles all identical elements gracefully.

💡 If nums[mid] == nums[high], decrement high to shrink search space.

Why it failed: Fails on all identical elements due to infinite loop or incorrect shrinking; fix by decrementing high when nums[mid] == nums[high].

✓ Correctly handles arrays with all identical elements.

t2_03edge

Input[1,2]

Expected1

⏱ Performance - must finish in 2000ms

Two elements, not rotated; minimum is first element.

💡 Small arrays can be tricky; verify your binary search boundaries.

💡 Check if your code handles arrays where rotation is zero.

💡 If nums[low] < nums[high], return nums[low] immediately.

Why it failed: Fails on two-element non-rotated array by not checking if array is already sorted; fix by returning nums[low] if nums[low] < nums[high].

✓ Correctly handles two-element non-rotated arrays.

t3_01corner

Input[10,1,10,10,10]

Expected1

⏱ Performance - must finish in 2000ms

Duplicates with pivot in middle; tests correct shrinking of high pointer.

💡 Duplicates equal to nums[high] can hide the pivot.

💡 Shrinking high pointer when nums[mid] == nums[high] avoids missing pivot.

💡 Avoid skipping the pivot by only decrementing high by one when duplicates equal.

Why it failed: Fails due to skipping pivot when nums[mid] == nums[high] and high decremented too aggressively; fix by decrementing high by one only.

✓ Correctly handles duplicates hiding the pivot.

t3_02corner

Input[3,3,1,3]

Expected1

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack style and binary search; must not assume unique elements.

💡 Duplicates require careful comparison, not just unique pivot detection.

💡 Do not assume strictly increasing or unique elements in binary search.

💡 Handle nums[mid] == nums[high] by shrinking high pointer cautiously.

Why it failed: Fails by assuming unique elements or strict ordering; fix by handling duplicates with high pointer shrinking.

✓ Handles duplicates correctly without unique element assumptions.

t3_03corner

Input[2,2,2,3,1,2]

Expected1

⏱ Performance - must finish in 2000ms

Greedy trap test: naive binary search picking wrong half due to duplicates.

💡 Greedy approach picking half based on nums[mid] < nums[high] can fail with duplicates.

💡 When nums[mid] == nums[high], shrink high pointer instead of choosing half.

💡 Avoid greedy elimination; shrink search space conservatively.

Why it failed: Fails greedy trap by choosing wrong half when nums[mid] == nums[high]; fix by shrinking high pointer by one.

✓ Avoids greedy trap and finds minimum correctly.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100000 tests O(n) worst-case complexity due to duplicates; must complete within 2 seconds.

💡 Worst-case complexity can degrade to O(n) due to duplicates.

💡 Binary search with shrinking high pointer is average O(log n) but worst O(n).

💡 Optimize by early exit if subarray is sorted.

Why it failed: TLE due to O(n) worst-case complexity when many duplicates; fix by implementing early exit when subarray is sorted.

✓ Algorithm runs within time limit confirming expected complexity.

Practice

1. You need to ship packages within a given number of days. Each package has a weight, and you must ship packages in order without splitting any package. You want to find the minimum ship capacity to ship all packages within the deadline. Which algorithmic approach guarantees finding the optimal ship capacity efficiently?

easy

A. Greedy approach that assigns packages to days until capacity is reached, then moves to next day without binary search

B. Dynamic programming to find the minimum capacity by exploring all subsets of packages and days

C. Sorting packages and using a two-pointer technique to assign packages to days

D. Binary search on the answer space (capacity) combined with a feasibility check to verify if shipping within days is possible

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a minimum capacity that allows shipping all packages in order within a fixed number of days.

2. Step 2: Recognize the pattern

   Binary searching the capacity (answer space) and checking feasibility is the optimal approach because capacity ranges between max package weight and sum of all weights, and feasibility can be checked in linear time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search on answer space is classic for optimization with feasibility checks [OK]

Hint: Binary search on capacity range solves this optimally [OK]

Common Mistakes:

• Thinking greedy alone finds minimal capacity
• Confusing DP with subset sums
• Using two pointers without sorting relevance

2. Given the following code and input nums = [2, 4, 4, 6] and target = 4, what is the final returned value?

easy

A. [1, 2]

B. [2, 3]

C. [0, 1]

D. [-1, -1]

Solution

1. Step 1: Trace binary search to find any occurrence of 4

   Initial left=0, right=3, mid=1, nums[1]=4 matches target, found=1.

2. Step 2: Expand to find leftmost and rightmost indices

   Start=1, check left: nums[0]=2 !=4 stop; end=1, check right: nums[2]=4 matches, end=2; nums[3]=6 stop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Positions of 4 are indices 1 and 2 [OK]

Hint: Break binary search on first found, then expand boundaries [OK]

Common Mistakes:

• Off-by-one errors expanding boundaries
• Returning found index only
• Confusing indices with values

3. 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

4. The following code attempts to find the median of two sorted arrays using binary search on the smaller array. Identify the line containing the subtle bug that can cause incorrect median calculation for even total length arrays.

medium

A. Line: if (m + n) % 2 == 0: return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2

B. Line: if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1

C. Line: partitionY = (m + n) // 2 - partitionX

D. Line: while low <= high:

Solution

1. Step 1: Understand partition calculation

   partitionY must be total left half minus partitionX to split arrays correctly.

2. Step 2: Identify off-by-one bug

   Using (m + n) // 2 instead of (m + n + 1) // 2 causes incorrect partition when total length is odd, leading to wrong median.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Partition calculation off-by-one breaks median correctness [OK]

Hint: Partition indices must sum to half total length exactly, using (m+n+1)//2 for correct odd/even handling [OK]

Common Mistakes:

• Swapping arrays incorrectly
• Wrong median formula for even length
• Loop boundary off-by-one

5. Suppose the matrix rows are sorted but columns are not guaranteed to be sorted. Which of the following approaches correctly finds the target value efficiently?

hard

A. Use the staircase search starting from the top-right corner.

B. Use a brute force nested loop to check every element.

C. Perform binary search on each row independently.

D. Sort each column first, then apply staircase search.

Solution

1. Step 1: Understand matrix constraints

   Only rows are sorted; columns are unsorted, so staircase search assumptions fail.

2. Step 2: Evaluate approaches

   Binary search on rows works but columns unsorted means target could be anywhere in columns; brute force guarantees correctness.

3. Step 3: Consider sorting columns

   Sorting columns is expensive and changes matrix; not practical for search.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Brute force is correct though less efficient; others rely on column sorting [OK]

Hint: Without column sorting, staircase search fails [OK]

Common Mistakes:

• Assuming staircase search works with only row sorting
• Thinking sorting columns is cheap
• Believing binary search on rows suffices