Continuous Subarrays solution and explanation
Google
9 more videos on this problem
Continuous Subarrays | Detailed Approaches | Time Complexity | Leetcode 2762 | codestorywithMIKcodestorywithMIK · 52:13 · 11K views
Continuous Subarrays | Leetcode 2762Techdose · 24:05 · 9K views
2762. Continuous Subarrays | 5 Approaches | Map | Deque | 2 PointersAryan Mittal · 46:28 · 4K views
Continuous Subarrays | Leetcode 2762 | Sliding Window | Contest 352Tech Courses · 15:23 · 3K views
3 different Approaches | 2762. Continuous Subarrays | Leetcode Weekly Contest 352codingMohan · 36:10 · 3K views
Most optimal solution | 2762. Continuous Subarrays | leetcode daily challenge | shashcodeShashCode · 30:13 · 2K views
2762. Continuous Subarrays (Leetcode Medium)Programming Live with Larry · 54:13 · 1K views
【每日一题】LeetCode 2762. Continuous SubarraysHuifeng Guan · 20:16 · 946 views
LeetCode 2762 Continuous Subarrays | Variable Sliding Window | Asked in Google Amazon Adobe UberCode Harmony · 26:21 · 594 views
leetcode 2762. Continuous Subarrays - two-pointer sliding window methodCode-Yao · 10:59 · 476 views
The problem
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
Approach overview
Problem 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 1: Sliding Window Approach
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'.
def continuous_subarrays(nums):
start = 0
total = 0
for end in range(len(nums)):
while start < end and abs(nums[end] - nums[start]) > 2:
start += 1
total += end - start + 1
return total
# Example usage
print(continuous_subarrays([5, 4, 2, 4])) # Output: 8The 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.
Approach 2: Brute Force Approach
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.
function continuousSubarrays(nums) {
let total = 0;
for (let start = 0; start < nums.length; start++) {
for (let end = start; end < nums.length; end++) {
let isValid = true;
for (let i = start; i <= end; i++) {
for (let j = i + 1; j <= end; j++) {
if (Math.abs(nums[i] - nums[j]) > 2) {
isValid = false;
break;
}
}
if (!isValid) break;
}
if (isValid) total++;
}
}
return total;
}
// Example usage
console.log(continuousSubarrays([5, 4, 2, 4])); // Output: 8In 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.
Approach 3: Brute Force Approach
In this approach, we iterate over all possible subarrays and check the condition for each subarray. Although simple to implement, it's not efficient for large inputs.
def is_continuous(nums, start, end):
for i in range(start, end + 1):
for j in range(i + 1, end + 1):
if abs(nums[i] - nums[j]) > 2:
return False
return True
def count_continuous_subarrays(nums):
count = 0
for start in range(len(nums)):
for end in range(start, len(nums)):
if is_continuous(nums, start, end):
count += 1
return count
nums = [5, 4, 2, 4]
print("Total Continuous Subarrays:", count_continuous_subarrays(nums))public class ContinuousSubarrays {
public static boolean isContinuous(int[] nums, int start, int end) {
for (int i = start; i <= end; i++) {
for (int j = i + 1; j <= end; j++) {
if (Math.abs(nums[i] - nums[j]) > 2) return false;
}
}
return true;
}
public static int countContinuousSubarrays(int[] nums) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
for (int end = start; end < nums.length; end++) {
if (isContinuous(nums, start, end)) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {5, 4, 2, 4};
System.out.println("Total Continuous Subarrays: " + countContinuousSubarrays(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
bool isContinuous(const vector<int>& nums, int start, int end) {
for (int i = start; i <= end; ++i) {
for (int j = i + 1; j <= end; ++j) {
if (abs(nums[i] - nums[j]) > 2) return false;
}
}
return true;
}
int countContinuousSubarrays(const vector<int>& nums) {
int count = 0;
for (int start = 0; start < nums.size(); ++start) {
for (int end = start; end < nums.size(); ++end) {
if (isContinuous(nums, start, end)) {
count++;
}
}
}
return count;
}
int main() {
vector<int> nums = {5, 4, 2, 4};
cout << "Total Continuous Subarrays: " << countContinuousSubarrays(nums) << endl;
return 0;
}#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int isContinuous(int* nums, int start, int end) {
for (int i = start; i <= end; i++) {
for (int j = i + 1; j <= end; j++) {
if (abs(nums[i] - nums[j]) > 2) return 0;
}
}
return 1;
}
int countContinuousSubarrays(int* nums, int numsSize) {
int count = 0;
for (int start = 0; start < numsSize; start++) {
for (int end = start; end < numsSize; end++) {
if (isContinuous(nums, start, end)) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {5, 4, 2, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Total Continuous Subarrays: %d\n", countContinuousSubarrays(nums, numsSize));
return 0;
}using System;
public class ContinuousSubarrays {
public static bool IsContinuous(int[] nums, int start, int end) {
for (int i = start; i <= end; i++) {
for (int j = i + 1; j <= end; j++) {
if (Math.Abs(nums[i] - nums[j]) > 2) return false;
}
}
return true;
}
public static int CountContinuousSubarrays(int[] nums) {
int count = 0;
for (int start = 0; start < nums.Length; start++) {
for (int end = start; end < nums.Length; end++) {
if (IsContinuous(nums, start, end)) {
count++;
}
}
}
return count;
}
public static void Main() {
int[] nums = { 5, 4, 2, 4 };
Console.WriteLine($"Total Continuous Subarrays: {CountContinuousSubarrays(nums)}");
}
}The Python solution checks all existing subarrays for continuity, calculating the total count that meet the condition using a helper function to examine element pairs.
Time Complexity: O(n^3), dominated by the nested loop structure and the pair check.
Space Complexity: O(1), minimal additional space.
Approach 4: Sliding Window Approach
This approach uses a more efficient sliding window technique. You slide over the array with two pointers and dynamically maintain the conditions for a valid subarray. Adjust pointers as needed to expand or contract the window based on the condition.
public class ContinuousSubarrays {
public static int countContinuousSubarrays(int[] nums) {
int n = nums.length;
int left = 0, right = 0, count = 0;
while (right < n) {
int minVal = nums[right], maxVal = nums[right];
for (int i = right; i >= left; i--) {
maxVal = Math.max(maxVal, nums[i]);
minVal = Math.min(minVal, nums[i]);
if (maxVal - minVal <= 2) {
count++;
} else {
left = i + 1;
break;
}
}
right++;
}
return count;
}
public static void main(String[] args) {
int[] nums = {5, 4, 2, 4};
System.out.println("Total Continuous Subarrays: " + countContinuousSubarrays(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int countContinuousSubarrays(vector<int>& nums) {
int left = 0, right = 0, count = 0;
while (right < nums.size()) {
int minVal = nums[right], maxVal = nums[right];
for (int i = right; i >= left; --i) {
maxVal = max(maxVal, nums[i]);
minVal = min(minVal, nums[i]);
if (maxVal - minVal <= 2) {
count++;
} else {
left = i + 1;
break;
}
}
++right;
}
return count;
}
int main() {
vector<int> nums = {5, 4, 2, 4};
cout << "Total Continuous Subarrays: " << countContinuousSubarrays(nums) << endl;
return 0;
}function countContinuousSubarrays(nums) {
let left = 0;
let right = 0;
let count = 0;
while (right < nums.length) {
let minVal = nums[right], maxVal = nums[right];
for (let i = right; i >= left; i--) {
maxVal = Math.max(maxVal, nums[i]);
minVal = Math.min(minVal, nums[i]);
if (maxVal - minVal <= 2) {
count++;
} else {
left = i + 1;
break;
}
}
right++;
}
return count;
}
const nums = [5, 4, 2, 4];
console.log("Total Continuous Subarrays:", countContinuousSubarrays(nums));#include <stdio.h>
#include <stdlib.h>
int countContinuousSubarrays(int* nums, int numsSize) {
int left = 0, right = 0, count = 0;
while (right < numsSize) {
int minVal = nums[right], maxVal = nums[right];
for (int i = right; i >= left; i--) {
if (nums[i] > maxVal) maxVal = nums[i];
if (nums[i] < minVal) minVal = nums[i];
if (maxVal - minVal <= 2) {
count++;
} else {
left = i + 1;
break;
}
}
right++;
}
return count;
}
int main() {
int nums[] = {5, 4, 2, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Total Continuous Subarrays: %d\n", countContinuousSubarrays(nums, numsSize));
return 0;
}using System;
public class ContinuousSubarrays {
public static int CountContinuousSubarrays(int[] nums) {
int left = 0, right = 0, count = 0;
while (right < nums.Length) {
int minVal = nums[right], maxVal = nums[right];
for (int i = right; i >= left; i--) {
maxVal = Math.Max(maxVal, nums[i]);
minVal = Math.Min(minVal, nums[i]);
if (maxVal - minVal <= 2) {
count++;
} else {
left = i + 1;
break;
}
}
right++;
}
return count;
}
public static void Main() {
int[] nums = { 5, 4, 2, 4 };
Console.WriteLine($"Total Continuous Subarrays: {CountContinuousSubarrays(nums)}");
}
}In this Java implementation, the sliding window is dynamically adjusted as the max/min conditions exceed the limit. This sliding mechanism minimizes unnecessary recalculations.
Time Complexity: O(n), derived from optimizing the index range transitions.
Space Complexity: O(1), maintains in-memory operations without extra space.
Approach 5: Ordered List + Two Pointers
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.
func continuousSubarrays(nums []int) (ans int64) {
i := 0
tm := treemap.NewWithIntComparator()
for j, x := range nums {
if v, ok := tm.Get(x); ok {
tm.Put(x, v.(int)+1)
} else {
tm.Put(x, 1)
}
for {
a, _ := tm.Min()
b, _ := tm.Max()
if b.(int)-a.(int) > 2 {
if v, _ := tm.Get(nums[i]); v.(int) == 1 {
tm.Remove(nums[i])
} else {
tm.Put(nums[i], v.(int)-1)
}
i++
} else {
break
}
}
ans += int64(j - i + 1)
}
return
}Approach 6: Monotonic queue + Two Pointers
function continuousSubarrays(nums: number[]): number {
const [minQ, maxQ]: [number[], number[]] = [[], []];
const n = nums.length;
let res = 0;
for (let r = 0, l = 0; r < n; r++) {
const x = nums[r];
while (minQ.length && nums[minQ.at(-1)!] > x) minQ.pop();
while (maxQ.length && nums[maxQ.at(-1)!] < x) maxQ.pop();
minQ.push(r);
maxQ.push(r);
while (minQ.length && maxQ.length && nums[maxQ[0]] - nums[minQ[0]] > 2) {
if (maxQ[0] < minQ[0]) {
l = maxQ[0] + 1;
maxQ.shift();
} else {
l = minQ[0] + 1;
minQ.shift();
}
}
res += r - l + 1;
}
return res;
}Complexity comparison
| 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. |
| Brute Force Approach | Time Complexity: O(n^3), dominated by the nested loop structure and the pair check. |
| Sliding Window Approach | Time Complexity: O(n), derived from optimizing the index range transitions. |
| Ordered List + Two Pointers | – |
| Monotonic queue + Two Pointers | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Continuous Subarrays easy or hard?
Continuous Subarrays is generally classified as a Medium problem. The challenge comes from recognizing that you must track both the minimum and maximum elements efficiently while maintaining a valid sliding window.
Continuous Subarrays Python/Java solution
The typical implementation uses two pointers with deques from standard libraries. Python commonly uses collections.deque, while Java uses ArrayDeque. Both implementations maintain monotonic order while expanding and shrinking the sliding window.
How to solve Continuous Subarrays in O(n)?
Maintain a sliding window with two deques: one decreasing deque for the maximum and one increasing deque for the minimum. Expand the right pointer while updating both structures. If the difference between the front elements exceeds 2, move the left pointer and remove elements leaving the window. Count valid subarrays using right - left + 1.
What is the best approach for Continuous Subarrays?
The optimal solution uses a sliding window with two monotonic deques to maintain the current minimum and maximum values. This allows you to expand and shrink the window while ensuring the difference between max and min stays within 2. The approach runs in O(n) time because each element enters and leaves the window at most once.
Is Continuous Subarrays asked at Google/Amazon/Meta?
Problems combining sliding window techniques with monotonic queues appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving maintaining window minimum and maximum values are common systemized interview patterns.
What data structure is used in Continuous Subarrays?
The most efficient solution uses monotonic double-ended queues (deques). One deque tracks the maximum values in decreasing order, and the other tracks minimum values in increasing order. These structures allow constant-time updates and retrieval of window extremes.
What is the time complexity of Continuous Subarrays?
The optimal sliding window approach runs in O(n) time and O(n) space using two monotonic queues. A brute force approach that checks all subarrays takes O(n²) time because it expands every starting index and recalculates min and max values.