Dynamic Programming21 sections · 916 units
Open in Course

Challenge: Online vs Offline

Query order matters

Monotonic queue works online: process elements left to right, answer queries as they arrive. Some problems allow offline: collect all queries, sort cleverly, answer in better order.

Example: if queries come with variable kk values, sort queries by kk, adjust window sizes as needed. Online requires O(n)O(n) per query. Offline might allow O(n+q)O(n + q) total with careful ordering. Online algorithms process elements one at a time with no future knowledge. Offline can reorder for efficiency.