Prefix-Sum

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

LeetCode 4051 note: prefix sums, complement counting, range counting, and the k = 0 edge case

LeetCode 2218 note: piles are taken from the top, so taking x coins is worth a prefix sum; a grouped knapsack with dp[j] = the best value taking j coins so far, enumerating how many from each pile

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 327 note: prefix sums plus merge sort counting with two pointers bounding a range, and a log of retyping it over a dozen times

LeetCode 3548 note: try each horizontal cut (transpose for vertical); the difference must equal a cell on the larger side, and a one-row or one-column side can only drop an end cell, while any cell works otherwise

LeetCode 2382 note: work backward so removals become additions; the Union-Find root stores the segment sum, and the maximum only grows

LeetCode 3919 note: walk one step at a time, each costing 1 (when the next index is the closest) or the gap; jumping is never cheaper, so answer queries with prefix sums

LeetCode 3904 note: the first index where the prefix maximum minus the suffix minimum is <= k; build the suffix minimum right to left first

LeetCode 3903 note: the first index where the prefix maximum minus the suffix minimum is <= k; build the suffix minimum right to left first

LeetCode 3900 note: equal prefix differences mean balanced; a substring off by 2 also works if a swappable character exists outside, and keeping the two earliest positions per difference is enough