DSA problem
Continuous Subarrays
You are given a 0-indexed integer array nums. A subarray of nums is called continuous if for every pair of indices i, j in the subarray, |nums[i] - nums[j]| <= 2. Equivalently, the difference between the maximum and the minimum element of the subarray is at most 2. Return the total number of continuous subarrays.
Notice that the property "max minus min is at most 2" is monotone with respect to window growth: if a window of [l, r] is valid, every sub-window contained in it is also valid. This monotonicity is what makes a sliding window applicable. We will expand r step by step and shrink l only when the window becomes invalid.
To check the current max and min in O(1) amortized time as the window slides, we use two monotonic deques. One deque holds indices whose values are monotonically decreasing from front to back, so its front is the running maximum. The other deque holds indices whose values are monotonically increasing, so its front is the running minimum. Both deques are updated whenever we push a new r and whenever we shrink l past their fronts.
For every valid right end r, the number of valid subarrays ending at r is r - l + 1 because all left endpoints from l to r produce valid windows. Summing this quantity across all r yields the answer. The algorithm runs in O(n) time and O(n) space.
Examples
nums = [5,4,2,4]8nums = [1,2,3]6nums = [1,5,1]3Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- A subarray is continuous when its max minus its min is at most 2.
- Return the count as a 64-bit integer.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.