Dynamic Programming21 sections · 916 units
Open in Course

Prefix Min Operation

Advanced technique

Some problems require "prefix min": replace f(x)f(x) with minyxf(y)\min_{y \leq x} f(y). This truncates the function, keeping only the minimum value for all yy up to xx.

In heap terms: after computing f(x)f(x) for all xx, you want the function to be non-increasing. Pop from the min-heap until it's empty, leaving only the max-heap. This operation changes the function shape but preserves the slope-change representation. Use it when constraints force monotonicity.