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.
This approach utilizes a sliding window to find all valid continuous subarrays.
We maintain a window from position 'start' to 'end'. As we iterate over the elements, we adjust the 'start' position to ensure all elements within the window meet the condition 0 <= |nums[i1] - nums[i2]| <= 2. For each position 'end', we extend the window to the right and calculate the number of valid subarrays ending at 'end'.
The function continuous_subarrays computes the total number of continuous subarrays by using two pointers, 'start' and 'end'. For each new element at 'end', it checks the subarrays that end in this position and calculates how many of them are valid by adjusting 'start'.
Time Complexity: O(n) because each element is processed at most twice, once by 'start' and once by 'end'.
Space Complexity: O(1) since no additional data structures are used besides basic variables.
A naive solution involves examining all subarrays within the array.
For every possible starting index, calculate every ending index and check if the subarray between these indices forms a continuous subarray. This solution is less efficient but can serve as a baseline check for correctness.
In the function continuousSubarrays, nested loops are used to explore every possible subarray. For each subarray, a check is performed to verify if all elements meet the required continuous condition.
Time Complexity: O(n^3) due to triple looping over the array to check all subarrays.
Space Complexity: O(1) as no extra space is used beyond variables.
We can use two pointers, i and j, to maintain the left and right endpoints of the current subarray, and use an ordered list to maintain all elements in the current subarray.
Iterate through the array nums. For the current number nums[i] we're iterating over, we add it to the ordered list. If the difference between the maximum and minimum values in the ordered list is greater than 2, we then loop to move the pointer i to the right, continuously removing nums[i] from the ordered list, until the list is empty or the maximum difference between elements in the ordered list is not greater than 2. At this point, the number of uninterrupted subarrays is j - i + 1, which we add to the answer.
After the iteration, return the answer.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array nums.
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) because each element is processed at most twice, once by 'start' and once by 'end'. Space Complexity: O(1) since no additional data structures are used besides basic variables. |
| Brute Force Approach | Time Complexity: O(n^3) due to triple looping over the array to check all subarrays. Space Complexity: O(1) as no extra space is used beyond variables. |
| Ordered List + Two Pointers | — |
| Monotonic queue + Two Pointers | — |
| 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 |
Continuous Subarrays | Detailed Approaches | Time Complexity | Leetcode 2762 | codestorywithMIK • codestorywithMIK • 11,369 views views
Watch 9 more video solutions →Practice Continuous Subarrays with our built-in code editor and test cases.
Practice on FleetCode