Dynamic Programming21 sections · 916 units
Open in Course

Longest Continuous Subarray - Problem Statement

With absolute diff constraint

Find longest subarray where max. Min limit\leq limit. Need to track both max AND min in the window. Use two monotonic queues: one decreasing (for max), one increasing (for min). Expand window right. If max. Min > limit, shrink from left until valid. Update both queues on shrink. Time: O(n)O(n).

Time complexity: O(n)O(n). Each element enters and leaves each queue once. This is a classic two-queue pattern. Two queues work independently. The max queue and min queue together bound the range of values in the window.

Space complexity: O(k)O(k) for the two deques.