Binary-Search

LeetCode 1011 note: binary search on the answer over [max(weights), sum(weights)], checking the day count by filling greedily in order

One-dimensional DP, state-machine DP, DP with a monotonic deque, interval scheduling DP after sorting, deduplicated subsequence counting, and DP-tagged problems where an observation or greedy is faster

Interval DP (choose the last step / merge equal ends), partition DP into k segments, palindrome tables plus partitioning, and memoizing the whole state when it is too tangled to split

Lower / upper bound, binary search on the answer, k-th smallest, integer roots, and why the two interval styles must not be mixed

LeetCode 719 note: binary search on the distance, counting pairs with distance <= mid using a sliding window

LeetCode 1292 note: 2D prefix sums plus binary search on the side length; never mix the two binary search styles

LeetCode 410 note: binary search the answer; for a cap mid, greedily fill each segment to count the fewest segments, and mid works if that count is <= k

LeetCode 1235 note: sort jobs by end time with best[j] = best profit using the first j jobs; taking job j binary-searches the last job ending <= its start

LeetCode 2141 note: a battery longer than the average can only serve one computer, so remove it with that computer and average the rest, using strict greater-than

LeetCode 902 note: digit DP with state (pos, tight, started); before starting, a position can be skipped, representing numbers with fewer digits than n

LeetCode 3932 note: the answer is floor(r^(1/k)) - floor((l-1)^(1/k)); take roots with integer binary search and count 0 too

LeetCode note for Longest Increasing Subsequence, rebuilt from the original learning note