Find the Count of Monotonic Pairs II solution and explanation
4 more videos on this problem
3251. Find the Count of Monotonic Pairs II | Weekly Leetcode 410codingMohan · 33:04 · 2K views
3251. Find the Count of Monotonic Pairs II (Leetcode Hard)Programming Live with Larry · 36:18 · 606 views
Leetcode Weekly Contest 410 | Find the Count of Monotonic Pairs I & II | Dp and optimizationAlgonaline · 19:54 · 568 views
3251. Find the Count of Monotonic Pairs II | Weekly Contest 410 | LeetcodeAmit Choraria · 21:46 · 156 views
3251. Find the Count of Monotonic Pairs II | Weekly Contest 410 | LeetCodePulkit Malhotra · 9:55 · 109 views
The problem
You are given an array of positive integers nums of length n.
We call a pair of non-negative integer arrays (arr1, arr2) monotonic if:
- The lengths of both arrays are
n. arr1is monotonically non-decreasing, in other words,arr1[0] <= arr1[1] <= ... <= arr1[n - 1].arr2is monotonically non-increasing, in other words,arr2[0] >= arr2[1] >= ... >= arr2[n - 1].arr1[i] + arr2[i] == nums[i]for all0 <= i <= n - 1.
Return the count of monotonic pairs.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [2,3,2]
Output: 4
Explanation:
The good pairs are:
([0, 1, 1], [2, 2, 1])([0, 1, 2], [2, 2, 0])([0, 2, 2], [2, 1, 0])([1, 2, 2], [1, 1, 0])
Example 2:
Input: nums = [5,5,5,5]
Output: 126
Constraints:
1 <= n == nums.length <= 20001 <= nums[i] <= 1000
Approach overview
Problem Overview: You receive an integer array nums. Build two arrays a and b such that a[i] + b[i] = nums[i], a is non‑decreasing, and b is non‑increasing. The task is to count how many valid pairs (a, b) exist.
Approach 1: Dynamic Programming with Prefix Sum (O(n * m) time, O(n * m) space)
Let dp[i][x] represent the number of ways where a[i] = x. Since a[i] + b[i] = nums[i], x ranges from 0 to nums[i]. The monotonic constraints produce a transition constraint from the previous value prev: a[i] ≥ prev (non‑decreasing) and nums[i] - a[i] ≤ nums[i-1] - prev (because b must be non‑increasing). Rearranging gives a[i] ≥ prev + max(0, nums[i] - nums[i-1]). For each x, you sum all valid prev values that satisfy this bound. Direct summation would be O(m²), so maintain prefix sums to compute range totals in O(1). Iterate through the array, update the DP row using prefix sums of the previous row, and accumulate counts modulo 1e9+7. This approach uses standard dynamic programming combined with prefix sums to keep transitions efficient.
Approach 2: Combinatorial Transformation (O(n * m) time, O(m) space)
The constraints can be simplified by analyzing the required increase in a. Define d[i] = max(0, nums[i] - nums[i-1]). From the inequality above, a[i] must increase by at least d[i] compared to a[i-1]. Subtract the cumulative minimum increases to transform the sequence into a new variable where the monotonic requirement becomes simple non‑decreasing growth with bounded limits. After shifting the bounds, the remaining choices resemble distributing increments across positions, which can be counted using combinatorial reasoning or DP with cumulative counts. This interpretation connects the problem to combinatorics and array constraint transformations. It reduces repeated DP transitions and keeps only the valid ranges for each position.
Recommended for interviews: The dynamic programming approach with prefix sums is the expected solution. It clearly models the constraints and runs in O(n * m), which fits the limits. Starting with the DP formulation shows understanding of state transitions, while optimizing with prefix sums demonstrates the ability to reduce nested summations.
Approach 1: Dynamic Programming Approach
The idea is to use a dynamic programming table to keep track of the number of ways to fill the `arr1` and `arr2` arrays up to each index such that they satisfy the constraints of being monotonic. For each index `i` and each possible value of `arr1[i]`, we'll compute the number of ways to choose `arr1` values up to `i` such that the sum `arr1[i] + arr2[i] = nums[i]` and `arr1` is non-decreasing and `arr2` is non-increasing.
..................Approach 2: Dynamic Programming + Prefix Sum Optimization
We define f[i][j] to represent the number of monotonic array pairs for the subarray [0, ldots, i] where arr1[i] = j. Initially, f[i][j] = 0, and the answer is sum_{j=0}^{nums[n-1]} f[n-1][j].
When i = 0, we have f[0][j] = 1 for 0 leq j leq nums[0].
When i > 0, we can calculate f[i][j] based on f[i-1][j']. Since arr1 is non-decreasing, j' leq j. Additionally, since arr2 is non-increasing, nums[i] - j leq nums[i - 1] - j'. Thus, j' leq min(j, j + nums[i - 1] - nums[i]).
The answer is sum_{j=0}^{nums[n-1]} f[n-1][j].
The time complexity is O(n times m), and the space complexity is O(n times m). Here, n represents the length of the array nums, and m represents the maximum value in the array nums.
function countOfPairs(nums: number[]): number {
const mod = 1e9 + 7;
const n = nums.length;
const m = Math.max(...nums);
const f: number[][] = Array.from({ length: n }, () => Array(m + 1).fill(0));
for (let j = 0; j <= nums[0]; j++) {
f[0][j] = 1;
}
const g: number[] = Array(m + 1).fill(0);
for (let i = 1; i < n; i++) {
g[0] = f[i - 1][0];
for (let j = 1; j <= m; j++) {
g[j] = (g[j - 1] + f[i - 1][j]) % mod;
}
for (let j = 0; j <= nums[i]; j++) {
const k = Math.min(j, j + nums[i - 1] - nums[i]);
if (k >= 0) {
f[i][j] = g[k];
}
}
}
let ans = 0;
for (let j = 0; j <= nums[n - 1]; j++) {
ans = (ans + f[n - 1][j]) % mod;
}
return ans;
}func countOfPairs(nums []int) (ans int) {
const mod int = 1e9 + 7
n := len(nums)
m := slices.Max(nums)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 0; j <= nums[0]; j++ {
f[0][j] = 1
}
g := make([]int, m+1)
for i := 1; i < n; i++ {
g[0] = f[i-1][0]
for j := 1; j <= m; j++ {
g[j] = (g[j-1] + f[i-1][j]) % mod
}
for j := 0; j <= nums[i]; j++ {
k := min(j, j+nums[i-1]-nums[i])
if k >= 0 {
f[i][j] = g[k]
}
}
}
for j := 0; j <= nums[n-1]; j++ {
ans = (ans + f[n-1][j]) % mod
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | – |
| Dynamic Programming + Prefix Sum Optimization | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Sum | O(n * m) | O(n * m) | General solution that directly models monotonic constraints |
| Combinatorial Transformation | O(n * m) | O(m) | When deriving mathematical bounds to reduce DP transitions |
Frequently asked questions
Is Find the Count of Monotonic Pairs II easy or hard?
Find the Count of Monotonic Pairs II is rated Hard because it combines multiple constraints: two monotonic sequences, equation coupling between arrays, and optimized DP transitions. Recognizing the inequality transformation and using prefix sums is the key challenge.
Find the Count of Monotonic Pairs II Python/Java solution
Python and Java implementations typically build a DP table and maintain prefix sums for each row. For every index i and value x, compute the valid previous range and fetch the count using the prefix sum array. The final answer is the sum of dp[n-1][x] for all valid x values.
How to solve Find the Count of Monotonic Pairs II in O(n*m)?
Use dynamic programming where dp[i][x] represents choosing a[i] = x. Determine the valid range of previous values using the constraints from the non‑decreasing a array and non‑increasing b array. Maintain prefix sums of the previous DP row so each transition becomes a constant‑time range query.
What is the best approach for Find the Count of Monotonic Pairs II?
Dynamic programming with prefix sums is the most reliable approach. Define dp[i][x] as the number of ways where a[i] = x and enforce the monotonic constraints between adjacent elements. Prefix sums allow you to compute valid transition ranges in O(1), giving an overall complexity of O(n * m).
Is Find the Count of Monotonic Pairs II asked at Google/Amazon/Meta?
Problems involving constrained dynamic programming and combinatorics frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine monotonic sequences with DP transitions are common in advanced algorithm rounds.
What data structure is used in Find the Count of Monotonic Pairs II?
The core structure is a dynamic programming table combined with a prefix sum array for fast range queries. Arrays are sufficient to store DP states and cumulative sums, making the implementation efficient and cache friendly.
What is the time complexity of Find the Count of Monotonic Pairs II?
The optimized solution runs in O(n * m) time, where n is the length of nums and m is the maximum value in nums. Each state transition is computed using prefix sums instead of nested loops, which prevents an O(m^2) slowdown.