Find the Count of Monotonic Pairs I - 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,1,1],[2,2,1]), ([0,1,2],[2,2,0]), ([0,2,2],[2,1,0]), ([1,2,2],[1,1,0]). Each satisfies arr1 non-decreasing and arr2 non-increasing constraints.

Example 2 — Minimum Size

$ Input: nums = [5,5]

› Output: 21

💡 Note: For nums=[5,5], we need arr1 non-decreasing and arr2 non-increasing. There are 21 valid monotonic pairs total: for each valid arr1[0] value from 0 to 5, we count valid arr1[1] values that maintain both monotonic constraints.

Example 3 — Single Element

$ Input: nums = [3]

› Output: 4

💡 Note: Single position allows arr1 values 0,1,2,3 with corresponding arr2 values 3,2,1,0. All are valid since no monotonic constraints between positions.

Constraints

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

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 f Meta 8 M Microsoft 6

The key insight is to use dynamic programming to count valid combinations where arr1 is non-decreasing and arr2 is non-increasing, with arr1[i] + arr2[i] = nums[i]. Best approach uses bottom-up DP with space optimization. Time: O(n × max_val²), Space: O(max_val)

Common Approaches

✓ Hash Map

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

Bottom-Up Dynamic Programming

⏱️ Time: O(n × max_val²) Space: O(max_val)

Use bottom-up DP where dp[i][j] represents number of ways to fill first i positions with arr1[i-1] = j. For each position, compute transitions based on monotonic constraints.

Dynamic Programming with Memoization

⏱️ Time: O(n * max_val²) Space: O(n * max_val²)

Optimize the recursive approach by memoizing results for each unique state defined by current position and previous values of arr1 and arr2. This eliminates redundant calculations.

Recursive Brute Force

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

For each position, try all valid values for arr1[i] (from previous arr1[i-1] to nums[i]) and compute arr2[i] = nums[i] - arr1[i], checking if arr2 maintains non-increasing order.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

#define MOD 1000000007

int countMonotonicPairs(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    if (numsSize == 1) return nums[0] + 1;
    
    // dp[i][j] = number of ways to fill first i positions with arr1[i-1] = j
    // We need to track all possible values of arr1[i]
    int maxVal = 0;
    for (int i = 0; i < numsSize; i++) {
        maxVal = maxVal > nums[i] ? maxVal : nums[i];
    }
    
    // Use static arrays to avoid stack overflow
    static long long dp[2001][1001];  // [position][arr1_value]
    static long long newDp[1001];
    
    // Initialize for first position
    for (int j = 0; j <= nums[0]; j++) {
        dp[0][j] = 1;
    }
    
    // Fill DP table
    for (int i = 1; i < numsSize; i++) {
        // Clear newDp
        for (int j = 0; j <= maxVal; j++) {
            newDp[j] = 0;
        }
        
        for (int curr = 0; curr <= nums[i]; curr++) {
            // arr1[i] = curr, so arr2[i] = nums[i] - curr
            int arr2_curr = nums[i] - curr;
            
            // Sum over all valid previous values of arr1
            for (int prev = 0; prev <= curr && prev <= nums[i-1]; prev++) {
                // arr1[i-1] = prev, so arr2[i-1] = nums[i-1] - prev
                int arr2_prev = nums[i-1] - prev;
                
                // Check if arr2 is non-increasing: arr2[i-1] >= arr2[i]
                if (arr2_prev >= arr2_curr) {
                    newDp[curr] = (newDp[curr] + dp[i-1][prev]) % MOD;
                }
            }
        }
        
        // Copy newDp to dp[i]
        for (int j = 0; j <= maxVal; j++) {
            dp[i][j] = newDp[j];
        }
    }
    
    // Sum all possibilities for the last position
    long long result = 0;
    for (int j = 0; j <= nums[numsSize-1]; j++) {
        result = (result + dp[numsSize-1][j]) % MOD;
    }
    
    return (int)result;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    
    // Remove brackets and parse
    char* start = strchr(line, '[');
    if (start) {
        start++;
        char* end = strchr(start, ']');
        if (end) *end = '\0';
        
        char* token = strtok(start, ",");
        while (token != NULL) {
            nums[numsSize++] = atoi(token);
            token = strtok(NULL, ",");
        }
    }
    
    int result = countMonotonicPairs(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

285 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