when problem is related to finding ≥
When the problem asks to find the first index where value ≥ target → use:
bisect.bisect_left(arr, target)
else we use bisect_right for ≤ but have to add a -1
| Goal | Expression |
|---|---|
First index where arr[i] ≥ x |
bisect_left(arr, x) |
Last index where arr[i] < x |
bisect_left(arr, x) - 1 ✅ |
First index where arr[i] > x |
bisect_right(arr, x) |
Last index where arr[i] ≤ x |
bisect_right(arr, x) - 1 ✅ |
cache = [
[
[-1] * (N+1) # k
for _ in range(N) # j
] for _ in range(N) # i
]
For 1D lists:
[0] * N and [0 for _ in range(N)] are the same for all practical purposes with numbers.For 2D lists:
NEVER do [[0] * N] * N for a 2D list!
This creates N references to the same row, so changes to one row affect all rows.
Instead, always use a list comprehension for 2D lists:
dp = [[0] * N for _ in range(N)]