Continuous Subarrays
MedPrompt
You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:
- Let
i,i + 1, ...,jbe the indices in the subarray. Then, for each pair of indicesi <= 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] <= 109
Approaches
4 approaches with complexity analysis and trade-offs.
This approach involves generating every possible subarray, and for each one, checking if it meets the 'continuous' criteria. The criteria is that the difference between the maximum and minimum element in the subarray must be less than or equal to 2.
Algorithm
- Initialize a counter
countto 0. - Iterate through each possible start index
ifrom 0 ton-1. - For each
i, iterate through each possible end indexjfromiton-1. - For the subarray
nums[i...j], find the minimum (minVal) and maximum (maxVal) elements by iterating fromitoj. - If
maxVal - minVal <= 2, incrementcount. - After all subarrays are checked, return
count.
Walkthrough
We use two nested loops to define the start (i) and end (j) indices of all possible subarrays. For each subarray nums[i...j], we iterate through it a third time to find its minimum and maximum values. If max - min <= 2, we increment a counter. This method is simple to understand but highly inefficient due to the triple nested loops.
public class Solution { public long continuousSubarrays(int[] nums) { long count = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int minVal = Integer.MAX_VALUE; int maxVal = Integer.MIN_VALUE; // Find min and max in subarray nums[i..j] for (int k = i; k <= j; k++) { minVal = Math.min(minVal, nums[k]); maxVal = Math.max(maxVal, nums[k]); } if (maxVal - minVal <= 2) { count++; } } } return count; }}Complexity
Time
O(n^3). Three nested loops are used. The outer two loops select the subarray (`O(n^2)` pairs), and the inner loop finds the min/max in `O(n)` time.
Space
O(1). We only use a few variables to store the count, indices, min, and max.
Trade-offs
Pros
Simple to conceptualize and implement.
Requires no extra data structures.
Cons
Extremely inefficient, with a cubic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
This approach improves upon the brute-force method by avoiding the third loop. As we extend a subarray from nums[i...j] to nums[i...j+1], we can update the minimum and maximum values in constant time instead of re-scanning the entire subarray.
Algorithm
- Initialize a counter
countto 0. - Iterate through each possible start index
ifrom 0 ton-1. - For each
i, initializeminValandmaxValtonums[i]. - Start an inner loop for the end index
jfromiton-1. - In the inner loop, update
minVal = min(minVal, nums[j])andmaxVal = max(maxVal, nums[j]). - If
maxVal - minVal <= 2, incrementcount. - If
maxVal - minVal > 2, break the inner loop, as any further extension will also be invalid. - Return
count.
Walkthrough
We iterate through all possible starting points i of a subarray. For each i, we start another loop for the endpoint j, from i to the end of the array. As we expand the subarray by incrementing j, we keep track of the minimum and maximum values seen so far within nums[i...j]. If max - min <= 2, we count this subarray. If the condition is violated, we know that any further extension of the subarray from i will also be invalid, so we can break the inner loop and move to the next starting point i.
public class Solution { public long continuousSubarrays(int[] nums) { long count = 0; int n = nums.length; for (int i = 0; i < n; i++) { int minVal = nums[i]; int maxVal = nums[i]; for (int j = i; j < n; j++) { minVal = Math.min(minVal, nums[j]); maxVal = Math.max(maxVal, nums[j]); if (maxVal - minVal <= 2) { count++; } else { // If nums[i..j] is not continuous, // any subarray nums[i..k] where k > j won't be either. break; } } } return count; }}Complexity
Time
O(n^2). Two nested loops are used. The operations inside the inner loop are O(1).
Space
O(1). Only a few variables are used for tracking state.
Trade-offs
Pros
More efficient than the O(n^3) approach.
Still relatively easy to implement.
Cons
The quadratic time complexity is still too slow for the given constraints (
n <= 10^5).
This approach uses a sliding window and a balanced binary search tree (like Java's TreeMap) to maintain the elements within the current window. For each right endpoint of the window, we expand it and then shrink it from the left until the condition max - min <= 2 is met. The number of valid subarrays ending at the current right endpoint can then be calculated easily.
Algorithm
- Initialize
count = 0,left = 0, and aTreeMapto store element frequencies in the window. - Iterate
rightfrom 0 ton-1. - Add
nums[right]to theTreeMap. - While the difference between the max key and min key in the
TreeMapis greater than 2:- Decrement the frequency of
nums[left]in theTreeMap. - If the frequency becomes zero, remove the element from the
TreeMap. - Increment
left.
- Decrement the frequency of
- Add
right - left + 1tocount. - Return
count.
Walkthrough
We use a sliding window defined by [left, right]. We iterate right from 0 to n-1. For each right, we add nums[right] to a TreeMap which stores the elements in the window and their frequencies. The TreeMap allows us to find the min (firstKey()) and max (lastKey()) elements in the window in O(log k) time, where k is the number of distinct elements in the window. If max - min > 2, we shrink the window by incrementing left and removing nums[left] from the TreeMap until the condition is satisfied. Once the window [left, right] is valid, we know that all subarrays ending at right with a start index from left to right are also valid. There are right - left + 1 such subarrays, which we add to our total count.
import java.util.TreeMap; public class Solution { public long continuousSubarrays(int[] nums) { long count = 0; int n = nums.length; TreeMap<Integer, Integer> windowCounts = new TreeMap<>(); int left = 0; for (int right = 0; right < n; right++) { windowCounts.put(nums[right], windowCounts.getOrDefault(nums[right], 0) + 1); while (windowCounts.lastKey() - windowCounts.firstKey() > 2) { windowCounts.put(nums[left], windowCounts.get(nums[left]) - 1); if (windowCounts.get(nums[left]) == 0) { windowCounts.remove(nums[left]); } left++; } count += (right - left + 1); } return count; }}Complexity
Time
O(n log n). Each element is added to and removed from the `TreeMap` at most once. `TreeMap` operations take `O(log k)` time, where `k` is the window size. In the worst case, `k` can be up to `n`.
Space
O(n). In the worst case, the `TreeMap` might store all `n` elements if they are all distinct and form a valid window.
Trade-offs
Pros
Significantly more efficient than O(n^2).
Passes the time limits for the given constraints.
Cons
Logarithmic factor in time complexity due to tree operations.
Higher space complexity compared to brute-force approaches.
This is the most optimal approach, achieving linear time complexity. It uses a sliding window combined with two monotonic deques (double-ended queues). One deque maintains indices of elements in decreasing order of value to find the window's maximum in O(1) time. The other deque maintains indices in increasing order of value to find the window's minimum in O(1) time.
Algorithm
- Initialize
count = 0,left = 0, and two deques,maxDequeandminDeque. - Iterate
rightfrom 0 ton-1. - Update
maxDeque: remove indices from the tail that correspond to values less than or equal tonums[right], then addright. - Update
minDeque: remove indices from the tail that correspond to values greater than or equal tonums[right], then addright. - While
nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > 2:- If
maxDeque.peekFirst() == left, remove it. - If
minDeque.peekFirst() == left, remove it. - Increment
left.
- If
- Add
right - left + 1tocount. - Return
count.
Walkthrough
We maintain a sliding window [left, right]. We also use two deques: maxDeque to track the maximum and minDeque to track the minimum. As we iterate right from 0 to n-1, we update the deques. For maxDeque, we remove indices from the end that correspond to values smaller than or equal to nums[right], ensuring the values corresponding to indices are in decreasing order. For minDeque, we do the opposite to maintain increasing order. This way, nums[maxDeque.peekFirst()] is always the max and nums[minDeque.peekFirst()] is always the min of the current window. If max - min > 2, we shrink the window from the left by incrementing left and removing left from the deques if it's at the front. Once the window is valid, we add right - left + 1 to our total count, representing all valid subarrays ending at right.
import java.util.Deque;import java.util.LinkedList; public class Solution { public long continuousSubarrays(int[] nums) { long count = 0; int n = nums.length; Deque<Integer> maxDeque = new LinkedList<>(); Deque<Integer> minDeque = new LinkedList<>(); int left = 0; for (int right = 0; right < n; right++) { // Maintain maxDeque (indices of decreasing values) while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[right]) { maxDeque.pollLast(); } maxDeque.addLast(right); // Maintain minDeque (indices of increasing values) while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) { minDeque.pollLast(); } minDeque.addLast(right); // Shrink window if condition is violated while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > 2) { // If the leftmost element is the max/min, remove it from deque if (maxDeque.peekFirst() == left) { maxDeque.pollFirst(); } if (minDeque.peekFirst() == left) { minDeque.pollFirst(); } left++; } // Add count of valid subarrays ending at 'right' count += (right - left + 1); } return count; }}Complexity
Time
O(n). Each element's index is added to and removed from each deque at most once. The `left` and `right` pointers traverse the array once. All operations are amortized O(1).
Space
O(n). In the worst case (e.g., a strictly increasing or decreasing array), the deques can store up to `n` indices.
Trade-offs
Pros
Optimal time complexity.
Very efficient for large inputs.
Cons
The logic with two deques can be more complex to understand and implement correctly compared to other approaches.
Solutions
Solution
class Solution {public long continuousSubarrays(int[] nums) { long ans = 0; int i = 0, n = nums.length; TreeMap<Integer, Integer> tm = new TreeMap<>(); for (int j = 0; j < n; ++j) { tm.merge(nums[j], 1, Integer : : sum); while (tm.lastEntry().getKey() - tm.firstEntry().getKey() > 2) { tm.merge(nums[i], -1, Integer : : sum); if (tm.get(nums[i]) == 0) { tm.remove(nums[i]); } ++i; } ans += j - i + 1; } return ans; }}from sortedcontainers import SortedList class Solution : def continuousSubarrays ( self , nums : List [ int ]) -> int : ans = i = 0 sl = SortedList () for x in nums : sl . add ( x ) while sl [ - 1 ] - sl [ 0 ] > 2 : sl . remove ( nums [ i ]) i += 1 ans += len ( sl ) return ansclass Solution {public: long long continuousSubarrays(vector<int> &nums) { long long ans = 0; int i = 0, n = nums.size(); multiset<int> s; for (int j = 0; j < n; ++j) { s.insert(nums[j]); while (*s.rbegin() - *s.begin() > 2) { s.erase(s.find(nums[i++])); } ans += j - i + 1; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.