Search in Rotated Array II (Duplicates)

📋

Search in Rotated Array II (Duplicates)

Edge cases:

</>

IDE

def search(nums: list[int], target: int) -> bool:public boolean search(int[] nums, int target)bool search(vector<int>& nums, int target)function search(nums, target)

def search(nums, target):
    # Write your solution here
    pass

class Solution {
    public boolean search(int[] nums, int target) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool search(vector<int>& nums, int target) {
    // Write your solution here
    return false;
}

function search(nums, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseFails to find target when duplicates cause ambiguity and search space is not shrunk properly.✅ Add logic to shrink both ends when nums[left] == nums[mid] == nums[right].

Wrong: trueReturns true incorrectly when target is not present due to incorrect mid comparisons.✅ Ensure comparisons correctly exclude impossible halves and only return true when nums[mid] == target.

Wrong: runtime error or crashDoes not handle empty array or single element arrays properly causing index errors.✅ Add explicit checks for empty and single-element arrays before binary search loop.

Wrong: timeoutAlgorithm degenerates to O(n^2) due to not shrinking search space when duplicates equal mid.✅ Implement shrinking both ends when nums[left] == nums[mid] == nums[right] to reduce search space.

✓

Test Cases

Handle base cases like empty and single-element arrays before binary search.

Focus on shrinking search space when duplicates cause ambiguity.

Consider worst-case complexity and optimize duplicate handling.

t1_01basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Target 0 is present in the rotated array.

💡 Use modified binary search to handle rotation and duplicates.

💡 Check if left, mid, or right elements equal target; shrink search space carefully.

💡 When duplicates at edges equal mid, shrink both ends to avoid ambiguity.

Why it failed: Incorrect output means binary search logic failed to handle duplicates properly; fix by shrinking both ends when nums[left] == nums[mid] == nums[right].

✓ Correctly identifies presence of target in rotated array with duplicates.

t1_02basic

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Target 3 is not present in the rotated array.

💡 Confirm binary search correctly identifies absence of target.

💡 Ensure search space shrinks properly even if target is missing.

💡 Return false only after exhausting all possible positions.

Why it failed: Returning true incorrectly means search did not fully explore array or misidentified target; fix by proper mid comparisons and shrinking.

✓ Correctly returns false when target is absent.

t2_01edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty array cannot contain any target.

💡 Check for empty input before binary search.

💡 Return false immediately if array length is zero.

💡 Avoid index errors by handling empty array edge case.

Why it failed: Code crashes or returns true on empty array; fix by adding a check for empty input at start.

✓ Correctly handles empty array by returning false.

t2_02edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Single element array where target is present.

💡 Binary search should handle single element arrays.

💡 Check if nums[0] equals target before proceeding.

💡 Return true immediately if single element matches target.

Why it failed: Fails to find target in single element array; fix by checking single element equality before binary search loop.

✓ Correctly returns true for single element matching target.

t2_03edge

Input{"nums":[1],"target":0}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element array where target is absent.

💡 Check single element against target before binary search.

💡 Return false if single element does not match target.

💡 Avoid unnecessary loops for single element arrays.

Why it failed: Incorrectly returns true or crashes on single element array without target; fix by explicit single element check.

✓ Correctly returns false when single element does not match target.

t2_04edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Array with all duplicates where target is present.

💡 Duplicates can confuse binary search decisions.

💡 Shrink both ends when duplicates equal mid to reduce search space.

💡 Return true if any element equals target.

Why it failed: Fails to find target in all duplicates array; fix by shrinking both ends when nums[left] == nums[mid] == nums[right].

✓ Correctly finds target in all duplicates array.

t3_01corner

Input{"nums":[1,1,3,1],"target":3}

Expectedtrue

⏱ Performance - must finish in 2000ms

Duplicates cause ambiguity; target 3 is present.

💡 Duplicates at edges can confuse binary search decisions.

💡 Shrink both ends when nums[left] == nums[mid] == nums[right] to avoid infinite loops.

💡 Ensure search space reduces even with duplicates.

Why it failed: Infinite loop or incorrect false due to not shrinking both ends when duplicates equal mid; fix by adding both ends shrink step.

✓ Handles duplicates correctly and finds target.

t3_02corner

Input{"nums":[2,2,2,3,2,2,2],"target":3}

Expectedtrue

⏱ Performance - must finish in 2000ms

Target in middle with duplicates around; tests correct mid handling.

💡 Check mid element carefully when duplicates surround it.

💡 Do not assume left or right half is sorted if duplicates present.

💡 Shrink search space cautiously to find target.

Why it failed: Fails to find target due to assuming sorted half incorrectly with duplicates; fix by handling duplicates by shrinking both ends.

✓ Correctly finds target despite duplicates around mid.

t3_03corner

Input{"nums":[1,3,1,1,1],"target":3}

Expectedtrue

⏱ Performance - must finish in 2000ms

Rotated array with duplicates and target in rotated segment.

💡 Do not rely solely on nums[left] <= nums[mid] to decide sorted half.

💡 When nums[left] == nums[mid], shrink left to reduce ambiguity.

💡 Use careful comparisons to locate target.

Why it failed: Incorrectly returns false due to greedy assumption that left half is sorted; fix by shrinking left when duplicates equal mid.

✓ Correctly locates target in rotated array with duplicates.

t4_01performance

Input{"nums":[10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000],"target":1}

Expectednull

⏱ Performance - must finish in 2000ms

n=300, worst case O(n) due to duplicates, must complete within 2s.

💡 Duplicates can degrade binary search to linear time.

💡 Use shrinking both ends to reduce search space.

💡 Avoid infinite loops by careful duplicate handling.

Why it failed: TLE due to O(n) worst case complexity from duplicates; fix by shrinking both ends when nums[left] == nums[mid] == nums[right].

✓ Algorithm runs within time limit despite duplicates.

Practice

1. Given the following code snippet, what is the final return value when calling minDays([1,10,3,10,2], 3, 1)?

easy

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Trace binary search boundaries

   min bloom day = 1, max bloom day = 10. Binary search mid values: 5, then 3, then 2.

2. Step 2: Check feasibility at mid=5 and mid=2

   At day=5, canMake returns true (flowers bloomed on days 1,3,2). Try lower days. At day=2, canMake returns true as well. At day=1, canMake returns false. So minimum day is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tracing confirms minimum feasible day is 2. [OK]

Hint: Check feasibility at midpoints to narrow minimum day [OK]

Common Mistakes:

• Off-by-one errors in binary search boundaries
• Miscounting bouquets in feasibility check

2. You need to find the minimum speed to travel through a series of distances within a given total time, where each segment except the last must be completed in whole hours (rounded up). Which algorithmic approach guarantees finding the minimum feasible speed efficiently?

easy

A. Binary search on the speed range (answer space) combined with a feasibility check

B. Brute force linear search incrementing speed until the time constraint is met

C. Dynamic programming to store minimum speeds for subproblems

D. Greedy approach by always choosing the fastest possible speed for each segment

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the minimum speed that satisfies a time constraint with rounding up travel times for all but the last segment.

2. Step 2: Identify the suitable algorithmic pattern

   Binary search on the answer space (speed) efficiently narrows down the minimum feasible speed by checking feasibility at midpoints, unlike greedy or DP which do not fit the problem structure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on answer space is standard for optimization problems with monotonic feasibility [OK]

Hint: Binary search on answer space fits monotonic feasibility [OK]

Common Mistakes:

• Thinking greedy or DP can solve this efficiently
• Using brute force linear search without pruning

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

4. Examine the following buggy code that attempts to search a target in a 2D matrix using the staircase search approach starting from the top-left corner. Identify the line containing the subtle bug that causes incorrect behavior or infinite loops.

medium

A. Line 9: Incrementing row when element is less than target

B. Line 7: Using '<' instead of '<=' in while condition

C. Line 11: Decrementing col without boundary check

D. Line 3: Starting at top-left corner instead of top-right

Solution

1. Step 1: Analyze starting point

   Starting at top-left corner breaks the staircase search logic because we cannot eliminate rows or columns correctly.

2. Step 2: Check pointer movements

   Moving row down when current < target and col left when current > target only works if starting at top-right corner.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Starting at top-left causes infinite loops or wrong results [OK]

Hint: Staircase search must start at top-right corner [OK]

Common Mistakes:

• Starting at top-left or bottom-left corner
• Not checking empty matrix
• Moving pointers in wrong directions

5. Suppose the array is no longer sorted but you still need to find the first and last positions of a target value. Which approach is correct and efficient?

hard

A. Use a linear scan to find first and last occurrences directly

B. Sort the array first, then apply modified binary search to find positions

C. Use the same modified binary search approach since it works on any array

D. Use a hash map to store all indices of each value, then retrieve target positions

Solution

1. Step 1: Recognize that binary search requires sorted array

   Without sorting, binary search cannot guarantee correct positions.

2. Step 2: Evaluate alternatives

   Sorting changes indices, so linear scan or hash map are options; linear scan is simplest and O(n).

3. Step 3: Compare efficiency and correctness

   Linear scan finds first and last positions in one pass without modifying array.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search requires sorted input; linear scan works otherwise [OK]

Hint: Binary search needs sorted array; linear scan works otherwise [OK]

Common Mistakes:

• Trying binary search on unsorted array
• Sorting and losing original indices
• Overcomplicating with hash maps