Prefix-Sum

LeetCode 3719 note: n is only 1500, so fix the left end and extend right, maintaining distinct odds and evens in two sets

LeetCode 2838 note: sort monsters by power, build coin prefix sums, and bisect_right per hero

LeetCode 1712 note: fix the first cut and find the valid range of the second cut with two bisects or two monotonic pointers

LeetCode 930 note: “sum exactly goal” = “sum at most goal” − “sum at most goal - 1”; or prefix sums with a hash map

LeetCode 3814 note: sort by cost with a prefix maximum of capacity, and bisect the most expensive partner for each machine

LeetCode 2968 note: after sorting, the cheapest common target for a block is its median; prefix sums give the cost in O(1), and it grows with the window, so slide

LeetCode 2875 note: strip target // sum full cycles; the remainder is smaller than one cycle, so a sliding window over two copies of nums always finds it

LeetCode 2302 note: score = sum × length with positive numbers grows with the window; shrink while the score is >= k, and right - left + 1 valid subarrays end at right

LeetCode 3413 note: the best k bags always have one end on a segment boundary; compute “left end at a segment start” and “right end at a segment end” (the latter by mirroring and reusing the same function)

LeetCode 2106 note: the harvest is always a contiguous block of fruits; covering [L, R] takes (R - L) + min(|start - L|, |R - start|) steps, so slide a window over the fruits array

LeetCode 2271 note: starting the carpet at some segment’s start is never worse; after sorting, two pointers sum the fully covered segments and count the last one partially

LeetCode 1838 note: after sorting, raising the whole window to nums[right] costs nums[right] × length − window sum; shrink the left while that exceeds k