float('inf')len(lookup) instead of len(lookup.values())
values() builds a view object—unneeded work every loop.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: