Leetcode-DSA/Day 58 at main · Renu-code123/Leetcode-DSA · GitHub

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
29
30
31
32
33
34
35
36
37
#3578.count-partitions-with-max-min-difference-at-most-k:-


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

        from collections import deque
        minD, maxD = deque(), deque()
        l = 0

        for i in range(n):
            while minD and minD[-1] > nums[i]:
                minD.pop()
            minD.append(nums[i])

            while maxD and maxD[-1] < nums[i]:
                maxD.pop()
            maxD.append(nums[i])

            while maxD[0] - minD[0] > k:
                if nums[l] == minD[0]:
                    minD.popleft()
                if nums[l] == maxD[0]:
                    maxD.popleft()
                l += 1

            dp[i+1] = (prefix[i] - prefix[l-1]) % MOD if l > 0 else prefix[i]
            prefix[i+1] = (prefix[i] + dp[i+1]) % MOD

        return dp[n]