Skip to main content

Practice ยท 1 of 2

Sliding window maximum

Implement std::vector<int> windowed_max(const std::vector<int>& v, std::size_t k) returning the maximum of every contiguous window of size k, in order. If k is 0 or v is empty return an empty vector; if k >= v.size() return a single-element vector with the overall maximum. Target O(n) with a monotonic std::deque of indices (pop from the back while the new value is greater-or-equal; pop the front when it falls out of the window).

Difficulty: intermediate

Back to lesson: Practice: Sequence container problems