Find the Count of Monotonic Pairs II - Problem

Array Math Dynamic Programming Combinatorics Prefix Sum Hard

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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,2]

› Output: 4

💡 Note: Valid monotonic pairs: ([0,2,1],[2,1,1]), ([0,2,2],[2,1,0]), ([0,3,1],[2,0,1]), ([0,3,2],[2,0,0]). Each satisfies arr1 non-decreasing, arr2 non-increasing, and arr1[i] + arr2[i] = nums[i].

Example 2 — Single Element

$ Input: nums = [5]

› Output: 6

💡 Note: For single element, arr1[0] can be 0,1,2,3,4,5 and arr2[0] = 5-arr1[0]. All 6 combinations are valid since there are no monotonic constraints to check.

Example 3 — Identical Elements

$ Input: nums = [2,2]

› Output: 6

💡 Note: Valid pairs include ([0,0],[2,2]), ([0,1],[2,1]), ([0,2],[2,0]), ([1,1],[1,1]), ([1,2],[1,0]), ([2,2],[0,0]). Total count is 6.

Constraints

1 ≤ nums.length ≤ 2000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is recognizing this as a constrained counting problem where we split each nums[i] into arr1[i] + arr2[i] with monotonic constraints. The optimal approach uses dynamic programming with mathematical optimization to achieve O(n × max(nums)) time complexity by tracking valid states efficiently.

Common Approaches

✓ Dp 1d

⏱️ Time: N/A Space: N/A

Brute Force Recursion

⏱️ Time: O(2^n) Space: O(n)

For each position, enumerate all possible values for arr1[i] from 0 to nums[i], ensuring arr1 is non-decreasing and arr2 is non-increasing. This explores the entire solution space recursively.

Dynamic Programming

⏱️ Time: O(n × max(nums)²) Space: O(n × max(nums)²)

Build a DP table where dp[i][j][k] represents the number of ways to fill positions 0 to i-1 with arr1[i-1] = j and arr2[i-1] = k. This eliminates redundant calculations from the brute force approach.

Optimized DP with Mathematical Insight

⏱️ Time: O(n × max(nums)) Space: O(max(nums))

Transform the problem by recognizing that we can use a 2D DP approach where we track the range of valid values more efficiently. Instead of tracking exact previous values, we can use mathematical properties to compute transitions faster.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX 1001

long long solution(int nums[], int n) {
    
    if (n == 1) {
        return nums[0] + 1;
    }

    long long prevDp[MAX] = {0};
    long long currDp[MAX] = {0};

    // Initialize for position 0
    for (int a1 = 0; a1 <= nums[0]; a1++) {
        prevDp[a1] = 1;
    }

    for (int i = 1; i < n; i++) {

        for (int j = 0; j < MAX; j++)
            currDp[j] = 0;

        for (int a1 = 0; a1 <= nums[i]; a1++) {
            int a2 = nums[i] - a1;
            if (a2 < 0)
                continue;

            long long count = 0;

            for (int prevA1 = 0; prevA1 <= nums[i-1]; prevA1++) {
                long long ways = prevDp[prevA1];
                if (ways == 0)
                    continue;

                int prevA2 = nums[i-1] - prevA1;

                if (prevA1 <= a1 && prevA2 >= a2) {
                    count = (count + ways) % MOD;
                }
            }

            if (count > 0) {
                currDp[a1] = count;
            }
        }

        for (int j = 0; j < MAX; j++) {
            prevDp[j] = currDp[j];
        }
    }

    long long result = 0;

    for (int a1 = 0; a1 < MAX; a1++) {
        result = (result + prevDp[a1]) % MOD;
    }

    return result;
}

int main() {

    char line[10000];
    fgets(line, sizeof(line), stdin);

    int nums[1000];
    int n = 0;

    line[strcspn(line, "\n")] = 0;

    char *token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }

    printf("%lld\n", solution(nums, n));

    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

⚡ Linearithmic Space

26.7K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen