Medium

Continuous Subarrays

LAB

Return the number of contiguous subarrays where the difference between the maximum and minimum value is at most 2.

EXAMPLES

Example 1

Input
{
  "nums": [
    5,
    4,
    2,
    4
  ]
}

Output
8

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Think of SortedList as a sorted list of numbers. window.add(3) maintains sorted order. window.discard(5) removes element. Operations take O(log n) time.

Key insight: res += r-l+1 because if [l,r] works, any subarray that ends at index r and starts at index i: l <= i <= r also works.

Reveal reference solution +

pythonREFERENCE

from sortedcontainers import SortedList

def continuousSubarrays(self, nums: List[int]) -> int:
    n = len(nums)
    l = 0
    res = 0
    window = SortedList()

    for r in range(n):
        window.add(nums[r])

        while window and window[-1] - window[0] > 2:
            window.discard(nums[l])
            l += 1

        # [l,r] works - count all subarrays ending at r
        res += r - l + 1

    return res

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗