leetcode

commit 8875111b46c3d020eb593ec8cb85bc22d4fc5a34
parent c21b21782861dde4d3d1744b91945addf8730c50
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat,  6 Dec 2025 10:33:12 +0100

3578. count partition with max-min difference at most k

Diffstat:
A
count_partition_max_min_diff_k.c
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++
A
count_partition_max_min_diff_k.py
 | 
47
+++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 95 insertions(+), 0 deletions(-)
diff --git a/count_partition_max_min_diff_k.c b/count_partition_max_min_diff_k.c
@@ -0,0 +1,48 @@
+// 3578. Count Partitions With Max-Min Difference at Most K
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and an integer 'k'. your task is to
+ * partition 'nums' into one or more non-empty contiguous segments such that in
+ * each segment, the difference between its maximum and minimum elements is at
+ * most 'k'. return the total number of ways to partition 'nums' under this
+ * condition. since the answer may be too large, return it modulo 10^9 + 7.
+ */
+
+int countPartitions(int *nums, int numsSize, int k) {
+  static int mod = 1e9 + 7;
+  long *dp = (long *)calloc(numsSize + 1, sizeof(long)), total = 0;
+  dp[0] = 1;
+  int *max = (int *)malloc(numsSize * sizeof(int));
+  int *min = (int *)malloc(numsSize * sizeof(int));
+  int max_l = 0, max_r = 0, min_l = 0, min_r = 0, l = 0;
+  for (int r = 0; r < numsSize; r++) {
+    while (max_l < max_r && nums[max[max_r - 1]] <= nums[r])
+      max_r--;
+    while (min_l < min_r && nums[min[min_r - 1]] >= nums[r])
+      min_r--;
+    max[max_r++] = r;
+    min[min_r++] = r;
+    while (nums[max[max_l]] - nums[min[min_l]] > k) {
+      if (max[max_l] == l)
+        max_l++;
+      if (min[min_l] == l)
+        min_l++;
+      total = (total - dp[l] + mod) % mod;
+      l++;
+    }
+    total = (total + dp[r]) % mod;
+    dp[r + 1] = total;
+  }
+  int ans = dp[numsSize];
+  free(dp);
+  free(max);
+  free(min);
+  return ans;
+}
+
+int main() {
+  int n1[] = {9, 4, 1, 3, 7}, n2[] = {3, 3, 4};
+  printf("%d\n", countPartitions(n1, ARRAY_SIZE(n1), 4)); // expect: 6
+  printf("%d\n", countPartitions(n2, ARRAY_SIZE(n2), 0)); // expect: 2
+}
diff --git a/count_partition_max_min_diff_k.py b/count_partition_max_min_diff_k.py
@@ -0,0 +1,47 @@
+# 3578. Count Partitions With Max-Min Difference at Most K
+from collections import deque
+
+"""
+you are given an integer array 'nums' and an integer 'k'. your task is to
+partition 'nums' into one or more non-empty contiguous segments such that in
+each segment, the difference between its maximum and minimum elements is at
+most 'k'. return the total number of ways to partition 'nums' under this
+condition. since the answer may be too large, return it modulo 10^9 + 7.
+"""
+
+
+class Solution(object):
+    def countPartitions(self, nums, k):
+        """
+        :type nums: List[int]
+        :type k: int
+        :rtype: int
+        """
+        n, mod = len(nums), 10**9 + 7
+        dp = [0] * (n + 1)
+        dp[0] = 1
+        mx, mn = deque(), deque()
+        left, total = 0, 0
+        for right in range(n):
+            while mx and nums[mx[-1]] <= nums[right]:
+                mx.pop()
+            while mn and nums[mn[-1]] >= nums[right]:
+                mn.pop()
+            mx.append(right)
+            mn.append(right)
+            while nums[mx[0]] - nums[mn[0]] > k:
+                if mx[0] == left:
+                    mx.popleft()
+                if mn[0] == left:
+                    mn.popleft()
+                total = (total - dp[left]) % mod
+                left += 1
+            total = (total + dp[right]) % mod
+            dp[right + 1] = total
+        return dp[n]
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.countPartitions(nums=[9, 4, 1, 3, 7], k=4))
+    print(obj.countPartitions(nums=[3, 3, 4], k=0))