Dynamic Programming21 sections · 916 units
Open in Course

Pattern - Monotonic Queue Recognition

Identifying applicable problems

Signal 1: DP transition with min/max\min/\max over a sliding window [ik,i1][i-k, i-1]. Signal 2: "Find shortest/longest subarray with some property" where property involves sums or min/max.

Signal 3: Two-pointer problems where you need efficient access to window's extreme values. Not applicable: arbitrary range (use segment tree), range sum (use prefix sums), or when window bounds are non-monotonic. The sliding window with min/max is the telltale sign. If you see a bounded range of indices, think monotonic queue.