Find Minimum in Rotated Array II (With Duplicates)

🎯

Find Minimum in Rotated Array II (With Duplicates)

hardBINARY_SEARCHAmazonGoogle

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.

💡 This problem is a variant of binary search on a rotated sorted array but complicated by duplicates. Beginners often struggle because duplicates can hide the pivot point, making it tricky to decide which half to discard.

📋

Problem Statement

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

💡

Example

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

Output0

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

Input"[1,3,5]"

Output1

The array is not rotated; the minimum is the first element.

• Array with all identical elements → minimum is that element
• Array rotated at last element → minimum is first element
• Array with two elements, rotated → minimum is smaller element
• Array not rotated at all → minimum is first element

⚠️

Common Mistakes

Not handling duplicates by shrinking high pointer

Algorithm may get stuck in infinite loop or return incorrect minimum

✅ Add else case to decrement high when nums[mid] == nums[high]

Using mid = (low + high) / 2 without floor or integer division

May cause floating point errors or infinite loops in some languages

✅ Use integer division or floor to get valid mid index

Returning nums[mid] instead of nums[low] after loop ends

May return wrong element as minimum

✅ Return nums[low] because low points to minimum after convergence

Not checking if subarray is already sorted for early exit

Unnecessary binary search steps, slower performance

✅ Add check if nums[low] < nums[high] to return early

🧠

Brute Force (Linear Scan)

💡 This approach exists to establish a baseline and ensure understanding of the problem. It’s simple but inefficient, helping beginners grasp the problem before optimizing.

Intuition

Since the array is rotated, the minimum element is the only element where the previous element is greater. Without any optimization, we can scan the entire array to find this point.

Algorithm

1. Initialize min_val as the first element.
2. Iterate through the array from the second element to the end.
3. Update min_val if the current element is smaller.
4. Return min_val after the loop ends.

💡 The algorithm is straightforward but requires checking every element, which is inefficient for large arrays.

</>

Code

def find_min(nums):
    min_val = nums[0]
    for num in nums[1:]:
        if num < min_val:
            min_val = num
    return min_val

# Driver code
if __name__ == '__main__':
    arr = [2,2,2,0,1]
    print(find_min(arr))  # Output: 0

Line Notes

min_val = nums[0]Initialize min_val to first element to have a baseline for comparison

for num in nums[1:]Iterate through all elements starting from second to check for smaller values

if num < min_valUpdate min_val whenever a smaller element is found

return min_valReturn the smallest element found after full traversal

public class Solution {
    public static int findMin(int[] nums) {
        int minVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < minVal) {
                minVal = nums[i];
            }
        }
        return minVal;
    }

    public static void main(String[] args) {
        int[] arr = {2,2,2,0,1};
        System.out.println(findMin(arr)); // Output: 0
    }
}

Line Notes

int minVal = nums[0];Set initial minimum to first element for comparison

for (int i = 1; i < nums.length; i++)Loop through array starting from second element

if (nums[i] < minVal)Update minVal if current element is smaller

return minVal;Return the minimum value found after full iteration

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int minVal = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < minVal) {
            minVal = nums[i];
        }
    }
    return minVal;
}

int main() {
    vector<int> arr = {2,2,2,0,1};
    cout << findMin(arr) << endl; // Output: 0
    return 0;
}

Line Notes

int minVal = nums[0];Initialize minVal with first element to start comparisons

for (int i = 1; i < nums.size(); i++)Traverse the array from second element onwards

if (nums[i] < minVal)Update minVal if a smaller element is found

return minVal;Return the smallest element after full traversal

function findMin(nums) {
    let minVal = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < minVal) {
            minVal = nums[i];
        }
    }
    return minVal;
}

// Test
console.log(findMin([2,2,2,0,1])); // Output: 0

Line Notes

let minVal = nums[0];Initialize minVal to first element for baseline comparison

for (let i = 1; i < nums.length; i++)Loop through array starting from second element

if (nums[i] < minVal)Update minVal if current element is smaller

return minVal;Return the minimum value found after checking all elements

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan through all n elements once to find the minimum, so time is linear. Space is constant as no extra storage is needed.

💡 For n=100,000 elements, this means checking each element once, which can be slow compared to binary search.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays, motivating the need for binary search optimization.

🧠

Modified Binary Search (Handle Duplicates by Shrinking High)

💡 This approach improves efficiency by using binary search principles but carefully handles duplicates that can obscure the pivot point.

Intuition

If the middle element is greater than the high element, the minimum lies to the right. If less, it lies to the left. If equal, we cannot decide, so we shrink the high pointer by one to reduce search space.

Algorithm

1. Initialize low and high pointers at array ends.
2. While low < high:
3. Calculate mid index.
4. If nums[mid] > nums[high], move low to mid + 1.
5. Else if nums[mid] < nums[high], move high to mid.
6. Else (nums[mid] == nums[high]), decrement high by 1.
7. Return nums[low] as minimum.

💡 The tricky part is handling duplicates by shrinking high when equality occurs, ensuring progress without missing the minimum.

</>

Code

def find_min(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if nums[mid] > nums[high]:
            low = mid + 1
        elif nums[mid] < nums[high]:
            high = mid
        else:
            high -= 1
    return nums[low]

# Driver code
if __name__ == '__main__':
    arr = [2,2,2,0,1]
    print(find_min(arr))  # Output: 0

Line Notes

low, high = 0, len(nums) - 1Initialize pointers to cover entire array

while low < high:Loop until pointers converge to minimum index

mid = (low + high) // 2Calculate middle index to split search space

if nums[mid] > nums[high]:Minimum must be right of mid, move low up

elif nums[mid] < nums[high]:Minimum is at mid or left side, move high down

else:Duplicates found, reduce high by one to shrink search space

return nums[low]Low pointer points to minimum after loop ends

public class Solution {
    public static int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]) {
                low = mid + 1;
            } else if (nums[mid] < nums[high]) {
                high = mid;
            } else {
                high--;
            }
        }
        return nums[low];
    }

    public static void main(String[] args) {
        int[] arr = {2,2,2,0,1};
        System.out.println(findMin(arr)); // Output: 0
    }
}

Line Notes

int low = 0, high = nums.length - 1;Initialize search boundaries

while (low < high)Continue until low meets high

int mid = low + (high - low) / 2;Calculate mid to avoid overflow

if (nums[mid] > nums[high])Minimum is in right half, move low up

else if (nums[mid] < nums[high])Minimum is in left half including mid, move high down

elseDuplicates prevent decision, shrink high by one

return nums[low];Low points to minimum after loop

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else if (nums[mid] < nums[high]) {
            high = mid;
        } else {
            high--;
        }
    }
    return nums[low];
}

int main() {
    vector<int> arr = {2,2,2,0,1};
    cout << findMin(arr) << endl; // Output: 0
    return 0;
}

Line Notes

int low = 0, high = nums.size() - 1;Set initial search boundaries

while (low < high)Loop until low and high converge

int mid = low + (high - low) / 2;Calculate mid safely to avoid overflow

if (nums[mid] > nums[high])Minimum lies right of mid, move low up

else if (nums[mid] < nums[high])Minimum lies at or left of mid, move high down

elseDuplicates found, shrink high to reduce search space

return nums[low];Low points to minimum after loop ends

function findMin(nums) {
    let low = 0, high = nums.length - 1;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else if (nums[mid] < nums[high]) {
            high = mid;
        } else {
            high--;
        }
    }
    return nums[low];
}

// Test
console.log(findMin([2,2,2,0,1])); // Output: 0

Line Notes

let low = 0, high = nums.length - 1;Initialize pointers to cover entire array

while (low < high)Loop until low and high meet

let mid = Math.floor((low + high) / 2);Calculate middle index

if (nums[mid] > nums[high])Minimum is in right half, move low up

else if (nums[mid] < nums[high])Minimum is in left half including mid, move high down

elseDuplicates prevent decision, shrink high by one

return nums[low];Low points to minimum after loop

⏱

Complexity

TimeO(n) in worst case due to duplicates, average O(log n)

SpaceO(1)

Duplicates can degrade binary search to linear time in worst case, but typically it runs in logarithmic time.

💡 For n=100,000, worst case might check many elements, but usually it’s much faster than linear scan.

Interview Verdict: Accepted and optimal for most cases

This is the preferred approach in interviews as it balances efficiency and correctness with duplicates.

🧠

Binary Search with Early Exit on Sorted Subarray

💡 This approach adds a check to quickly return if the current search space is already sorted, improving efficiency in some cases.

Intuition

If the subarray between low and high is sorted, the minimum is at low. Otherwise, use the modified binary search logic to narrow down the minimum.

Algorithm

1. Initialize low and high pointers.
2. While low < high:
3. If nums[low] < nums[high], return nums[low] immediately.
4. Calculate mid index.
5. If nums[mid] > nums[high], move low to mid + 1.
6. Else if nums[mid] < nums[high], move high to mid.
7. Else decrement high by 1.
8. Return nums[low] after loop.

💡 The early exit check avoids unnecessary searching when the subarray is already sorted.

</>

Code

def find_min(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        if nums[low] < nums[high]:
            return nums[low]
        mid = (low + high) // 2
        if nums[mid] > nums[high]:
            low = mid + 1
        elif nums[mid] < nums[high]:
            high = mid
        else:
            high -= 1
    return nums[low]

# Driver code
if __name__ == '__main__':
    arr = [2,2,2,0,1]
    print(find_min(arr))  # Output: 0

Line Notes

if nums[low] < nums[high]:Check if current subarray is sorted to return early

return nums[low]Low points to minimum after loop ends

mid = (low + high) // 2Calculate mid index for binary search

if nums[mid] > nums[high]:Minimum lies right of mid, move low up

elif nums[mid] < nums[high]:Minimum lies at or left of mid, move high down

else:Duplicates found, shrink high to reduce search space

public class Solution {
    public static int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            if (nums[low] < nums[high]) {
                return nums[low];
            }
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]) {
                low = mid + 1;
            } else if (nums[mid] < nums[high]) {
                high = mid;
            } else {
                high--;
            }
        }
        return nums[low];
    }

    public static void main(String[] args) {
        int[] arr = {2,2,2,0,1};
        System.out.println(findMin(arr)); // Output: 0
    }
}

Line Notes

if (nums[low] < nums[high])Check if current subarray is sorted to return early

return nums[low];Low points to minimum after loop

int mid = low + (high - low) / 2;Calculate mid index safely

if (nums[mid] > nums[high])Minimum lies right of mid, move low up

else if (nums[mid] < nums[high])Minimum lies at or left of mid, move high down

elseDuplicates found, shrink high to reduce search space

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        if (nums[low] < nums[high]) {
            return nums[low];
        }
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else if (nums[mid] < nums[high]) {
            high = mid;
        } else {
            high--;
        }
    }
    return nums[low];
}

int main() {
    vector<int> arr = {2,2,2,0,1};
    cout << findMin(arr) << endl; // Output: 0
    return 0;
}

Line Notes

if (nums[low] < nums[high])Check if current subarray is sorted to return early

return nums[low];Low points to minimum after loop

int mid = low + (high - low) / 2;Calculate mid index safely

if (nums[mid] > nums[high])Minimum lies right of mid, move low up

else if (nums[mid] < nums[high])Minimum lies at or left of mid, move high down

elseDuplicates found, shrink high to reduce search space

function findMin(nums) {
    let low = 0, high = nums.length - 1;
    while (low < high) {
        if (nums[low] < nums[high]) {
            return nums[low];
        }
        let mid = Math.floor((low + high) / 2);
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else if (nums[mid] < nums[high]) {
            high = mid;
        } else {
            high--;
        }
    }
    return nums[low];
}

// Test
console.log(findMin([2,2,2,0,1])); // Output: 0

Line Notes

if (nums[low] < nums[high])Check if current subarray is sorted to return early

return nums[low];Low points to minimum after loop

let mid = Math.floor((low + high) / 2);Calculate middle index

if (nums[mid] > nums[high])Minimum lies right of mid, move low up

else if (nums[mid] < nums[high])Minimum lies at or left of mid, move high down

elseDuplicates found, shrink high to reduce search space

⏱

Complexity

TimeO(n) worst case due to duplicates, average O(log n)

SpaceO(1)

Early exit can speed up cases where subarrays are sorted, but duplicates can still degrade to linear time.

💡 This optimization helps in many practical cases, reducing unnecessary binary search steps.

Interview Verdict: Accepted and slightly optimized over approach 2

This is a practical enhancement to the modified binary search that can impress interviewers.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (Modified Binary Search) is the best to code in interviews due to balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - never code
2. Modified Binary Search (Shrink High)	O(n) worst, O(log n) average	O(1)	No	N/A	Code this approach
3. Binary Search with Early Exit	O(n) worst, O(log n) average	O(1)	No	N/A	Mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints, especially about duplicates.Step 2: State the brute force linear scan approach to show understanding.Step 3: Introduce the modified binary search approach and explain handling duplicates.Step 4: Discuss the early exit optimization for sorted subarrays.Step 5: Code the optimal approach carefully, test on edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of binary search modifications, handling duplicates, and ability to optimize while maintaining correctness.

Common Follow-ups

• What if duplicates were not allowed? → Simpler binary search without shrinking high.
• Can you find the index of the minimum element? → Yes, return low pointer index.
• How does the algorithm degrade with many duplicates? → To linear time in worst case.
• Can you modify to find the maximum element? → Similar logic but adjusted comparisons.

💡 These follow-ups test your grasp of variations and edge cases, common in interviews.

🔍

Pattern Recognition

When to Use

1) Array is sorted but rotated; 2) Need to find boundary or minimum; 3) Duplicates present; 4) Want better than linear time.

Signature Phrases

rotated sorted arrayfind minimum elementduplicates allowedminimize operations

NOT This Pattern When

Standard binary search on sorted arrays without rotation or duplicates

Similar Problems

Find Minimum in Rotated Sorted Array (No Duplicates) - simpler version without duplicatesSearch in Rotated Sorted Array - find target instead of minimumFind Peak Element - similar boundary finding with binary search

Practice

1. Given the following code snippet, what is the final output when calling min_speed_on_time([1, 3, 2], 2.7)?

from math import ceil

def can_arrive(dist, hour, speed):
    total_time = 0.0
    for i in range(len(dist) - 1):
        total_time += ceil(dist[i] / speed)
    total_time += dist[-1] / speed
    return total_time <= hour

def min_speed_on_time(dist, hour):
    low, high = 1.0, 10**7
    epsilon = 1e-6
    while high - low > epsilon:
        mid = (low + high) / 2
        if can_arrive(dist, hour, mid):
            high = mid
        else:
            low = mid
    return ceil(high)

print(min_speed_on_time([1,3,2], 2.7))

easy

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Trace feasibility checks at mid speeds

   At speed=1, total time > 2.7; at speed=3, total time <= 2.7. Binary search narrows to ~3.

2. Step 2: Final returned speed is ceil of high bound after convergence

   Binary search converges near 3, so ceil(high) = 3 is returned.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected minimum speed for given input [OK]

Hint: Binary search converges to minimum feasible speed [OK]

Common Mistakes:

• Off-by-one in ceil rounding
• Misunderstanding last segment time calculation

2. Examine the following code snippet intended to count occurrences of a target in a sorted array. Which line contains a subtle bug that can cause incorrect counts when the target is not present?

medium

A. Line 2: import bisect

B. Line 4: left = bisect.bisect_left(nums, target)

C. Line 5: right = bisect.bisect_left(nums, target + 1)

D. Line 6: return right - left

Solution

1. Step 1: Understand bisect_left behavior

   bisect_left returns insertion point even if target not present.

2. Step 2: Identify issue in return statement

   Subtracting right - left without checking if target exists can yield positive count when target is absent.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Return line assumes target presence, causing incorrect counts [OK]

Hint: Check target presence before subtracting indices [OK]

Common Mistakes:

• Ignoring target absence check
• Misusing bisect_left boundaries
• Assuming import or bisect calls cause bugs

3. The following code attempts to find the kth positive missing number from a sorted array arr. Which line contains a subtle bug that causes incorrect results for some inputs?

def findKthPositive(arr, k):
    n = len(arr)
    total_missing = arr[-1] - n
    if k > total_missing:
        return arr[-1] + (k - total_missing)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        missing = arr[mid] - mid  # Bug here
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

medium

A. Line returning arr[right] + (k - (arr[right] - (right + 1)))

B. Line calculating total_missing = arr[-1] - n

C. Line updating left = mid + 1

D. Line calculating missing = arr[mid] - mid

Solution

1. Step 1: Identify the missing count formula

   The correct missing count at index mid is arr[mid] - (mid + 1), since indices are zero-based but numbers start at 1.

2. Step 2: Analyze the bug impact

   Using arr[mid] - mid undercounts missing numbers by 1, causing incorrect binary search decisions and wrong final result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct missing count formula is arr[mid] - (mid + 1) [OK]

Hint: Missing count must subtract (mid + 1), not mid [OK]

Common Mistakes:

• Off-by-one in missing count calculation
• Incorrect binary search boundary updates
• Ignoring missing numbers before first element

4. What is the time complexity of the optimized binary search solution for finding the k-th smallest number in an m x n multiplication table, where the counting function breaks early once count ≥ k?

medium

A. O(m * log(m * n))

B. O(m log(m * n))

C. O(log(m * n))

D. O(m * n log(m * n))

Solution

1. Step 1: Identify outer binary search iterations

   The binary search runs over the value range [1, m*n], so about O(log(m*n)) iterations.

2. Step 2: Analyze counting function complexity

   Counting iterates over m rows, each capped by min(n, x//i), but early break reduces average work. Worst case is O(m) per count.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(m * log(m * n)) [OK]

Hint: Counting is O(m), binary search O(log(m*n)) [OK]

Common Mistakes:

• Confusing n with m in complexity
• Assuming counting is O(m*n)

5. Suppose the problem is modified so that the two input arrays can contain duplicate elements and you want to find the median of the combined multiset where elements can be reused infinitely many times. Which modification to the binary search on value range approach correctly handles this scenario?

hard

A. Modify countLessEqual to count elements less or equal normally, but adjust total length to infinite, then return left directly.

B. Use the same binary search on value range but count elements less or equal considering infinite duplicates as infinite count.

C. Use binary search on value range with countLessEqual unchanged, but adjust the target count to half of the finite combined length ignoring duplicates.

D. Use binary search on value range with countLessEqual unchanged, but since duplicates are infinite, the median is the minimum element.

Solution

1. Step 1: Understand infinite duplicates impact

   Infinite duplicates mean total length is infinite, so median is the smallest value with countLessEqual ≥ half of infinite.

2. Step 2: Adjust countLessEqual and target

   Counting elements normally but total length infinite means target is infinite/2 = infinite, so median is left boundary where countLessEqual reaches infinite.

3. Step 3: Return left directly

   Since infinite duplicates, median is the smallest value that satisfies countLessEqual condition, so return left.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Infinite duplicates require adjusting total length and returning left [OK]

Hint: Infinite duplicates make total length infinite, median is smallest qualifying value [OK]

Common Mistakes:

• Counting duplicates as finite
• Ignoring infinite total length
• Returning min element incorrectly