Continuous Subarrays

Continuous Subarrays

What is this problem about?

The Continuous Subarrays interview question tasks you with finding the total number of continuous subarrays such that the difference between the maximum and minimum element in that subarray is at most 2.

Why is this asked in interviews?

This Continuous Subarrays coding problem is asked by Uber and Google to test a candidate's ability to maintain range constraints in a sliding window. It evaluates if you can efficiently track both the minimum and maximum of a dynamic range without re-scanning the entire window, which would lead to O(N^2) complexity.

Algorithmic pattern used

This follows the Array, Monotonic Queue, Sliding Window interview pattern.

1. Use two Monotonic Deques: one to track the maximums and one to track the minimums in the current window.
2. Expand the right pointer of the window.
3. If max - min > 2, shrink the left pointer and update the deques until the condition is met again.
4. For each right position, the number of valid subarrays ending at right is right - left + 1.

Example explanation

Array: [5, 4, 2, 4]

1. Right=0 (5): Window [5]. Max=5, Min=5. Count += 1.
2. Right=1 (4): Window [5, 4]. Max=5, Min=4. Diff=1. Count += 2. (Subarrays: [4], [5,4]).
3. Right=2 (2): Window [5, 4, 2]. Max=5, Min=2. Diff=3. Shrink Left.
4. New Window [4, 2]. Max=4, Min=2. Diff=2. Count += 2. (Subarrays: [2], [4,2]).
5. Right=3 (4): Window [4, 2, 4]. Max=4, Min=2. Count += 3. Total Count = 1 + 2 + 2 + 3 = 8.

Common mistakes candidates make

• Inefficient tracking: Using min() and max() functions on the window in every step (O(N * K)).
• Miscounting: Not understanding that adding one new element to a window of size W adds W new valid subarrays.
• Deque cleanup: Forgetting to remove indices from the front of the deque when they fall out of the sliding window.

Interview preparation tip

Practice using two deques simultaneously. This "Dual Monotonic Queue" pattern is the standard way to solve any "Sliding Window with Max-Min Difference" constraint.