2762. Continuous Subarrays

Description

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⁹

Solutions

Solution 1: Ordered List + Two Pointers

Thinking

A subarray is continuous iff its maximum and minimum differ by at most \(2\). Checking every pair of ends is quadratic and too slow at length \(10^5\).

After the right end inserts a value, drop left-end elements from a sorted list until the max–min gap is at most \(2\). The number of legal subarrays that end here equals the list size.

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\).

Python3JavaC++Go

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

class Solution {
    public long continuousSubarrays(int[] nums) {
        long ans = 0;
        int i = 0, n = nums.length;
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int j = 0; j < n; ++j) {
            tm.merge(nums[j], 1, Integer::sum);
            while (tm.lastEntry().getKey() - tm.firstEntry().getKey() > 2) {
                tm.merge(nums[i], -1, Integer::sum);
                if (tm.get(nums[i]) == 0) {
                    tm.remove(nums[i]);
                }
                ++i;
            }
            ans += j - i + 1;
        }
        return ans;
    }
}

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        long long ans = 0;
        int i = 0, n = nums.size();
        multiset<int> s;
        for (int j = 0; j < n; ++j) {
            s.insert(nums[j]);
            while (*s.rbegin() - *s.begin() > 2) {
                s.erase(s.find(nums[i++]));
            }
            ans += j - i + 1;
        }
        return ans;
    }
};

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
}

Solution 2: Monotonic queue + Two Pointers

Thinking

A sorted list pays a logarithm per update. Only the extrema matter, so two monotonic deques of indices suffice. When the gap exceeds \(2\), pop the older extremum and advance the left end. The counting is unchanged, and each index enters and leaves a deque once.

TypeScriptJavaScript

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;
}

function continuousSubarrays(nums) {
    const [minQ, maxQ] = [[], []];
    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;
}

2762. Continuous Subarrays

Description

Solutions

Solution 1: Ordered List + Two Pointers

Solution 2: Monotonic queue + Two Pointers

Comments