Find Minimum in Rotated Array II (With Duplicates)

▶

Steps

setup

Initialize low and high pointers

Set low to 0 and high to the last index of the array to start searching the entire array.

💡 Initialization defines the full search space before any comparisons.

Line:

low, high = 0, len(nums) - 1

💡 The entire array is considered initially as the minimum could be anywhere.

compare

Check if subarray is already sorted

Compare nums[low] and nums[high]. Since nums[0] = 2 is not less than nums[4] = 1, the array is not sorted in this range.

💡 If the subarray was sorted, the minimum would be at low, allowing early exit.

Line:

if nums[low] < nums[high]:
    return nums[low]

💡 The search must continue because the minimum is not at the current low index.

traverse

Calculate mid index

Calculate mid as the floor of (low + high) / 2, which is (0 + 4) // 2 = 2.

💡 Mid divides the current search space to compare and decide which half to keep.

Line:

mid = (low + high) // 2

💡 Midpoint is chosen to split the search space evenly.

compare

Compare nums[mid] and nums[high]

Compare nums[mid] = 2 with nums[high] = 1. Since 2 > 1, the minimum must be in the right half beyond mid.

💡 If mid value is greater than high, minimum is in the right half, so low moves up.

Line:

if nums[mid] > nums[high]:
    low = mid + 1

💡 We can discard the left half including mid because minimum is to the right.

traverse

Calculate new mid index in reduced search space

Calculate mid as (low + high) // 2 = (3 + 4) // 2 = 3.

💡 Recalculate mid to split the new smaller search space.

Line:

mid = (low + high) // 2

💡 Midpoint now points to index 3 for further comparison.

compare

Compare nums[mid] and nums[high] in new range

Compare nums[mid] = 0 with nums[high] = 1. Since 0 < 1, the minimum is in the left half including mid.

💡 If mid value is less than high, minimum is at mid or to the left, so high moves down.

Line:

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

💡 We can discard the right half beyond mid because minimum is at mid or left.

compare

Check if subarray is sorted in new range

Now low=3 and high=3. Since low equals high, the search space is a single element.

💡 When low equals high, the minimum is found at that index.

Line:

while low < high:

💡 Search space reduced to one element, which is the minimum.

final

Return minimum element

Return nums[low] = nums[3] = 0 as the minimum element in the rotated array.

💡 The algorithm successfully found the minimum by narrowing the search space and checking sorted subarrays.

Line:

return nums[low]

💡 The minimum element is at index 3 with value 0.

final

Final state with answer

The algorithm ends with the minimum element at index 3, value 0, after 9 steps.

💡 Final state confirms the answer and total steps taken.

💡 The minimum element is confirmed at index 3 with value 0.

def find_min(nums):
    low, high = 0, len(nums) - 1  # STEP 1
    while low < high:  # STEP 2 loop start
        if nums[low] < nums[high]:  # STEP 5 check sorted
            return nums[low]  # STEP 5 early return
        mid = (low + high) // 2  # STEP 3 calculate mid
        if nums[mid] > nums[high]:  # STEP 4 compare mid and high
            low = mid + 1  # STEP 4 move low up
        elif nums[mid] < nums[high]:  # STEP 6 compare mid and high
            high = mid  # STEP 6 move high down
        else:  # STEP 7 handle duplicates
            high -= 1  # STEP 7 decrement high
    return nums[low]  # STEP 6 or final return

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

📊

Find Minimum in Rotated Array II (With Duplicates) - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and comparison helps you understand how the algorithm deals with duplicates and rotated arrays, which is not obvious from code alone.

lo

2

0

2

1

2

2

0

3

hi

1

4

Next: lo=0 hi=4

lo

2

0

2

1

2

2

0

3

hi

1

4

Next: lo=0 hi=4

lo

2

0

2

1

mid

2

2

0

3

hi

1

4

mid[2]=2 - mid value ready for comparison

Next: lo=0 hi=4

2

0

2

1

mid

2

2

lo

0

3

hi

1

4

mid[2]=2 - nums[mid] > nums[high], move low up

Next: lo=3 hi=4

2

0

2

1

2

2

lo/mid

0

3

hi

1

4

mid[3]=0 - mid value ready for comparison

Next: lo=3 hi=4

2

0

2

1

2

2

lo/mid/hi

0

3

1

4

mid[3]=0 - nums[mid] < nums[high], move high down

Next: lo=3 hi=3

2

0

2

1

2

2

lo/hi

0

3

1

4

Next: lo=3 hi=3

2

0

2

1

2

2

lo/hi

0

3

1

4

Next: lo=3 hi=3

2

0

2

1

2

2

lo/hi

0

3

1

4

Next: lo=3 hi=3

Key Takeaways

✓ The algorithm uses binary search to efficiently narrow down the search space even with duplicates.

Duplicates complicate elimination, but the algorithm handles them by shrinking the high pointer carefully.

✓ Early exit is possible when the current subarray is already sorted, saving unnecessary work.

Recognizing sorted subarrays allows immediate return of the minimum without further searching.

✓ When nums[mid] equals nums[high], the algorithm cannot decide which side to discard and reduces high by one to shrink the space.

This subtle step prevents infinite loops and ensures progress despite duplicates.

Practice

1. You are given an unsorted array of integers and need to find an index of an element that is greater than its neighbors (or boundary elements if at edges). Which algorithmic approach guarantees an optimal O(log n) time solution for this problem?

easy

A. Linear scan checking each element and its neighbors sequentially

B. Dynamic programming to store and compare local maxima

C. Modified binary search that compares middle element with its right neighbor to decide search direction

D. Greedy approach selecting the first element larger than the previous one

Solution

1. Step 1: Understand problem constraints

   The problem requires finding a peak element efficiently, which suggests a logarithmic time approach.

2. Step 2: Identify algorithm matching O(log n) time

   Modified binary search that compares mid element with its neighbor to decide which half to search next achieves O(log n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search halves search space each step [OK]

Hint: Peak element search uses modified binary search [OK]

Common Mistakes:

• Assuming greedy or DP solves this optimally
• Confusing linear scan as optimal
• Using DP unnecessarily

2. Given the following code for fast exponentiation, what is the value of result after the first iteration of the while loop when calling myPow(2.0, 3)?

easy

A. 1.0

B. 8.0

C. 4.0

D. 2.0

Solution

1. Step 1: Trace first iteration with n=3

   Initial values: result=1.0, current_product=2.0, n=3. Since n%2==1, result *= current_product -> result=2.0.

2. Step 2: Update current_product and n

   current_product *= current_product -> 4.0, n //= 2 -> 1. Loop continues.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   After first iteration, result updated once by current_product=2.0 [OK]

Hint: Check if n is odd to multiply result first [OK]

Common Mistakes:

• Forgetting to multiply result when n is odd
• Updating current_product before result
• Off-by-one in loop iterations

3. The following code attempts to find the kth smallest element in a sorted matrix using a min-heap. Identify the line containing the subtle bug that can cause incorrect results when duplicates exist or when counting is off.

medium

A. Line where count is incremented after the kth check (count += 1)

B. Line where initial elements are pushed into the heap (heapq.heappush in for loop)

C. Line where the kth element is checked (if count == k: return val)

D. Line where next element in the row is pushed (heapq.heappush inside while loop)

Solution

1. Step 1: Understand counting logic

   Count should increment before checking if count == k to correctly identify the kth popped element.

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

   Currently, count is incremented after the check, so the function returns the (k-1)th element instead of kth.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment count before kth check fixes off-by-one error [OK]

Hint: Check order of count increment and kth check [OK]

Common Mistakes:

• Off-by-one in counting popped elements
• Returning before incrementing count
• Misplaced heap push causing missing elements

4. Consider the following buggy code snippet for finding the pivot in a rotated sorted array. Which line contains the subtle bug that can cause incorrect pivot detection?

medium

A. if nums[mid] > nums[high]: -- comparison logic is correct

B. mid = (low + high) / 2 -- mid should be integer index, not float

C. low = mid + 1 -- updating low is correct when nums[mid] > nums[high]

D. return low -- returning low as pivot is correct

Solution

1. Step 1: Identify mid calculation issue

   mid is computed using division '/', which returns float in Python 3, causing invalid indexing.

2. Step 2: Impact of float mid

   Using float as index causes runtime error or incorrect behavior; integer division '//' is required.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Changing '/' to '//' fixes the bug [OK]

Hint: mid must be integer index [OK]

Common Mistakes:

• Using '/' instead of '//' in Python
• Misplaced comparison operators

5. Suppose the problem is modified so that the array can contain multiple identical adjacent elements (plateaus), and you want to find any peak element efficiently. Which modification to the original modified binary search algorithm correctly handles this scenario without degrading to linear time?

hard

A. Change the comparison to nums[mid] <= nums[mid + 1] and recurse right if true, else left

B. Skip over equal adjacent elements by moving mid until nums[mid] != nums[mid + 1] before comparison

C. Use linear scan since binary search cannot handle plateaus correctly

D. Modify recursion to always recurse left half to find the first peak

Solution

1. Step 1: Understand plateau challenge

   Equal adjacent elements break strict inequality assumptions in original binary search.

2. Step 2: Modify comparison to handle equality

   Using ≤ ensures recursion moves right when plateau or increasing slope, preserving O(log n) time.

3. Step 3: Avoid linear scan or skipping elements

   Skipping elements or linear scan can degrade performance; always recursing left loses efficiency.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Modified comparison handles plateaus without extra overhead [OK]

Hint: Use <= comparison to handle plateaus in binary search [OK]

Common Mistakes:

• Trying to skip equal elements linearly
• Assuming linear scan is necessary
• Always recursing one side losing log n guarantee