#2762

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Continuous Subarrays

Count all continuous subarrays efficiently using sliding window with running max-min state tracking for array consistency.

array queue sliding window heap priority queue ordered set

Problem Statement

You are given a 0-indexed integer array nums. A subarray is defined as a contiguous non-empty sequence of elements within nums, and a subarray is called continuous if its maximum and minimum elements differ by at most a specific range, maintaining a consistent window of values.

Return the total number of continuous subarrays in nums. Each subarray must satisfy the running state constraint on maximum and minimum values, making sliding window with dynamic updates the core approach.

Examples

Example 1

Input: nums = [5,4,2,4]

Output: 8

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

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 <= 105
1 <= nums[i] <= 109

Solution Approach

Sliding Window Expansion

Use two pointers to define a dynamic window. Expand the right pointer while the subarray remains valid by maintaining the current maximum and minimum values using monotonic queues.

State Tracking with Monotonic Queues

Maintain a decreasing queue for maximum values and an increasing queue for minimum values. Update the queues as the window moves to quickly check whether adding a new element keeps the subarray continuous.

Counting Valid Subarrays

For each window defined by left and right pointers, add the number of valid subarrays ending at the current right index. Increment the left pointer and remove outdated elements from queues when constraints are violated.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The algorithm processes each element at most twice using two pointers and monotonic queues, resulting in O(n) time. Queues store indices and adjust in constant time per operation, using O(1) extra space overall since only state tracking is needed.

What Interviewers Usually Probe

Looks for a sliding window with dynamic state updates.
Checks understanding of monotonic queue usage for max-min tracking.
May ask how to handle large arrays efficiently in O(n).

Common Pitfalls or Variants

Common pitfalls

Forgetting to shrink the window when max-min exceeds allowed range.
Incorrectly updating monotonic queues when elements leave the window.
Counting subarrays incorrectly by not considering all subarrays ending at current index.

Follow-up variants

Compute subarrays with sum constraints instead of max-min differences.
Count subarrays with exactly k distinct elements using similar sliding window techniques.
Find the longest continuous subarray under the same max-min constraint.

FAQ

What is a continuous subarray in this problem?

A continuous subarray is any contiguous sequence of nums where the difference between maximum and minimum values satisfies the window constraint.

How does the sliding window approach apply to Continuous Subarrays?

Sliding window dynamically expands and contracts while maintaining max-min state to count valid subarrays efficiently.

Can this approach handle large arrays up to 10^5 elements?

Yes, using O(n) time with monotonic queues ensures performance even for the maximum constraints.

Why use monotonic queues instead of sorting each window?

Sorting each window would be O(n^2) or worse. Monotonic queues maintain max-min in O(1) per element, keeping overall time O(n).

How do I count all valid subarrays without missing any?

For each right pointer, count subarrays from left to right by adding (right-left+1) whenever the window is valid, updating left when constraints break.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

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 ans

Solution 2: Monotonic queue + Two Pointers

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

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 ans

Continue Practicing

#1438 longest continuous subarray with absolute diff less than or equal to limit #2398 maximum number of robots within budget #2944 minimum number of coins for fruits