Find the Count of Monotonic Pairs II
HardUpdated: Aug 2, 2025
Practice on:
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 10^9 + 7.
Examples
Example 1
Input: nums = [2,3,2]
Output: 4
Explanation:
The good pairs are:
1. `([0, 1, 1], [2, 2, 1])`
2. `([0, 1, 2], [2, 2, 0])`
3. `([0, 2, 2], [2, 1, 0])`
4. `([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
Solution
Method 1 – Dynamic Programming with 2D State
Intuition
We need to count the number of monotonic pairs (arr1, arr2) where arr1 is non-decreasing, arr2 is non-increasing, and arr1[i] + arr2[i] = nums[i]. Unlike part I, here both arr1 and arr2 must be monotonic, so we need to track both the last value of arr1 and arr2 in our DP.
Approach
- Let dp[i][a][b] be the number of ways to fill arr1[0..i] and arr2[0..i] where arr1[i]=a, arr2[i]=b, arr1 is non-decreasing, arr2 is non-increasing, and a+b=nums[i].
- For each position, for each possible value of arr1[i] and arr2[i], sum over all valid previous (a', b') such that a' <= a and b' >= b.
- Use prefix sums to speed up the DP transitions.
- The answer is the sum over all valid dp[n-1][a][b] for a+b=nums[n-1].
Code
Python
class Solution:
def countMonotonicPairs(self, nums: list[int]) -> int:
MOD = 10**9 + 7
n = len(nums)
mx = max(nums)
dp = [[[0]*(mx+1) for _ in range(mx+1)] for _ in range(n)]
for a in range(nums[0]+1):
b = nums[0] - a
dp[0][a][b] = 1
for i in range(1, n):
for a in range(nums[i]+1):
b = nums[i] - a
if b < 0 or b > mx:
continue
for pa in range(a+1):
for pb in range(b, mx+1):
dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD
ans = 0
for a in range(nums[-1]+1):
b = nums[-1] - a
if 0 <= b <= mx:
ans = (ans + dp[n-1][a][b]) % MOD
return ans
C++
class Solution {
public:
int countMonotonicPairs(vector<int>& nums) {
const int MOD = 1e9 + 7;
int n = nums.size(), mx = *max_element(nums.begin(), nums.end());
vector<vector<vector<int>>> dp(n, vector<vector<int>>(mx+1, vector<int>(mx+1, 0)));
for (int a = 0; a <= nums[0]; ++a) {
int b = nums[0] - a;
dp[0][a][b] = 1;
}
for (int i = 1; i < n; ++i) {
for (int a = 0; a <= nums[i]; ++a) {
int b = nums[i] - a;
if (b < 0 || b > mx) continue;
for (int pa = 0; pa <= a; ++pa) {
for (int pb = b; pb <= mx; ++pb) {
dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD;
}
}
}
}
int ans = 0;
for (int a = 0; a <= nums[n-1]; ++a) {
int b = nums[n-1] - a;
if (b < 0 || b > mx) continue;
ans = (ans + dp[n-1][a][b]) % MOD;
}
return ans;
}
};
Java
class Solution {
public int countMonotonicPairs(int[] nums) {
int MOD = 1_000_000_007, n = nums.length, mx = 0;
for (int v : nums) mx = Math.max(mx, v);
int[][][] dp = new int[n][mx+1][mx+1];
for (int a = 0; a <= nums[0]; ++a) {
int b = nums[0] - a;
dp[0][a][b] = 1;
}
for (int i = 1; i < n; ++i) {
for (int a = 0; a <= nums[i]; ++a) {
int b = nums[i] - a;
if (b < 0 || b > mx) continue;
for (int pa = 0; pa <= a; ++pa) {
for (int pb = b; pb <= mx; ++pb) {
dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD;
}
}
}
}
int ans = 0;
for (int a = 0; a <= nums[n-1]; ++a) {
int b = nums[n-1] - a;
if (b < 0 || b > mx) continue;
ans = (ans + dp[n-1][a][b]) % MOD;
}
return ans;
}
}
Kotlin
class Solution {
fun countMonotonicPairs(nums: IntArray): Int {
val MOD = 1_000_000_007
val n = nums.size
val mx = nums.maxOrNull() ?: 0
val dp = Array(n) { Array(mx+1) { IntArray(mx+1) } }
for (a in 0..nums[0]) {
val b = nums[0] - a
dp[0][a][b] = 1
}
for (i in 1 until n) {
for (a in 0..nums[i]) {
val b = nums[i] - a
if (b < 0 || b > mx) continue
for (pa in 0..a) {
for (pb in b..mx) {
dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD
}
}
}
}
var ans = 0
for (a in 0..nums[n-1]) {
val b = nums[n-1] - a
if (b < 0 || b > mx) continue
ans = (ans + dp[n-1][a][b]) % MOD
}
return ans
}
}
Go
func countMonotonicPairs(nums []int) int {
MOD := int(1e9 + 7)
n := len(nums)
mx := 0
for _, v := range nums {
if v > mx { mx = v }
}
dp := make([][][]int, n)
for i := range dp {
dp[i] = make([][]int, mx+1)
for j := range dp[i] {
dp[i][j] = make([]int, mx+1)
}
}
for a := 0; a <= nums[0]; a++ {
b := nums[0] - a
dp[0][a][b] = 1
}
for i := 1; i < n; i++ {
for a := 0; a <= nums[i]; a++ {
b := nums[i] - a
if b < 0 || b > mx { continue }
for pa := 0; pa <= a; pa++ {
for pb := b; pb <= mx; pb++ {
dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD
}
}
}
}
ans := 0
for a := 0; a <= nums[n-1]; a++ {
b := nums[n-1] - a
if b < 0 || b > mx { continue }
ans = (ans + dp[n-1][a][b]) % MOD
}
return ans
}
Rust
impl Solution {
pub fn count_monotonic_pairs(nums: Vec<i32>) -> i32 {
const MOD: i32 = 1_000_000_007;
let n = nums.len();
let mx = *nums.iter().max().unwrap() as usize;
let mut dp = vec![vec![vec![0; mx+1]; mx+1]; n];
for a in 0..=nums[0] as usize {
let b = nums[0] as usize - a;
dp[0][a][b] = 1;
}
for i in 1..n {
for a in 0..=nums[i] as usize {
let b = nums[i] as usize - a;
if b > mx { continue; }
for pa in 0..=a {
for pb in b..=mx {
dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD;
}
}
}
}
let mut ans = 0;
for a in 0..=nums[n-1] as usize {
let b = nums[n-1] as usize - a;
if b > mx { continue; }
ans = (ans + dp[n-1][a][b]) % MOD;
}
ans
}
}
TypeScript
class Solution {
countMonotonicPairs(nums: number[]): number {
const MOD = 1e9 + 7, n = nums.length, mx = Math.max(...nums);
const dp: number[][][] = Array.from({length: n}, () => Array.from({length: mx+1}, () => Array(mx+1).fill(0)));
for (let a = 0; a <= nums[0]; ++a) {
const b = nums[0] - a;
dp[0][a][b] = 1;
}
for (let i = 1; i < n; ++i) {
for (let a = 0; a <= nums[i]; ++a) {
const b = nums[i] - a;
if (b < 0 || b > mx) continue;
for (let pa = 0; pa <= a; ++pa) {
for (let pb = b; pb <= mx; ++pb) {
dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD;
}
}
}
}
let ans = 0;
for (let a = 0; a <= nums[n-1]; ++a) {
const b = nums[n-1] - a;
if (b < 0 || b > mx) continue;
ans = (ans + dp[n-1][a][b]) % MOD;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * m^2), where n is the length of nums and m is the max value in nums, due to DP over two states. - 🧺 Space complexity:
O(n * m^2), for the DP table.