Continuous Subarrays - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumArray Queue Sliding Window Heap (Priority Queue)16 min readAsked at: Amazon, Microsoft, Meta +2

Practice this problem

Problem Statement

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 indices i <= i₁, i₂ <= j, 0 <= |nums[i₁] - nums[i₂]| <= 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 <= 10⁵
1 <= nums[i] <= 10⁹

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'.

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'.

Code

Python C C++Java C#JavaScript

Python

C++

Java

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaScript C C++Java Python C#

JavaScript

C++

Java

Python

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Approach 4: Monotonic queue + Two Pointers

Code

TypeScript JavaScript

TypeScript

JavaScript

Try this approach in the editor →

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.
Ordered List + Two Pointers	—
Monotonic queue + Two Pointers	—

Detailed 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

Video Solution

Continuous Subarrays | Detailed Approaches | Time Complexity | Leetcode 2762 | codestorywithMIK • codestorywithMIK • 11,943 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Continuous Subarrays with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance58.0%

Approaches4

Reading time16 min

Asked at

Amazon Microsoft Meta Google Bloomberg

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Sliding Window Approach

Code

Complexity

Approach 2: Brute Force Approach

Code

Complexity

Approach 3: Ordered List + Two Pointers

Code

Approach 4: Monotonic queue + Two Pointers

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents