Scale Engineer

Find the Count of Monotonic Pairs I

Hard
#2886Time: O(n * M). For each of the `n` states, we perform O(M) work to compute the DP values and their prefix sums.Space: O(n * M), for the DP and prefix sum tables.1 company
Patterns
MathDynamic ProgrammingCombinatoricsPrefix Sum
Data structures
Array
Companies
Arcesium

Prompt

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.

 

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 <= 2000
  • 1 <= nums[i] <= 50

Approaches

3 approaches with complexity analysis and trade-offs.

This approach optimizes the naive DP solution by observing that the inner loop is calculating a sum over a range. Such summations can be computed efficiently using prefix sums. By pre-calculating the prefix sums for each row of the DP table, we can determine the value of any dp[i][j] in constant time, which significantly improves the overall time complexity.

Algorithm

  • The DP state dp[i][j] is the same as the naive approach.
  • The transition dp[i][j] = sum(dp[i-1][k]) is over a contiguous range of k.
  • The upper bound for k is limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1])).
  • We can precompute prefix sums for each row i-1 of the DP table into an array ps[i-1].
  • dp[i][j] can then be found in O(1) time using ps[i-1][limit].
  • This removes the innermost loop from the naive DP approach.

Walkthrough

The key insight is that the transition dp[i][j] = sum(dp[i-1][k]) is performed for k in the range [0, limit], where limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1])). This is a prefix sum.

We can maintain a parallel 2D array, ps, where ps[i][x] stores the sum of dp[i][k] for k from 0 to x. After computing the i-1-th row of the dp table, we can compute the i-1-th row of the ps table in O(M) time. Then, when computing the i-th row of dp, each dp[i][j] can be found in O(1) by looking up the precomputed value in ps[i-1], effectively eliminating one loop from the previous approach.

Algorithm Steps:

  1. Create a DP table dp[n][M+1] and a prefix sum table ps[n][M+1].
  2. Base Case (i=0): Fill dp[0] and ps[0] as before.
  3. Transitions (i > 0): For i from 1 to n-1:
    • For each j from 0 to nums[i]:
      • Calculate the upper bound for k: limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1])).
      • If limit >= 0, set dp[i][j] = ps[i-1][limit].
    • Compute the prefix sums for the new dp[i] row and store them in ps[i].
  4. Final Result: The answer is ps[n-1][nums[n-1]].
class Solution {    public int countMonotonicPairs(int[] nums) {        int n = nums.length;        int maxVal = 0;        for (int num : nums) {            maxVal = Math.max(maxVal, num);        }        long[][] dp = new long[n][maxVal + 1];        long[][] ps = new long[n][maxVal + 1];        int MOD = 1_000_000_007;         // Base case: i = 0        for (int j = 0; j <= nums[0]; j++) {            dp[0][j] = 1;        }        ps[0][0] = dp[0][0];        for (int j = 1; j <= maxVal; j++) {            ps[0][j] = (ps[0][j - 1] + dp[0][j]) % MOD;        }         // Fill DP table for i > 0        for (int i = 1; i < n; i++) {            long diff = (long)nums[i] - nums[i-1];            for (int j = 0; j <= nums[i]; j++) {                long k_upper_bound = j - Math.max(0, diff);                long limit = Math.min(nums[i-1], k_upper_bound);                                if (limit >= 0) {                    dp[i][j] = ps[i-1][(int)limit];                }            }                        ps[i][0] = dp[i][0];            for (int j = 1; j <= maxVal; j++) {                ps[i][j] = (ps[i][j - 1] + dp[i][j]) % MOD;            }        }         return (int) ps[n - 1][nums[n - 1]];    }}

Complexity

Time

O(n * M). For each of the `n` states, we perform O(M) work to compute the DP values and their prefix sums.

Space

O(n * M), for the DP and prefix sum tables.

Trade-offs

Pros

  • Much faster than the naive DP approach, with a time complexity of O(n * M).

  • Handles the given constraints very efficiently.

Cons

  • Requires additional space for the prefix sum table, although the asymptotic space complexity remains the same.

Solutions

class Solution { public int countOfPairs ( int [] nums ) { final int mod = ( int ) 1 e9 + 7 ; int n = nums . length ; int m = Arrays . stream ( nums ). max (). getAsInt (); int [][] f = new int [ n ][ m + 1 ]; for ( int j = 0 ; j <= nums [ 0 ]; ++ j ) { f [ 0 ][ j ] = 1 ; } int [] g = new int [ m + 1 ]; for ( int i = 1 ; i < n ; ++ i ) { g [ 0 ] = f [ i - 1 ][ 0 ]; for ( int j = 1 ; j <= m ; ++ j ) { g [ j ] = ( g [ j - 1 ] + f [ i - 1 ][ j ]) % mod ; } for ( int j = 0 ; j <= nums [ i ]; ++ j ) { int k = Math . min ( j , j + nums [ i - 1 ] - nums [ i ]); if ( k >= 0 ) { f [ i ][ j ] = g [ k ]; } } } int ans = 0 ; for ( int j = 0 ; j <= nums [ n - 1 ]; ++ j ) { ans = ( ans + f [ n - 1 ][ j ]) % mod ; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem