Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For each right endpoint, the valid starts of its final segment form a suffix of possible starts: removing leftmost elements cannot increase the segment's maximum-minus-minimum. If dp[j] counts partitions of the first j elements, append a valid final segment starting at j to any of those partitions.

Approach

Set dp[0] = 1 for the empty prefix. Maintain an ordered multiset for the current window and move its left boundary forward until its maximum minus minimum is at most k. Keep a running sum of the DP entries corresponding to eligible segment starts.

When the left boundary advances past index left, subtract dp[left] from that sum and remove the outgoing value from the multiset. After the window is valid, assign the sum to dp[right + 1], then add this new DP value for the next iteration. Normalize updates modulo 1,000,000,007.

Each partition has a unique final segment, so the recurrence counts it exactly once. Return dp[n] after all endpoints are processed.

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        dp = [1] + [0] * n
        acc = 1
        sl = SortedList()
        l = 0

        for r in range(n):
            sl.add(nums[r])
            while sl[-1] - sl[0] > k:
                sl.remove(nums[l])
                acc = (acc - dp[l]) % MOD
                l += 1
            dp[r + 1] = acc
            acc = (acc + dp[r + 1]) % MOD

        return dp[n]

Complexity analysis

Let n=nums.length and W be the maximum maintained window size, including the newly inserted value before shrinking. JavaScript's AVL multiset gives O(nlog(W+1)) worst-case time. Python uses the block-based SortedList: updates are approximately logarithmic in practice but do not have the same strict AVL guarantee; O(nW) is a conservative worst-case upper bound including block shifts and reorganization. Both have O(n) auxiliary space for DP and the window, and O(n) total insertions/removals.