LC-2762: Continuous Subarrays

Question

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if: Let i, i + 1, …, j be the indices in the subarray. Then, for each pair of indices i <= 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.

Approach

Since the size of the array can be around 10^6, we can’t use nested loops. However, we can think of a two-pointer aproach to keep track of the current subarray/window.
We also need a way to maintain the maximum and the minimum of the current subarray. The maximum/minimum can be maintained by storing the maximum/minimum element at each iteration in such a way that when the left part of the window slides by one, we can easily remove that element without affecting the remaining maximum/minimum elements. A monotonic queue should be useful in such a situation.

But what is a monotonic queue, you might ask

A monotonic queue is a data structure that supports efficient insertion, deletion, and retrieval of elements in a specific order, typically in increasing or decreasing order.

Explanation

Suppose, we need to get the maximum elements of a particular window(subarray) in a list. We can make use of a double ended queue which supports insertion/deletion/retrieval from both it’s ends. We can keep removing the elements from the it’s back-end while the current element is greater than the element at the back, and then insert it. This will maintain the queue in a decreasing order and we can easily get the largest element by querying it’s front element.

Talk is cheap, just show me the code

class Solution {
    Deque<Integer> maxQ;
    Deque<Integer> minQ;
    public int getMaxInSubarray(){
        return maxQ.size() == 0 ? -1 : maxQ.peekFirst();
    }
    public int getMinInSubarray(){
        return minQ.size() == 0 ? -1 : minQ.peekFirst();
    }
    public long continuousSubarrays(int[] nums) {
        minQ = new ArrayDeque<>();
        maxQ = new ArrayDeque<>();
        
        int l = 0;// starting index of the current subarray
        int r = 0;// ending index of the current subarray
        long ans = 0;
        int n = nums.length;
        while(r < n){
            // in order to maintain a monotonic max queue remove smaller elements from the back
            while(maxQ.size() > 0 && maxQ.peekLast() < nums[r]){
                maxQ.removeLast();
            }
            // in order to maintain a monotonic min queue remove greater elements from the back
            while(minQ.size() > 0 && minQ.peekLast() > nums[r]){
                minQ.removeLast();
            }
            // add the current element in both the queues
            maxQ.addLast(nums[r]);
            minQ.addLast(nums[r]);
            
            // slide the left pointer of the current window(subarray) if necessary
            while(getMaxInSubarray() - getMinInSubarray() > 2){
                if(maxQ.size() > 0 && maxQ.peekFirst() == nums[l]){
                    maxQ.removeFirst();
                }
                if(minQ.size() > 0 && minQ.peekFirst() == nums[l]){
                    minQ.removeFirst();
                }
                l++;
            }
            // size of the current subarray is actually 
            // the number of subarrays(of varied sizes) that it will constitute
            ans += r - l + 1;
            r++;
        }
        return ans;
    }
}

Complexity

Time complexity: O(n)

Space complexity: O(n)

For further reference: