Search in Rotated Array II (Duplicates)

▶

Steps

setup

Initialize pointers

Set left to 0 and right to the last index of the array to start searching the entire array.

💡 Initializing pointers to cover the full array ensures no elements are missed initially.

Line:

left, right = 0, len(nums) - 1

💡 The search space currently includes the entire array.

shrink

Skip duplicates at left boundary

Check if nums[left] equals nums[left + 1] and increment left to skip duplicates at the left boundary.

💡 Skipping duplicates at boundaries prevents unnecessary comparisons and narrows the search space efficiently.

Line:

while left < right and nums[left] == nums[left + 1]:
    left += 1

💡 No duplicates at the left boundary to skip, so left remains at 0.

shrink

Skip duplicates at right boundary

Check if nums[right] equals nums[right - 1] and decrement right to skip duplicates at the right boundary.

💡 Skipping duplicates at the right boundary also helps reduce the search space and avoid redundant checks.

Line:

while right > left and nums[right] == nums[right - 1]:
    right -= 1

💡 No duplicates at the right boundary to skip, so right remains at 6.

compare

Calculate mid index

Calculate mid as the floor of (left + right) / 2 to check the middle element of the current search space.

💡 Midpoint divides the search space to decide which half to explore next.

Line:

mid = (left + right) // 2

💡 Mid is at index 3, pointing to value 0.

compare

Check if mid value equals target

Compare nums[mid] with target; since they are equal, the target is found.

💡 Finding the target at mid means the search can end successfully.

Line:

if nums[mid] == target:
    return True

💡 The target 0 is present at index 3 in the array.

reconstruct

Return True as target found

Since the target was found, the function returns True indicating success.

💡 Returning True confirms the presence of the target in the array.

Line:

return True

💡 The search terminates successfully with the target found.

setup

Restart search for target 3 (not present) - Initialize pointers

Reset left and right pointers to search entire array for target 3.

💡 Starting fresh search for a different target demonstrates the algorithm's behavior when target is absent.

Line:

left, right = 0, len(nums) - 1

💡 Search space covers entire array again.

shrink

Skip duplicates at left boundary for target 3

Check and skip duplicates at left boundary; none found so left remains 0.

💡 Duplicate skipping keeps search efficient by ignoring repeated values at boundaries.

Line:

while left < right and nums[left] == nums[left + 1]:
    left += 1

💡 Left boundary stable at 0.

shrink

Skip duplicates at right boundary for target 3

Check and skip duplicates at right boundary; none found so right remains 6.

💡 Right boundary duplicate skipping avoids redundant checks.

Line:

while right > left and nums[right] == nums[right - 1]:
    right -= 1

💡 Right boundary stable at 6.

compare

Calculate mid index for target 3

Calculate mid index to check middle element for target 3.

💡 Midpoint helps decide which half to search next.

Line:

mid = (left + right) // 2

💡 Mid is 3, value is 0.

compare

Check if left half is sorted

Compare nums[left] and nums[mid] to determine if left half is sorted.

💡 Knowing which half is sorted guides the binary search decision.

Line:

if nums[left] <= nums[mid]:

💡 Left half is not sorted, so right half must be sorted.

compare

Check if target lies in right sorted half

Check if target is between nums[mid] and nums[right] to decide search direction.

💡 If target is in sorted half, search there; else search the other half.

Line:

if nums[mid] < target <= nums[right]:

💡 Target is not in right sorted half, so search left half next.

shrink

Update right pointer to mid - 1

Set right to mid - 1 to narrow search to left half.

💡 Shrinking search space focuses on the half where target may exist.

Line:

right = mid - 1

💡 Search space is now indices 0 to 2.

shrink

Skip duplicates at left boundary in new search space

Check and skip duplicates at left boundary; none found so left remains 0.

💡 Duplicate skipping continues to optimize search.

Line:

while left < right and nums[left] == nums[left + 1]:
    left += 1

💡 Left boundary stable at 0.

shrink

Skip duplicates at right boundary in new search space

Check and skip duplicates at right boundary; none found so right remains 2.

💡 Right boundary duplicate skipping continues.

Line:

while right > left and nums[right] == nums[right - 1]:
    right -= 1

💡 Right boundary stable at 2.

compare

Calculate mid index in reduced search space

Calculate mid index to check middle element in indices 0 to 2.

💡 Midpoint guides next search decision.

Line:

mid = (left + right) // 2

💡 Mid is 1, value is 5.

compare

Check if left half is sorted in reduced space

Compare nums[left] and nums[mid] to determine if left half is sorted.

💡 Identifying sorted half helps decide search direction.

Line:

if nums[left] <= nums[mid]:

💡 Left half is sorted, so check if target lies here.

compare

Check if target lies in left sorted half

Check if target is between nums[left] and nums[mid] to decide search direction.

💡 If target is in sorted half, search there; else search the other half.

Line:

if nums[left] <= target < nums[mid]:

💡 Target lies in left half, so update right pointer.

shrink

Update right pointer to mid - 1

Set right to mid - 1 to narrow search to left half.

💡 Shrinking search space focuses on the half where target may exist.

Line:

right = mid - 1

💡 Search space is now index 0 only.

prune

Terminate search - target not found

Since left pointer is greater than right, search space is empty and target is not found.

💡 Empty search space means target is absent in the array.

Line:

while left <= right:
    ...
return False

💡 Target 3 is not present in the array.

def search(nums, target):
    left, right = 0, len(nums) - 1  # STEP 1,7
    while left <= right:  # STEP 2-6,8-20
        while left < right and nums[left] == nums[left + 1]:
            left += 1  # STEP 2,8,14
        while right > left and nums[right] == nums[right - 1]:
            right -= 1  # STEP 3,9,15
        mid = (left + right) // 2  # STEP 4,10,16
        if nums[mid] == target:
            return True  # STEP 5,6
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1  # STEP 13,19
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return False  # STEP 20

if __name__ == '__main__':
    print(search([2,5,6,0,0,1,2], 0))  # True
    print(search([2,5,6,0,0,1,2], 3))  # False

📊

Search in Rotated Array II (Duplicates) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how duplicates and rotation affect the binary search logic, which is hard to grasp from code alone.

Target: 0

lo

2

0

5

1

6

2

0

3

0

4

1

5

hi

2

6

Next: lo=0 hi=6

Target: 0

lo

2

0

5

1

6

2

0

3

0

4

1

5

hi

2

6

Next: lo=0 hi=6

Target: 0

lo

2

0

5

1

6

2

0

3

0

4

1

5

hi

2

6

Next: lo=0 hi=6

Target: 0

lo

2

0

5

1

6

2

mid

0

3

0

4

1

5

hi

2

6

mid[3]=0 - nums[mid] == target

Next: lo=0 hi=6

Target: 0

lo

2

0

5

1

6

2

mid

0

3

0

4

1

5

hi

2

6

mid[3]=0 - nums[mid] == target

Next: lo=0 hi=6

Target: 0

lo

2

0

5

1

6

2

mid

0

3

0

4

1

5

hi

2

6

mid[3]=0 - target found

Next: lo=0 hi=6

Target: 3

lo

2

0

5

1

6

2

0

3

0

4

1

5

hi

2

6

Next: lo=0 hi=6

Target: 3

lo

2

0

5

1

6

2

0

3

0

4

1

5

hi

2

6

Next: lo=0 hi=6

Target: 3

lo

2

0

5

1

6

2

0

3

0

4

1

5

hi

2

6

Next: lo=0 hi=6

Target: 3

lo

2

0

5

1

6

2

mid

0

3

0

4

1

5

hi

2

6

mid[3]=0 - nums[mid] != target

Next: lo=0 hi=6

Target: 3

lo

2

0

5

1

6

2

mid

0

3

0

4

1

5

hi

2

6

mid[3]=0 - left half not sorted

Next: lo=0 hi=6

Target: 3

lo

2

0

5

1

6

2

mid

0

3

0

4

1

5

hi

2

6

mid[3]=0 - target not in right half

Next: lo=0 hi=2

Target: 3

lo

2

0

5

1

hi

6

2

mid

0

3

0

4

1

5

2

6

mid[3]=0 - search space shrunk to left half

Next: lo=0 hi=2

Target: 3

lo

2

0

5

1

hi

6

2

0

3

0

4

1

5

2

6

Next: lo=0 hi=2

Target: 3

lo

2

0

5

1

hi

6

2

0

3

0

4

1

5

2

6

Next: lo=0 hi=2

Target: 3

lo

2

0

mid

5

1

hi

6

2

0

3

0

4

1

5

2

6

mid[1]=5 - nums[mid] != target

Next: lo=0 hi=2

Target: 3

lo

2

0

mid

5

1

hi

6

2

0

3

0

4

1

5

2

6

mid[1]=5 - left half sorted

Next: lo=0 hi=2

Target: 3

lo

2

0

mid

5

1

hi

6

2

0

3

0

4

1

5

2

6

mid[1]=5 - target in left half

Next: lo=0 hi=0

Target: 3

lo/hi

2

0

mid

5

1

6

2

0

3

0

4

1

5

2

6

mid[1]=5 - search space shrunk to left half

Next: lo=0 hi=0

Target: 3

hi

2

0

lo

5

1

6

2

0

3

0

4

1

5

2

6

Next: lo=1 hi=0

Key Takeaways

✓ Skipping duplicates at the boundaries before each binary search iteration is crucial to avoid infinite loops and correctly narrow the search space.

This behavior is subtle and often missed when reading code, but watching the pointers move clarifies its necessity.

✓ Determining which half of the array is sorted despite rotation helps decide where to search next.

Visualizing the sorted half and target range comparison makes the branching logic intuitive.

✓ When the target is found at mid, the search ends immediately, demonstrating the efficiency of binary search even in rotated arrays with duplicates.

Seeing the exact moment the target is found reinforces understanding of the algorithm's stopping condition.

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. You are given a sorted array and a target value. You need to find the starting and ending indices of the target value in the array. Which algorithmic approach guarantees an optimal solution with logarithmic time complexity?

easy

A. Linear scan from start to end to find first and last occurrences

B. Greedy approach to jump to target positions based on value comparisons

C. Modified binary search to find leftmost and rightmost positions separately

D. Dynamic programming to store intermediate results for each index

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so binary search can be used to find target positions efficiently.

2. Step 2: Identify suitable algorithm

   Modified binary search can find leftmost and rightmost indices in O(log n) time, which is optimal compared to linear scan or greedy methods.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits sorted property for O(log n) search [OK]

Hint: Sorted array + position search -> modified binary search [OK]

Common Mistakes:

• Thinking linear scan is optimal
• Confusing greedy with binary search
• Using DP unnecessarily

3. Consider the following Python code implementing the min-heap approach to find the kth smallest element in a sorted matrix. Given the matrix [[1,3],[2,4]] and k = 3, what value does the function return?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Initialize min-heap with first elements

   Push (1,0,0) and (2,1,0) into heap.

2. Step 2: Extract elements until count == k

   Pop 1 (count=1), push 3 from row 0; pop 2 (count=2), push 4 from row 1; pop 3 (count=3), return 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Third smallest element is 3 [OK]

Hint: Trace heap pops and pushes carefully [OK]

Common Mistakes:

• Off-by-one counting of popped elements
• Returning wrong popped value
• Confusing row and column indices

4. Consider the following buggy implementation of fast exponentiation. Which line contains the subtle bug that causes incorrect results for negative exponents?

medium

A. Line 12: if negative: return result

B. Line 4: negative = n < 0

C. Line 3: if n == 0: return 1.0

D. Line 9: current_product *= current_product

Solution

1. Step 1: Understand handling of negative exponents

   For negative n, the result should be 1 / (x^{|n|}).

2. Step 2: Identify incorrect return statement

   Line 12 returns result directly for negative exponents, missing the reciprocal operation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning result instead of 1 / result breaks correctness for negative powers [OK]

Hint: Negative exponent requires reciprocal at return [OK]

Common Mistakes:

• Forgetting to invert result for negative n
• Misplacing abs() call
• Incorrect loop condition

5. Suppose the problem is modified so that the array elements can be reused infinitely many times (i.e., you can pick elements multiple times in order). Which of the following changes to the algorithm is necessary to correctly find the minimal largest sum when splitting into m subarrays?

hard

A. Change feasibility check to a dynamic programming approach since greedy fails with reuse

B. Modify feasibility check to allow overlapping subarrays and remove prefix sums

C. Keep the same binary search on answer space and greedy feasibility check without changes

D. Use a sliding window approach instead of binary search to handle reuse

Solution

1. Step 1: Understand reuse impact

   Allowing reuse breaks the greedy feasibility check because subarrays can overlap or be formed in multiple ways.

2. Step 2: Identify correct approach

   Dynamic programming is needed to explore combinations with reuse, as greedy feasibility check no longer guarantees correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reuse requires DP, not greedy feasibility [OK]

Hint: Reuse breaks greedy feasibility, needs DP [OK]

Common Mistakes:

• Assuming greedy feasibility check still works with reuse
• Trying to fix with sliding window which doesn't handle reuse properly
• Ignoring that prefix sums alone don't solve reuse complexity