Find Peak Element

▶

Steps

setup

Initialize Search Boundaries

Start binary search with low=0 and high=3, covering the entire array.

💡 Initial boundaries define the full search space before any comparisons.

Line:

return binarySearch(0, len(nums) - 1)

💡 The search space covers the entire array initially.

compare

Calculate Midpoint

Calculate mid as (0 + 3) // 2 = 1 to check the middle element in the current search space.

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

Line:

mid = (low + high) // 2

💡 Mid index divides the array into two halves for comparison.

compare

Compare nums[mid] and nums[mid+1]

Compare nums[1] = 2 with nums[2] = 3 to decide which half contains a peak.

💡 This comparison determines if the peak lies to the right or left of mid.

Line:

if nums[mid] < nums[mid + 1]:

💡 Since nums[mid] < nums[mid+1], the peak must be in the right half.

shrink

Update Search Space to Right Half

Update low to mid + 1 = 2, keeping high at 3, narrowing search to indices [2, 3].

💡 Updating boundaries focuses the search on the promising half containing the peak.

Line:

return binarySearch(mid + 1, high)

💡 Search space is now smaller, focusing on the right half.

compare

Calculate Midpoint in New Search Space

Calculate mid as (2 + 3) // 2 = 2 to check the middle element in the new search space.

💡 Midpoint recalculation is necessary for the smaller search space.

Line:

mid = (low + high) // 2

💡 Mid now points to index 2, the start of the new search space.

compare

Compare nums[mid] and nums[mid+1] Again

Compare nums[2] = 3 with nums[3] = 1 to decide which half contains a peak.

💡 This comparison will determine if the peak is at mid or to the left.

Line:

if nums[mid] < nums[mid + 1]:

💡 Since nums[mid] >= nums[mid+1], the peak is at mid or to the left.

shrink

Update Search Space to Left Half

Update high to mid = 2, keeping low at 2, narrowing search to index [2].

💡 Updating boundaries focuses the search on the single element that could be the peak.

Line:

return binarySearch(low, mid)

💡 Search space is now a single element, candidate for peak.

compare

Check if Search Space Reduced to One Element

Since low equals high (2 == 2), we have found the peak element index.

💡 When low equals high, the peak is found because no further search is needed.

Line:

if low == high:
    return low

💡 The peak element index is identified.

reconstruct

Prepare to Return Peak Index

Prepare to return index 2 as the peak element index where nums[2] = 3 is greater than neighbors.

💡 This step confirms the peak index before returning it.

Line:

return low

💡 The algorithm is ready to output the final peak index.

reconstruct

Return Peak Index

Return index 2 as the peak element index where nums[2] = 3 is greater than neighbors.

💡 Returning the index completes the search and provides the answer.

Line:

return binarySearch(0, len(nums) - 1)

💡 The algorithm successfully found the peak element index.

def findPeakElement(nums):
    def binarySearch(low, high):
        # STEP 8: Check if low == high
        if low == high:
            return low
        # STEP 2,5: Calculate mid
        mid = (low + high) // 2
        # STEP 3,6: Compare nums[mid] and nums[mid+1]
        if nums[mid] < nums[mid + 1]:
            # STEP 4: Search right half
            return binarySearch(mid + 1, high)
        else:
            # STEP 7: Search left half
            return binarySearch(low, mid)

# STEP 1: Initial call
print(findPeakElement([1, 2, 3, 1]))  # Output: 2

📊

Find Peak Element - Watch the Algorithm Execute, Step by Step

Watching each comparison and pointer update helps you understand how the algorithm eliminates half of the search space each time, making it very efficient.

lo

1

0

2

1

3

2

hi

1

3

Next: lo=0 hi=3

lo

1

0

mid

2

1

3

2

hi

1

3

mid[1]=2 - mid element selected for comparison

Next: lo=0 hi=3

lo

1

0

mid

2

1

3

2

hi

1

3

mid[1]=2 - 2 < 3, move right

Next: lo=2 hi=3

1

0

2

1

lo

3

2

hi

1

3

Next: lo=2 hi=3

1

0

2

1

lo/mid

3

2

hi

1

3

mid[2]=3 - mid element selected for comparison

Next: lo=2 hi=3

1

0

2

1

lo/mid

3

2

hi

1

3

mid[2]=3 - 3 >= 1, move left

Next: lo=2 hi=2

1

0

2

1

lo/hi

3

2

1

3

Next: lo=2 hi=2

1

0

2

1

lo/mid/hi

3

2

1

3

mid[2]=3 - low == high, peak found

Next: lo=2 hi=2

1

0

2

1

lo/mid/hi

3

2

1

3

mid[2]=3 - peak element confirmed

Next: lo=2 hi=2

1

0

2

1

lo/mid/hi

3

2

1

3

mid[2]=3 - peak element found

Next: lo=2 hi=2

Key Takeaways

✓ The algorithm efficiently narrows down the search space by comparing mid and mid+1 elements.

This insight is hard to see from code alone because the recursive calls and pointer updates happen implicitly.

✓ When nums[mid] < nums[mid+1], the peak must lie in the right half, otherwise in the left half.

Understanding this comparison rule is key to grasping why the algorithm eliminates half the search space each step.

✓ The search terminates when low equals high, indicating the peak element index is found.

This termination condition is subtle but critical; watching the pointers converge clarifies it.

Practice

1. What is the worst-case time complexity of the optimal modified binary search algorithm to find the minimum in a rotated sorted array with duplicates?

medium

A. O(n log n)

B. O(log n)

C. O(n)

D. O(1)

Solution

1. Step 1: Understand binary search with duplicates

   Duplicates can cause the algorithm to reduce high by one each iteration when nums[mid] == nums[high], leading to linear scan behavior.

2. Step 2: Analyze worst-case scenario

   In worst case (all elements equal), the algorithm degrades to O(n) because it may shrink high by one each time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Duplicates cause worst-case linear time [OK]

Hint: Duplicates cause worst-case linear time despite binary search [OK]

Common Mistakes:

• Assuming always O(log n)
• Confusing average and worst case

2. The following code attempts to find the k-th smallest number in an m x n multiplication table. Which line contains a subtle bug that can cause incorrect results for large inputs?

medium

A. Line 4: count = 0

B. Line 6: count += x // i # missing min with n

C. Line 8: if count >= k:

D. Line 13: mid = (low + high) // 2

Solution

1. Step 1: Identify counting logic

   The counting function must cap counts per row by n, since each row has only n elements.

2. Step 2: Analyze line 6

   Line 6 adds x // i without min(n, x // i), causing overcounting when x // i > n, leading to incorrect binary search decisions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bug causes wrong counts and incorrect final answer [OK]

Hint: Count per row capped by n to avoid overcounting [OK]

Common Mistakes:

• Forgetting min(n, x//i) in counting
• Incorrect mid calculation

3. Identify the bug in the following modified code snippet for the Minimum Days to Make m Bouquets problem:

medium

A. The feasibility function does not reset flowers count correctly.

B. Binary search boundaries are incorrectly set from 0 instead of min bloom day.

C. The initial check for m * k > n is missing, causing unnecessary computation.

D. Early stopping in feasibility function is missing, causing slower runtime.

Solution

1. Step 1: Check initial conditions

   The code lacks the check if m * k > n, which means it's impossible to make required bouquets.

2. Step 2: Consequences of missing check

   Without this, the code runs unnecessary binary search and feasibility checks, possibly returning wrong answers or timing out.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding the initial impossible case check fixes the bug. [OK]

Hint: Always check if total flowers suffice before processing [OK]

Common Mistakes:

• Forgetting impossible case check
• Misresetting flowers count in feasibility

4. What is the time complexity of the iterative fast exponentiation algorithm for computing x^n where n is a 32-bit integer?

medium

A. O(n)

B. O(n log n)

C. O(log n)

D. O(1)

Solution

1. Step 1: Identify loop iterations

   The algorithm halves n each iteration, so the loop runs approximately log₂(n) times.

2. Step 2: Confirm work per iteration

   Each iteration does a constant number of multiplications and divisions, so total time is O(log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Halving exponent each step -> logarithmic time [OK]

Hint: Halving exponent means O(log n) time [OK]

Common Mistakes:

• Confusing with O(n) from naive multiplication
• Assuming O(1) due to constant ops per iteration
• Thinking recursion adds extra complexity

5. Suppose the array can contain negative numbers and the target can be any integer. Which modification to the optimal binary search algorithm is necessary to correctly handle this scenario?

hard

A. No modification needed; the existing algorithm works for any integers.

B. Replace all comparisons with absolute value comparisons to handle negatives.

C. Add explicit checks for negative values before deciding which half is sorted.

D. Use a linear scan instead since binary search assumptions break with negatives.

Solution

1. Step 1: Understand impact of negative numbers

   Negative numbers do not break rotation or duplicates but affect comparison logic when deciding sorted halves.

2. Step 2: Modify comparison logic

   Explicitly check and compare values considering negatives to correctly identify sorted half and target range.

3. Step 3: Reject naive absolute value or linear scan

   Absolute values distort order; linear scan is inefficient and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Comparisons must handle negatives explicitly [OK]

Hint: Adjust comparisons to handle negatives explicitly [OK]

Common Mistakes:

• Assuming negatives don't affect comparisons
• Using absolute values incorrectly
• Switching to linear scan unnecessarily