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

 

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

Solutions

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.

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

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

Comments