Watch 10 video solutions for Continuous Subarrays, a medium level problem involving Array, Queue, Sliding Window. This walkthrough by codestorywithMIK has 11,369 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:
i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.Return the total number of continuous subarrays.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [5,4,2,4] Output: 8 Explanation: Continuous subarray of size 1: [5], [4], [2], [4]. Continuous subarray of size 2: [5,4], [4,2], [2,4]. Continuous subarray of size 3: [4,2,4]. There are no subarrys of size 4. Total continuous subarrays = 4 + 3 + 1 = 8. It can be shown that there are no more continuous subarrays.
Example 2:
Input: nums = [1,2,3] Output: 6 Explanation: Continuous subarray of size 1: [1], [2], [3]. Continuous subarray of size 2: [1,2], [2,3]. Continuous subarray of size 3: [1,2,3]. Total continuous subarrays = 3 + 2 + 1 = 6.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109Problem Overview: Given an integer array nums, count the number of contiguous subarrays where the difference between the maximum and minimum elements is at most 2. For every subarray you consider, the constraint max(nums[i..j]) - min(nums[i..j]) ≤ 2 must hold.
Approach 1: Brute Force (O(n²) time, O(1) space)
The straightforward solution checks every possible subarray. Start an index i, expand the end index j, and track the current minimum and maximum while iterating. If max - min becomes greater than 2, stop extending that subarray because any longer subarray starting at i will also violate the constraint. Each valid extension contributes one to the answer. This approach is easy to reason about and demonstrates the constraint clearly, but the nested iteration leads to O(n²) time in the worst case.
Approach 2: Sliding Window with Monotonic Queues (O(n) time, O(n) space)
The optimal solution maintains a dynamic window using the sliding window technique. Two pointers left and right represent the current window. The challenge is efficiently tracking the minimum and maximum values as the window grows and shrinks. Use two monotonic queues: one decreasing deque to store candidates for the maximum and one increasing deque for the minimum.
When you expand the window by moving right, push the element into both deques while preserving their monotonic order. The front of each deque always represents the current window's max and min. If max - min > 2, shrink the window by moving left and removing elements from the deque fronts when they leave the window. For every valid position of right, all subarrays ending at right and starting between left and right are valid, contributing right - left + 1 to the count.
This approach processes each element at most twice (once entering the window and once leaving), resulting in O(n) time complexity with O(n) auxiliary space for the deques. It combines ideas from array processing and monotonic data structures to maintain window constraints efficiently.
Recommended for interviews: The sliding window with monotonic queues is the expected solution. Interviewers want to see that you recognize the constraint depends only on the window's min and max, then maintain those values efficiently while adjusting two pointers. Brute force shows you understand the problem definition, but the linear-time window technique demonstrates strong algorithmic optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Useful for understanding the constraint and verifying correctness on small inputs |
| Sliding Window with Monotonic Queues | O(n) | O(n) | Best choice for large arrays where maintaining window min and max efficiently is required |