What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Binary Search Boundary

Builds on Lower Bound, which you haven’t finished yet.

P2MediumBuilt on Lower Bound~4 min speedrun

Peak Finding (Bitonic Binary Search)

Built on

Lower BoundThe check compares a value with the next value, so the search works on values that are not sorted, when they rise and then fall.

The problem

Peak Index in a Mountain Array (LC 852)(opens leetcode.com)

You're given a mountain array arr of length n: its values climb up to one peak and then descend.

Return the index of that peak.

Solve it in O(log n) time.

Example 1

Input:arr = [0,1,0]

Output:1

The peak element is 1 at index 1.

Extrema Search

list that rises and falls ➔ is the value falling after i? ➔ an index holding a peak

Spot it when: The statement asks for any peak, the top of a mountain or a local maximum of a list that is not sorted, and the answer is an index.

Extrema Search

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Invariant: A peak is always at an index from lo to hi: arr[lo - 1] < arr[lo] (or lo == 0), and arr[hi + 1] < arr[hi] (or hi is the last index).

Comparing arr[mid] with arr[mid + 1] tells which side holds a peak. If the values fall, a peak is at mid or to its left, so keep mid with hi = mid. If the values rise, a peak is to the right of mid, so skip mid with lo = mid + 1. At the start a peak exists from lo = 0 to hi = n - 1, because a position outside the list counts as smaller than every value. Each step keeps it there: hi = mid is used only when arr[mid] > arr[mid + 1], and lo = mid + 1 only when the values rise after mid. So the index where lo == hi is a peak. The search returns one peak, not always the highest, and it needs every two neighbouring values to differ, as Peak Index in a Mountain Array (LC 852) and Find Peak Element (LC 162) guarantee. The trap is hi = n: the check reads arr[mid + 1], so the last candidate is n - 2, and hi = n - 1 is one past it.

See it run

Extrema Search, step by step

lo 0hi 9mid -

Each column is one index. T means the values fall after that index, and F means they do not. The last column has no check, because it has no next value.

lo the left end of the range. Every candidate before lo is False.
hi the right end of the range. hi is the last index when no check is True, and it is never tested.
mid the candidate that this pass tests
mid = lo mid and lo are the same candidate
answer the index of a peak

Start: lo = 0 and hi = 9. The answer is somewhere from lo to hi, and hi is never tested.

arr[i]

1lo

2hi

is_falling(i)

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Setting hi = n while the check reads arr[i + 1]
Mistake
```
hi = n
```
Fix
```
hi = n - 1
```
What happens: The check reads arr[mid + 1], so the last candidate is n - 2. With hi = n, the candidates run up to n - 1. The check for n - 1 reads arr[n], which does not exist, and Python raises an IndexError. For arr = [1, 2, 3], the first check is False, so lo = 2. The next mid is 2, and the check reads arr[3].
Example: arr = [1, 2, 3]
Mistake: raises IndexErrorFix: returns 2
Gotcha 2: Using the check when two neighbouring values can be equal
Mistake
```
peak = peakIndexInMountainArray(arr)
```
Fix
```
peak = first_strict_peak(arr)
```
What happens: The check arr[mid] > arr[mid + 1] is False when the two values are equal, so the search moves right without knowing which side holds a peak. For arr = [3, 3, 1, 2], the first check is arr[1] > arr[2], which is True, so hi = 1. The second check is arr[0] > arr[1], which is 3 > 3 and False, so lo = 1. The call returns index 1, but its left neighbour is also 3, so index 1 is not a peak. The only peak is index 3. When a list can have equal neighbours, scan it from left to right and test both neighbours of each index.
Example: arr = [3, 3, 1, 2]
Mistake: returns 1Fix: returns 3
Gotcha 3: Returning the value instead of the index
Mistake
```
return arr[binary_search_lower_bound(lo, hi, is_falling)]
```
Fix
```
return binary_search_lower_bound(lo, hi, is_falling)
```
What happens: Lower Bound returns an index. The problem asks for the index of the peak. Returning arr[index] gives the height of the peak, which is a different number.
Example: arr = [0, 10, 5, 2]
Mistake: returns 10Fix: returns 1
Gotcha 4: In the grid, comparing a cell with its left and right neighbours at the same time
Mistake
```
return mat[r][col] > mat[r][col + 1] or mat[r][col] > mat[r][col - 1]
```
Fix
```
return mat[r][col] > mat[r][col + 1]
```
What happens: This mistake is in the grid code of the section A second worked check: a peak in a grid. The check must ask about the right neighbour only. With or, a column answers True when it is larger than its left neighbour, even when its right neighbour is larger. Then hi = mid throws away the columns on the right, and a peak may be there. For column 0, col - 1 is -1, and Python reads the last column without an error.
Example: mat = [[5, 8, 4], [0, 6, 7], [1, 3, 2]]
Mistake: returns [0, 0]Fix: returns [0, 1]
Gotcha 5: In the grid, comparing the first cell of the column instead of its largest cell
Mistake
```
return mat[0][col] > mat[0][col + 1]
```
Fix
```
return mat[r][col] > mat[r][col + 1]
```
What happens: This mistake is in the grid code of the section A second worked check: a peak in a grid. The argument that a peak lies to the right works only for the largest value of the column. The first cell of a column can be smaller than its right neighbour while a larger cell of the same column is a peak. The search then moves to the wrong side, and the cell it returns may not be a peak.
Example: mat = [[5, 0, 3], [8, 9, 7], [6, 2, 4]]
Mistake: returns [1, 2]Fix: returns [1, 1]

Not this one if…

The list is sorted and you look for where a value goes, as in Search Insert Position (LC 35): the check compares a value with target, not with the value next to it. See Lower Bound
The values do not rise and fall back smoothly: a sorted array was shifted, so there is one sudden drop from the largest to the smallest value, as in Find Minimum in Rotated Sorted Array (LC 153). See Rotated Array

Theory

The question we build

What we know

A peak is an index whose value is larger than both of its neighbours.

What the problem gives us

The input is arr. We return the index of a peak.

The question we build

We ask each index one yes-or-no question: "do the values fall after i?" The check compares arr[i] with arr[i + 1], so the last index is not a candidate. We use arr = [0, 10, 5, 2]. The candidates are the indices 0, 1 and 2. The answers are False, True, True. The first True is at index 1, and arr[1] is 10, the top.

arr[i]

is_falling(i)

arr[3] is not a candidate. The check would read arr[4], which does not exist.

Narrowing down to the template

The top is the first True, so the call is binary_search_lower_bound(0, n - 1, is_falling).

Step 1: Linear scan

The top is the first index where the next value is not larger. The scan moves to the right while the values rise.

Step 1: Linear scanPython

1		def peak_scan(arr):
2		i = 0
3		while i < len(arr) - 1 and arr[i] < arr[i + 1]:
4		i += 1 # keep moving while the values rise
5		return i

Cost: O(N) checks, where N is the number of values.

Step 2: Lower Bound on the slope

On a mountain, the question "do the values fall after i?" reads False, False, ..., True, True. So Lower Bound finds the first True, which is the top. A list with several peaks does not read that way. The section Two kinds of input below shows what the search returns there.

Step 2: Lower Bound on the slopePython

1		def find_peak(arr):
2		n = len(arr)
3
4		def is_falling(i):
5		return arr[i] > arr[i + 1]
6
7		lo = 0
8		hi = n - 1
9		return binary_search_lower_bound(lo, hi, is_falling)

Cost: O(log N) checks.

Item	Linear scan	Lower Bound on the slope
`arr[i] < arr[i + 1]` while moving	`is_falling(i)`	The scan asks if the values still rise. The check asks the opposite question.
moves to the first index where the values stop rising	an index holding a peak	On a mountain this is the first True. With several peaks, the search can return a different peak than the scan.

The shorter version

The shorter versionPython

1		import bisect
2
3		def find_peak_short(arr):
4		n = len(arr)
5		return bisect.bisect_left(range(n - 1), True, key=lambda i: arr[i] > arr[i + 1])

range(n - 1) holds the candidates 0 to n - 2. When no candidate is True, bisect_left returns n - 1, the same as the template. This form needs Python 3.10 or later, because of key=.

Two kinds of input

A mountain: Peak Index in a Mountain Array (LC 852). The values rise, then fall. The row of is_falling is False…False True…True, and the first True is the top.

Any list where neighbours differ: Find Peak Element (LC 162). The list can have several peaks. The row below is False, True, False, True, so it is not False…False True…True. The search still ends at a peak, because the invariant holds at every step. The scan returns index 1, and the search returns index 3. Both are peaks.

arr[i]

is_falling(i)

arr = [1, 3, 2, 4, 0]. Two peaks: index 1 and index 3. The search returns index 3.

A second worked check: a peak in a grid

Find a Peak Element II (LC 1901) asks for a cell that is larger than its four neighbours. A cell outside the grid counts as smaller. The candidates are the columns. For one column, find the row of its largest value. Then compare that cell with the cell to its right.

Code / Blueprint

def find_peak_grid(mat):
    rows = len(mat)
    cols = len(mat[0])
 
    def row_of_largest_in(col):
        best_row = 0
        for r in range(rows):
            if mat[r][col] > mat[best_row][col]:
                best_row = r
        return best_row
 
    def beats_right_neighbor(col):
        r = row_of_largest_in(col)
        return mat[r][col] > mat[r][col + 1]
 
    lo = 0
    hi = cols - 1                               # candidate columns are 0 .. cols - 2, because the check reads column col + 1
    col = binary_search_lower_bound(lo, hi, beats_right_neighbor)
    return [row_of_largest_in(col), col]

Let r be the row of the largest value of column col. No cell above or below mat[r][col] in that column is larger, so only its right neighbour matters. If mat[r][col] is larger than its right neighbour, a peak exists in column col or to its left. If it is not, a peak exists to the right. This only tells which side holds a peak. It does not make mat[r][col] a peak. When no column beats its right neighbour, the last column holds a peak. The cost is O(R log C), with R rows and C columns: one scan of a column for each check.

For [[1, 4], [3, 2]], the code returns [1, 0], the cell with 3. LeetCode lists [0, 1], and it accepts any peak.

Real measurements: noisy values

Measured values contain measurement error. One comparison between two close values can point the wrong way because of the error, not because the true curve bends there. Averaging each value with its neighbours before the search reduces this risk.

Say it in an interview

A rehearsed way to say the whole approach out loud, in about 60 seconds, for Peak Index in a Mountain Array (LC 852):

"Extrema Search is Lower Bound with the check arr[i] > arr[i + 1], which asks if the values fall after i. If they fall, a peak is at mid or to its left, so I set hi = mid. If they rise, a peak is to the right, so I set lo = mid + 1. A peak stays from lo to hi, so the index where they meet is a peak, but not always the highest one. The check reads the next value, so I call binary_search_lower_bound(0, n - 1, is_falling), and neighbouring values must differ. The time is O(log N) and the space is O(1)."

Common Questions

How do I find the lowest point of a list that falls and then rises?: Reverse the comparison. The check arr[i] < arr[i + 1] is False while the values fall and True from the lowest point on, so the same call returns an index holding a lowest value. For [5, 3, 1, 2, 4] it returns index 2.
How does the same check find the lowest cost in Minimum Cost to Make Array Equal (LC 2448)?: The total cost of a target value falls and then rises. The check cost(x) <= cost(x + 1) is False while the cost still falls and True from the lowest cost on. The candidates are the target values from the smallest to the largest number in the array.
How do I find a given value in Find in Mountain Array (LC 1095)?: Run three searches. The first finds the peak. The second searches the rising side for the target. The third searches the falling side, where a value larger than the target means the target is to the right, so that comparison is flipped.

Practice

Canonical LeetCode:Peak Index in a Mountain Array (LC 852)Find Peak Element (LC 162)Find a Peak Element II (LC 1901)Find in Mountain Array (LC 1095)Minimum Cost to Make Array Equal (LC 2448)

Many books teach Extrema Search as its own loop. The loop compares arr[mid] with arr[mid + 1], and asks if the values still rise. This course reuses the Lower Bound loop and asks the opposite question: do the values fall?

The classic loop

Old Way

Python

1	from typing import List
2
3	def peakIndexInMountainArray(arr: List[int]) -> int:
4	"""Peak Index in a Mountain Array, the classic loop that compares `arr[mid]` with `arr[mid + 1]`.
5	Time: O(log N) \| Space: O(1)
6	"""
7	lo, hi = 0, len(arr) - 1
8
9	while lo < hi:
10	mid = lo + (hi - lo) // 2
11	if arr[mid] < arr[mid + 1]:
12	lo = mid + 1 # Ascending slope; peak lies right
13	else:
14	hi = mid # Descending slope; mid could be peak
15
16	return lo

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = 0, len(arr) - 1	lo = 0 and hi = n - 1	The numbers are the same. In the template, `hi` is one past the last candidate, and the last candidate is `n - 2`.
while lo < hi:	while lo < hi: (inside the template)	The same loop condition.
if arr[mid] < arr[mid + 1]: lo = mid + 1	is_falling(mid) is False, so lo = mid + 1	The classic loop asks if the values rise. The check asks the opposite question.
else: hi = mid	is_falling(mid) is True, so hi = mid	Keep `mid`, because `mid` may be the peak.
return lo	return lo (inside the template)	`lo == hi` is a peak.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It is the same loop. The template only gives the loop a name and the check a function.

Gotchas of the classic loop

Gotchas1 of 5

The trap
Gotcha 1: Looping while lo <= hi instead of while lo < hi
Mistake
```
while lo <= hi:
```
Fix
```
while lo < hi:
```
What happens: When lo == hi, that index is a peak, and the search is done. while lo <= hi runs one more round with mid == lo == hi. The peak is higher than arr[mid + 1], so the loop sets hi = mid again. Nothing changes, so the loop never ends. If the peak is the last index, arr[mid + 1] raises an IndexError instead.
Example: Peak Index in a Mountain Array (LC 852): arr = [0, 1, 0]
Mistake: the loop never endsFix: returns 1
Gotcha 2: Rounding mid up so mid + 1 leaves the array
Mistake
```
mid = lo + (hi - lo + 1) // 2
```
Fix
```
mid = lo + (hi - lo) // 2
```
What happens: The loop compares arr[mid] with arr[mid + 1]. Rounding down keeps mid below hi, so mid + 1 is always a valid index. Rounding up makes mid == hi when two indices are left. Then arr[mid + 1] reads past the end, and Python raises an IndexError.
Example: arr = [1, 2]
Mistake: raises IndexErrorFix: returns 1
Gotcha 3: Expecting the search to return the highest peak
What happens: Find Peak Element (LC 162) accepts any peak, and its array need not be one mountain. The search walks toward a higher neighbour, so it always reaches some peak. That peak is not always the highest value in the array. When a problem needs the maximum itself, a binary search on the slope does not find it.
Gotcha 4: Searching the falling side with the rising comparison
What happens: Find in Mountain Array (LC 1095) takes three searches. The first finds the peak. The second searches the rising side, where the values go up. The third searches the falling side, where the values go down. On the falling side, a value larger than target means the target is to the right, so the comparison is flipped.
Gotcha 5: Using the slope test when neighbours can be equal
What happens: The test arr[mid] < arr[mid + 1] needs neighbours that differ. When arr[mid] == arr[mid + 1], the values do not say which side holds a peak. Find Peak Element (LC 162) and Peak Index in a Mountain Array (LC 852) forbid equal neighbours for this reason. When equal neighbours are allowed, scan the array from left to right instead.

Earlier signals

Values rise and then fall (a mountain), or any local peak will do, and you can compare neighbours.

Earlier description

If arr[mid] < arr[mid + 1], the values are still rising at mid, so walking right must reach a peak before the array ends (the outside counts as lower): lo = mid + 1. Otherwise mid is on a falling slope or is the peak itself, so keep it with hi = mid. Each step keeps a rising edge on the left of [lo, hi] and a falling edge on its right, so a peak is always inside, and when the range shrinks to lo == hi that index is a peak. The trap is the loop condition: while lo < hi stops as soon as one index is left. With lo <= hi, the loop reaches lo == hi on the peak, arr[mid] > arr[mid + 1] sets hi = mid again, and it never ends (when the peak is the last index, arr[mid + 1] reads past the end instead).

Earlier template

Python

1	from typing import Callable, List
2
3	def climb(lo: int, hi: int, is_rising: Callable[[int], bool]) -> int:
4	"""Extrema Search: an index in [lo, hi] where the values stop rising, which is a peak.
5	is_rising(mid) is True when the value at mid is lower than the value at mid + 1.
6	The loop calls is_rising(mid) only with mid < hi, so it may read the value at mid + 1.
7	Precondition: the values rise and then fall, and two neighbouring values are equal only at the peak.
8	N = hi - lo + 1. T = the cost of one is_rising call.
9	Time: O(T * log N) \| Space: O(1)
10	"""
11	while lo < hi:
12	mid = lo + (hi - lo) // 2
13	if is_rising(mid):
14	lo = mid + 1 # Ascending slope; peak lies right
15	else:
16	hi = mid # Descending slope; mid could be peak
17
18	return lo
19
20
21	# Peak Index in a Mountain Array (LC 852): the template above, with lo = 0, hi = len(arr) - 1 and is_rising(mid) = arr[mid] < arr[mid + 1]. That check costs O(1), so O(log N) time and O(1) space. The step debugger runs this code.
22	def peakIndexInMountainArray(arr: List[int]) -> int:
23	lo, hi = 0, len(arr) - 1
24
25	while lo < hi:
26	mid = lo + (hi - lo) // 2
27	if arr[mid] < arr[mid + 1]:
28	lo = mid + 1 # Ascending slope; peak lies right
29	else:
30	hi = mid # Descending slope; mid could be peak
31
32	return lo

Earlier invariant

arr[lo - 1] < arr[lo] (or lo == 0) and arr[hi] > arr[hi + 1] (or hi is the last index), so [lo, hi] always holds a peak.

Earlier direction

unimodal / mountain array ➔ local derivative comparison ➔ climb peak

Earlier gotchas

Looping while lo <= hi instead of while lo < hi

When lo == hi, that index is a peak, and the search is done. while lo <= hi runs one more round with mid == lo == hi. The peak is higher than arr[mid + 1], so the loop sets hi = mid again. Nothing changes, so the loop never ends. If the peak is the last index, arr[mid + 1] raises an IndexError instead.

Rounding mid up so mid + 1 leaves the array

The loop compares arr[mid] with arr[mid + 1]. Rounding down keeps mid below hi, so mid + 1 is always a valid index. Rounding up makes mid == hi when two indices are left. Then arr[mid + 1] reads past the end, and Python raises an IndexError.

Expecting the search to return the highest peak

Find Peak Element (LC 162) accepts any peak, and its array need not be one mountain. The search walks toward a higher neighbour, so it always reaches some peak. That peak is not always the highest value in the array. When a problem needs the maximum itself, a binary search on the slope does not find it.

Searching the falling side with the rising comparison

Find in Mountain Array (LC 1095) takes three searches. The first finds the peak. The second searches the rising side, where the values go up. The third searches the falling side, where the values go down. On the falling side, a value larger than target means the target is to the right, so the comparison is flipped.

Using the slope test when neighbours can be equal

The test arr[mid] < arr[mid + 1] needs neighbours that differ. When arr[mid] == arr[mid + 1], the values do not say which side holds a peak. Find Peak Element (LC 162) and Peak Index in a Mountain Array (LC 852) forbid equal neighbours for this reason. When equal neighbours are allowed, scan the array from left to right instead.

Theory Context•Binary Search Boundary

Builds on Lower Bound, which you haven’t finished yet.

P2MediumBuilt on Lower Bound~4 min speedrun

Peak Finding (Bitonic Binary Search)

Built on

Lower BoundThe check compares a value with the next value, so the search works on values that are not sorted, when they rise and then fall.

The problem

Peak Index in a Mountain Array (LC 852)(opens leetcode.com)

You're given a mountain array arr of length n: its values climb up to one peak and then descend.

Return the index of that peak.

Solve it in O(log n) time.

Example 1

Input:arr = [0,1,0]

Output:1

The peak element is 1 at index 1.

Extrema Search

list that rises and falls ➔ is the value falling after i? ➔ an index holding a peak

Spot it when: The statement asks for any peak, the top of a mountain or a local maximum of a list that is not sorted, and the answer is an index.

Extrema Search

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Invariant: A peak is always at an index from lo to hi: arr[lo - 1] < arr[lo] (or lo == 0), and arr[hi + 1] < arr[hi] (or hi is the last index).

See it run

Extrema Search, step by step

lo 0hi 9mid -

Each column is one index. T means the values fall after that index, and F means they do not. The last column has no check, because it has no next value.

lo the left end of the range. Every candidate before lo is False.
hi the right end of the range. hi is the last index when no check is True, and it is never tested.
mid the candidate that this pass tests
mid = lo mid and lo are the same candidate
answer the index of a peak

Start: lo = 0 and hi = 9. The answer is somewhere from lo to hi, and hi is never tested.

arr[i]

1lo

2hi

is_falling(i)

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Setting hi = n while the check reads arr[i + 1]
Mistake
```
hi = n
```
Fix
```
hi = n - 1
```
What happens: The check reads arr[mid + 1], so the last candidate is n - 2. With hi = n, the candidates run up to n - 1. The check for n - 1 reads arr[n], which does not exist, and Python raises an IndexError. For arr = [1, 2, 3], the first check is False, so lo = 2. The next mid is 2, and the check reads arr[3].
Example: arr = [1, 2, 3]
Mistake: raises IndexErrorFix: returns 2
Gotcha 2: Using the check when two neighbouring values can be equal
Mistake
```
peak = peakIndexInMountainArray(arr)
```
Fix
```
peak = first_strict_peak(arr)
```
What happens: The check arr[mid] > arr[mid + 1] is False when the two values are equal, so the search moves right without knowing which side holds a peak. For arr = [3, 3, 1, 2], the first check is arr[1] > arr[2], which is True, so hi = 1. The second check is arr[0] > arr[1], which is 3 > 3 and False, so lo = 1. The call returns index 1, but its left neighbour is also 3, so index 1 is not a peak. The only peak is index 3. When a list can have equal neighbours, scan it from left to right and test both neighbours of each index.
Example: arr = [3, 3, 1, 2]
Mistake: returns 1Fix: returns 3
Gotcha 3: Returning the value instead of the index
Mistake
```
return arr[binary_search_lower_bound(lo, hi, is_falling)]
```
Fix
```
return binary_search_lower_bound(lo, hi, is_falling)
```
What happens: Lower Bound returns an index. The problem asks for the index of the peak. Returning arr[index] gives the height of the peak, which is a different number.
Example: arr = [0, 10, 5, 2]
Mistake: returns 10Fix: returns 1
Gotcha 4: In the grid, comparing a cell with its left and right neighbours at the same time
Mistake
```
return mat[r][col] > mat[r][col + 1] or mat[r][col] > mat[r][col - 1]
```
Fix
```
return mat[r][col] > mat[r][col + 1]
```
What happens: This mistake is in the grid code of the section A second worked check: a peak in a grid. The check must ask about the right neighbour only. With or, a column answers True when it is larger than its left neighbour, even when its right neighbour is larger. Then hi = mid throws away the columns on the right, and a peak may be there. For column 0, col - 1 is -1, and Python reads the last column without an error.
Example: mat = [[5, 8, 4], [0, 6, 7], [1, 3, 2]]
Mistake: returns [0, 0]Fix: returns [0, 1]
Gotcha 5: In the grid, comparing the first cell of the column instead of its largest cell
Mistake
```
return mat[0][col] > mat[0][col + 1]
```
Fix
```
return mat[r][col] > mat[r][col + 1]
```
What happens: This mistake is in the grid code of the section A second worked check: a peak in a grid. The argument that a peak lies to the right works only for the largest value of the column. The first cell of a column can be smaller than its right neighbour while a larger cell of the same column is a peak. The search then moves to the wrong side, and the cell it returns may not be a peak.
Example: mat = [[5, 0, 3], [8, 9, 7], [6, 2, 4]]
Mistake: returns [1, 2]Fix: returns [1, 1]

Not this one if…

The list is sorted and you look for where a value goes, as in Search Insert Position (LC 35): the check compares a value with target, not with the value next to it. See Lower Bound
The values do not rise and fall back smoothly: a sorted array was shifted, so there is one sudden drop from the largest to the smallest value, as in Find Minimum in Rotated Sorted Array (LC 153). See Rotated Array

Theory

The question we build

What we know

A peak is an index whose value is larger than both of its neighbours.

What the problem gives us

The input is arr. We return the index of a peak.

The question we build

arr[i]

is_falling(i)

arr[3] is not a candidate. The check would read arr[4], which does not exist.

Narrowing down to the template

The top is the first True, so the call is binary_search_lower_bound(0, n - 1, is_falling).

Step 1: Linear scan

The top is the first index where the next value is not larger. The scan moves to the right while the values rise.

Step 1: Linear scanPython

1		def peak_scan(arr):
2		i = 0
3		while i < len(arr) - 1 and arr[i] < arr[i + 1]:
4		i += 1 # keep moving while the values rise
5		return i

Cost: O(N) checks, where N is the number of values.

Step 2: Lower Bound on the slope

Step 2: Lower Bound on the slopePython

1		def find_peak(arr):
2		n = len(arr)
3
4		def is_falling(i):
5		return arr[i] > arr[i + 1]
6
7		lo = 0
8		hi = n - 1
9		return binary_search_lower_bound(lo, hi, is_falling)

Cost: O(log N) checks.

Item	Linear scan	Lower Bound on the slope
`arr[i] < arr[i + 1]` while moving	`is_falling(i)`	The scan asks if the values still rise. The check asks the opposite question.
moves to the first index where the values stop rising	an index holding a peak	On a mountain this is the first True. With several peaks, the search can return a different peak than the scan.

The shorter version

The shorter versionPython

1		import bisect
2
3		def find_peak_short(arr):
4		n = len(arr)
5		return bisect.bisect_left(range(n - 1), True, key=lambda i: arr[i] > arr[i + 1])

range(n - 1) holds the candidates 0 to n - 2. When no candidate is True, bisect_left returns n - 1, the same as the template. This form needs Python 3.10 or later, because of key=.

Two kinds of input

A mountain: Peak Index in a Mountain Array (LC 852). The values rise, then fall. The row of is_falling is False…False True…True, and the first True is the top.

arr[i]

is_falling(i)

arr = [1, 3, 2, 4, 0]. Two peaks: index 1 and index 3. The search returns index 3.

A second worked check: a peak in a grid

Code / Blueprint

def find_peak_grid(mat):
    rows = len(mat)
    cols = len(mat[0])
 
    def row_of_largest_in(col):
        best_row = 0
        for r in range(rows):
            if mat[r][col] > mat[best_row][col]:
                best_row = r
        return best_row
 
    def beats_right_neighbor(col):
        r = row_of_largest_in(col)
        return mat[r][col] > mat[r][col + 1]
 
    lo = 0
    hi = cols - 1                               # candidate columns are 0 .. cols - 2, because the check reads column col + 1
    col = binary_search_lower_bound(lo, hi, beats_right_neighbor)
    return [row_of_largest_in(col), col]

For [[1, 4], [3, 2]], the code returns [1, 0], the cell with 3. LeetCode lists [0, 1], and it accepts any peak.

Real measurements: noisy values

Say it in an interview

A rehearsed way to say the whole approach out loud, in about 60 seconds, for Peak Index in a Mountain Array (LC 852):

"Extrema Search is Lower Bound with the check arr[i] > arr[i + 1], which asks if the values fall after i. If they fall, a peak is at mid or to its left, so I set hi = mid. If they rise, a peak is to the right, so I set lo = mid + 1. A peak stays from lo to hi, so the index where they meet is a peak, but not always the highest one. The check reads the next value, so I call binary_search_lower_bound(0, n - 1, is_falling), and neighbouring values must differ. The time is O(log N) and the space is O(1)."

Common Questions

How do I find the lowest point of a list that falls and then rises?: Reverse the comparison. The check arr[i] < arr[i + 1] is False while the values fall and True from the lowest point on, so the same call returns an index holding a lowest value. For [5, 3, 1, 2, 4] it returns index 2.
How does the same check find the lowest cost in Minimum Cost to Make Array Equal (LC 2448)?: The total cost of a target value falls and then rises. The check cost(x) <= cost(x + 1) is False while the cost still falls and True from the lowest cost on. The candidates are the target values from the smallest to the largest number in the array.
How do I find a given value in Find in Mountain Array (LC 1095)?: Run three searches. The first finds the peak. The second searches the rising side for the target. The third searches the falling side, where a value larger than the target means the target is to the right, so that comparison is flipped.

Practice

Canonical LeetCode:Peak Index in a Mountain Array (LC 852)Find Peak Element (LC 162)Find a Peak Element II (LC 1901)Find in Mountain Array (LC 1095)Minimum Cost to Make Array Equal (LC 2448)

The classic loop

Old Way

Python

1	from typing import List
2
3	def peakIndexInMountainArray(arr: List[int]) -> int:
4	"""Peak Index in a Mountain Array, the classic loop that compares `arr[mid]` with `arr[mid + 1]`.
5	Time: O(log N) \| Space: O(1)
6	"""
7	lo, hi = 0, len(arr) - 1
8
9	while lo < hi:
10	mid = lo + (hi - lo) // 2
11	if arr[mid] < arr[mid + 1]:
12	lo = mid + 1 # Ascending slope; peak lies right
13	else:
14	hi = mid # Descending slope; mid could be peak
15
16	return lo

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = 0, len(arr) - 1	lo = 0 and hi = n - 1	The numbers are the same. In the template, `hi` is one past the last candidate, and the last candidate is `n - 2`.
while lo < hi:	while lo < hi: (inside the template)	The same loop condition.
if arr[mid] < arr[mid + 1]: lo = mid + 1	is_falling(mid) is False, so lo = mid + 1	The classic loop asks if the values rise. The check asks the opposite question.
else: hi = mid	is_falling(mid) is True, so hi = mid	Keep `mid`, because `mid` may be the peak.
return lo	return lo (inside the template)	`lo == hi` is a peak.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It is the same loop. The template only gives the loop a name and the check a function.

Gotchas of the classic loop

Gotchas1 of 5

The trap
Gotcha 1: Looping while lo <= hi instead of while lo < hi
Mistake
```
while lo <= hi:
```
Fix
```
while lo < hi:
```
What happens: When lo == hi, that index is a peak, and the search is done. while lo <= hi runs one more round with mid == lo == hi. The peak is higher than arr[mid + 1], so the loop sets hi = mid again. Nothing changes, so the loop never ends. If the peak is the last index, arr[mid + 1] raises an IndexError instead.
Example: Peak Index in a Mountain Array (LC 852): arr = [0, 1, 0]
Mistake: the loop never endsFix: returns 1
Gotcha 2: Rounding mid up so mid + 1 leaves the array
Mistake
```
mid = lo + (hi - lo + 1) // 2
```
Fix
```
mid = lo + (hi - lo) // 2
```
What happens: The loop compares arr[mid] with arr[mid + 1]. Rounding down keeps mid below hi, so mid + 1 is always a valid index. Rounding up makes mid == hi when two indices are left. Then arr[mid + 1] reads past the end, and Python raises an IndexError.
Example: arr = [1, 2]
Mistake: raises IndexErrorFix: returns 1
Gotcha 3: Expecting the search to return the highest peak
What happens: Find Peak Element (LC 162) accepts any peak, and its array need not be one mountain. The search walks toward a higher neighbour, so it always reaches some peak. That peak is not always the highest value in the array. When a problem needs the maximum itself, a binary search on the slope does not find it.
Gotcha 4: Searching the falling side with the rising comparison
What happens: Find in Mountain Array (LC 1095) takes three searches. The first finds the peak. The second searches the rising side, where the values go up. The third searches the falling side, where the values go down. On the falling side, a value larger than target means the target is to the right, so the comparison is flipped.
Gotcha 5: Using the slope test when neighbours can be equal
What happens: The test arr[mid] < arr[mid + 1] needs neighbours that differ. When arr[mid] == arr[mid + 1], the values do not say which side holds a peak. Find Peak Element (LC 162) and Peak Index in a Mountain Array (LC 852) forbid equal neighbours for this reason. When equal neighbours are allowed, scan the array from left to right instead.

Earlier signals

Values rise and then fall (a mountain), or any local peak will do, and you can compare neighbours.

Earlier description

Earlier template

Python

1	from typing import Callable, List
2
3	def climb(lo: int, hi: int, is_rising: Callable[[int], bool]) -> int:
4	"""Extrema Search: an index in [lo, hi] where the values stop rising, which is a peak.
5	is_rising(mid) is True when the value at mid is lower than the value at mid + 1.
6	The loop calls is_rising(mid) only with mid < hi, so it may read the value at mid + 1.
7	Precondition: the values rise and then fall, and two neighbouring values are equal only at the peak.
8	N = hi - lo + 1. T = the cost of one is_rising call.
9	Time: O(T * log N) \| Space: O(1)
10	"""
11	while lo < hi:
12	mid = lo + (hi - lo) // 2
13	if is_rising(mid):
14	lo = mid + 1 # Ascending slope; peak lies right
15	else:
16	hi = mid # Descending slope; mid could be peak
17
18	return lo
19
20
21	# Peak Index in a Mountain Array (LC 852): the template above, with lo = 0, hi = len(arr) - 1 and is_rising(mid) = arr[mid] < arr[mid + 1]. That check costs O(1), so O(log N) time and O(1) space. The step debugger runs this code.
22	def peakIndexInMountainArray(arr: List[int]) -> int:
23	lo, hi = 0, len(arr) - 1
24
25	while lo < hi:
26	mid = lo + (hi - lo) // 2
27	if arr[mid] < arr[mid + 1]:
28	lo = mid + 1 # Ascending slope; peak lies right
29	else:
30	hi = mid # Descending slope; mid could be peak
31
32	return lo

Earlier invariant

arr[lo - 1] < arr[lo] (or lo == 0) and arr[hi] > arr[hi + 1] (or hi is the last index), so [lo, hi] always holds a peak.

Earlier direction

unimodal / mountain array ➔ local derivative comparison ➔ climb peak

Earlier gotchas

Looping while lo <= hi instead of while lo < hi

Rounding mid up so mid + 1 leaves the array

Expecting the search to return the highest peak

Searching the falling side with the rising comparison

Using the slope test when neighbours can be equal