Continuous Subarrays — LeetCode 2762 Python Solution

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

Example

Input

nums = [5,4,2,4]

Output

8

Explanation

Continuous subarray of size 1: [5], [4], [2], [4].

Python solution

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

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2762. Continuous Subarrays is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems