Find the Count of Monotonic Pairs I
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] <= 50
Solution
Method 1 – Dynamic Programming with Prefix Sums
Intuition
For each index, we can split nums[i] into arr1[i] and arr2[i] such that arr1 is non-decreasing and arr2 is non-increasing, and arr1[i] + arr2[i] = nums[i]. The number of ways to do this can be computed using DP, where we keep track of the last value of arr1 and the last value of arr2.
Approach
- Let dp[i][a] be the number of ways to fill arr1[0..i] where arr1[i] = a and arr1 is non-decreasing so far.
- For each position, for each possible value of arr1[i], sum over all valid arr1[i-1] <= arr1[i].
- For each arr1, arr2[i] = nums[i] - arr1[i]. arr2 must be non-increasing, so arr2[i] <= arr2[i-1].
- Use prefix sums to speed up the DP transitions.
- The answer is the sum over all valid dp[n-1][a].
Code
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<int>> dp(n, vector<int>(mx+1, 0));
for (int a = 0; a <= nums[0]; ++a) dp[0][a] = 1;
for (int i = 1; i < n; ++i) {
vector<int> pre(mx+2, 0);
for (int a = 0; a <= nums[i-1]; ++a) pre[a+1] = (pre[a] + dp[i-1][a]) % MOD;
for (int a = 0; a <= nums[i]; ++a) {
int b = nums[i] - a;
if (b < 0 || b > mx) continue;
if (i == 1 || b <= nums[i-1] - a) {
dp[i][a] = pre[a+1];
}
}
}
int ans = 0;
for (int a = 0; a <= nums[n-1]; ++a) ans = (ans + dp[n-1][a]) % 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 a := 0; a <= nums[0]; a++ {
dp[0][a] = 1
}
for i := 1; i < n; i++ {
pre := make([]int, mx+2)
for a := 0; a <= nums[i-1]; a++ {
pre[a+1] = (pre[a] + dp[i-1][a]) % MOD
}
for a := 0; a <= nums[i]; a++ {
b := nums[i] - a
if b < 0 || b > mx { continue }
dp[i][a] = pre[a+1]
}
}
ans := 0
for a := 0; a <= nums[n-1]; a++ {
ans = (ans + dp[n-1][a]) % 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];
for (int a = 0; a <= nums[0]; ++a) dp[0][a] = 1;
for (int i = 1; i < n; ++i) {
int[] pre = new int[mx+2];
for (int a = 0; a <= nums[i-1]; ++a) pre[a+1] = (pre[a] + dp[i-1][a]) % MOD;
for (int a = 0; a <= nums[i]; ++a) {
int b = nums[i] - a;
if (b < 0 || b > mx) continue;
dp[i][a] = pre[a+1];
}
}
int ans = 0;
for (int a = 0; a <= nums[n-1]; ++a) ans = (ans + dp[n-1][a]) % 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) { IntArray(mx+1) }
for (a in 0..nums[0]) dp[0][a] = 1
for (i in 1 until n) {
val pre = IntArray(mx+2)
for (a in 0..nums[i-1]) pre[a+1] = (pre[a] + dp[i-1][a]) % MOD
for (a in 0..nums[i]) {
val b = nums[i] - a
if (b < 0 || b > mx) continue
dp[i][a] = pre[a+1]
}
}
var ans = 0
for (a in 0..nums[n-1]) ans = (ans + dp[n-1][a]) % MOD
return ans
}
}
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(n)]
for a in range(nums[0]+1):
dp[0][a] = 1
for i in range(1, n):
pre = [0] * (mx+2)
for a in range(nums[i-1]+1):
pre[a+1] = (pre[a] + dp[i-1][a]) % MOD
for a in range(nums[i]+1):
b = nums[i] - a
if b < 0 or b > mx:
continue
dp[i][a] = pre[a+1]
return sum(dp[n-1][a] for a in range(nums[n-1]+1)) % MOD
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();
let mx = mx as usize;
let mut dp = vec![vec![0; mx+1]; n];
for a in 0..=nums[0] as usize {
dp[0][a] = 1;
}
for i in 1..n {
let mut pre = vec![0; mx+2];
for a in 0..=nums[i-1] as usize {
pre[a+1] = (pre[a] + dp[i-1][a]) % MOD;
}
for a in 0..=nums[i] as usize {
let b = nums[i] as isize - a as isize;
if b < 0 || b > mx as isize { continue; }
dp[i][a] = pre[a+1];
}
}
let mut ans = 0;
for a in 0..=nums[n-1] as usize {
ans = (ans + dp[n-1][a]) % 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(mx+1).fill(0));
for (let a = 0; a <= nums[0]; ++a) dp[0][a] = 1;
for (let i = 1; i < n; ++i) {
const pre = Array(mx+2).fill(0);
for (let a = 0; a <= nums[i-1]; ++a) pre[a+1] = (pre[a] + dp[i-1][a]) % MOD;
for (let a = 0; a <= nums[i]; ++a) {
const b = nums[i] - a;
if (b < 0 || b > mx) continue;
dp[i][a] = pre[a+1];
}
}
let ans = 0;
for (let a = 0; a <= nums[n-1]; ++a) ans = (ans + dp[n-1][a]) % MOD;
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * m), where n is the length of nums and m is the max value in nums, due to DP and prefix sums. - 🧺 Space complexity:
O(n * m), for the DP table.