Find the count of monotonic pairs ii

Array Math Dynamic Programming Combinatorics Prefix Sum

24.6% acceptance

Feb 25, 2026

102

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. arr1 is monotonically non-decreasing, in other words, arr1[0] <= arr1[1] <= ... <= arr1[n - 1]. arr2 is monotonically non-increasing, in other words, arr2[0] >= arr2[1] >= ... >= arr2[n - 1]. arr1[i] + arr2[i] == nums[i] for all 0 <= i <= n - 1. Return the count of monotonic pairs. Since the answer may be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_of_pairs(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    let max_val = *nums.iter().max().unwrap() as usize;
    let mut dp = vec![0i64; max_val + 1];
    for v in 0..=nums[0] as usize {
      dp[v] = 1;
    }
    for i in 1..n {
      let diff = (nums[i] - nums[i - 1]).max(0) as usize;
      let mut prefix = vec![0i64; max_val + 2];
      for v in 0..=max_val {
        prefix[v + 1] = (prefix[v] + dp[v]) % MOD;
      }
      let mut new_dp = vec![0i64; max_val + 1];
      for w in 0..=nums[i] as usize {
        if w >= diff {
          new_dp[w] = prefix[w - diff + 1];
        }
      }
      dp = new_dp;
    }
    (dp.iter().sum::<i64>() % MOD) as i32
  }
}