Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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].
Thereare 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:

1
2
3
4
5
6
7

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

Solution

Method 1 - Sliding window but naive

To determine the total number of continuous subarrays, we can use the sliding window technique. We need to maintain a window that satisfies the given property: for each pair of indices in the subarray, the absolute difference between their values is at most 2.

We’ll use two pointers:

  • l to mark the start of the window.
  • r to mark the end of the window.

As we slide the window, we’ll keep track of the minimum and maximum values within the current subarray. If at any point the condition max(nums[l:r+1]) - min(nums[l:r+1]) <= 2 is violated, we’ll move the starting pointer l to the right until the condition is again satisfied.

We’ll count the number of subarrays ending at r for each position of r by calculating r - l + 1, which gives us the count of valid subarrays ending at r.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public long continuousSubarrays(int[] nums) {
        int l = 0, r = 0;
        long ans = 0;
        int min = nums[0], max = nums[0];

        while (r < nums.length) {
            min = Math.min(min, nums[r]);
            max = Math.max(max, nums[r]);

            while (max - min > 2) {
                l++;
                min = max = nums[l];
                for (int k = l; k <= r; k++) {
                    min = Math.min(min, nums[k]);
                    max = Math.max(max, nums[k]);
                }
            }

            ans += (r - l + 1);
            r++;
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def continuous_subarrays(self, nums: List[int]) -> int:
        l: int = 0
        ans: int = 0
        min_val: int = nums[0]
        max_val: int = nums[0]

        for r in range(len(nums)):
            min_val = min(min_val, nums[r])
            max_val = max(max_val, nums[r])

            while max_val - min_val > 2:
                l += 1
                min_val = nums[l]
                max_val = nums[l]
                for k in range(l, r + 1):
                    min_val = min(min_val, nums[k])
                    max_val = max(max_val, nums[k])

            ans += (r - l + 1)

        return ans

Complexity

  • ⏰ Time complexity: O(n^2)
    • The sliding window results in time complexity of O(n) but we are again finding min and max elements in window again, resulting in time complexity of O(n^2).
  • 🧺 Space complexity: O(1) apart from the input array, as no additional space proportional to input size is used.

Method 2 - Sliding window using deque

To keep the complexity strictly linear, we can utilize data structures to maintain the minimum and maximum values more efficiently during our sliding window traversal. Specifically, we can use deques (double-ended queues) to maintain a window of the minimum and maximum values.

We can use deque:

  • Sliding Window:
    • We’ll use two deques: one to keep track of the minimum values (minDeque) and one for the maximum values (maxDeque).
  • Update Deques:
    • As we iterate through each element, we update the deques to include the current element.
    • Remove elements from deques if they go out of the current window bounds.
  • Adjust Window:
    • If the condition max_deque.peekFirst() - min_deque.peekFirst() > 2 is violated, increment the start pointer l to shrink the window until the condition is met again.
  • Count Valid Subarrays:
    • For each valid position of r, count the number of continuous subarrays ending at r by adding r - l + 1 to the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public long continuousSubarrays(int[] nums) {
        int l = 0;
        long ans = 0;
        Deque<Integer> minDeque = new LinkedList<>();
        Deque<Integer> maxDeque = new LinkedList<>();

        for (int r = 0; r < nums.length; r++) {
            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[r])
                minDeque.pollLast();
            minDeque.addLast(r);

            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[r])
                maxDeque.pollLast();
            maxDeque.addLast(r);

            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > 2) {
                l++;
                if (minDeque.peekFirst() < l) minDeque.pollFirst();
                if (maxDeque.peekFirst() < l) maxDeque.pollFirst();
            }

            ans += r - l + 1;
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def continuous_subarrays(self, nums: List[int]) -> int:
        l: int = 0
        ans: int = 0
        min_deque: deque[int] = deque()
        max_deque: deque[int] = deque()

        for r in range(len(nums)):
            while min_deque and nums[min_deque[-1]] >= nums[r]:
                min_deque.pop()
            min_deque.append(r)

            while max_deque and nums[max_deque[-1]] <= nums[r]:
                max_deque.pop()
            max_deque.append(r)

            while nums[max_deque[0]] - nums[min_deque[0]] > 2:
                l += 1
                if min_deque[0] < l:
                    min_deque.popleft()
                if max_deque[0] < l:
                    max_deque.popleft()

            ans += (r - l + 1)

        return ans

Complexity

  • ⏰ Time complexity: O(n), because each element is processed at most twice (once when added and once when removed from the deques).
  • 🧺 Space complexity: O(n) in the worst case to hold the deque elements.