Last active
December 7, 2025 17:29
-
-
Save tatsuyax25/9574d3af31ff16329afefed4f1ca9e16 to your computer and use it in GitHub Desktop.
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 num
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Count the number of ways to partition nums into contiguous segments | |
| * such that in each segment, max - min <= k. | |
| * | |
| * @param {number[]} nums - Input array of integers | |
| * @param {number} k - Maximum allowed difference between max and min in a segment | |
| * @return {number} - Number of valid partitions modulo 1e9+7 | |
| */ | |
| var countPartitions = function (nums, k) { | |
| const MOD = 1e9 + 7; | |
| const n = nums.length; | |
| // dp[i] = number of ways to partition the first i elements (nums[0..i-1]) | |
| const dp = Array(n + 1).fill(0); | |
| // prefix[i] = sum of dp[0..i-1], used for fast range sum queries | |
| // We allocate n+2 to avoid index issues when updating | |
| const prefix = Array(n + 2).fill(0); | |
| // Base case: empty prefix has 1 valid partition (no cuts) | |
| dp[0] = 1; | |
| prefix[1] = 1; | |
| // Deques to maintain min and max in the current sliding window | |
| let minDeque = []; // increasing order → front is min | |
| let maxDeque = []; // decreasing order → front is max | |
| // Left boundary of the current valid window | |
| let left = 0; | |
| // Iterate over array with right boundary | |
| for (let right = 0; right < n; right++) { | |
| // --- Update deques with nums[right] --- | |
| // Maintain maxDeque (monotonic decreasing) | |
| while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] <= nums[right]) { | |
| maxDeque.pop(); | |
| } | |
| maxDeque.push(right); | |
| // Maintain minDeque (monotonic increasing) | |
| while (minDeque.length && nums[minDeque[minDeque.length - 1]] >= nums[right]) { | |
| minDeque.pop(); | |
| } | |
| minDeque.push(right); | |
| // --- Shrink window from the left until valid --- | |
| // Condition: max - min <= k | |
| while (nums[maxDeque[0]] - nums[minDeque[0]] > k) { | |
| // If left index is leaving the window, pop it from deques | |
| if (maxDeque[0] === left) maxDeque.shift(); | |
| if (minDeque[0] === left) minDeque.shift(); | |
| left++; | |
| } | |
| // --- DP transition --- | |
| // dp[right+1] = sum of dp[j] for j in [left..right] | |
| // Using prefix sums: prefix[right+1] - prefix[left] | |
| dp[right + 1] = (prefix[right + 1] - prefix[left] + MOD) % MOD; | |
| // Update prefix sum for next iteration | |
| prefix[right + 2] = (prefix[right + 1] + dp[right + 1]) % MOD; | |
| } | |
| // Final answer: number of ways to partition the entire array | |
| return dp[n]; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment