Find the Count of Monotonic Pairs I - Practice Coding Problems

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: 6

💡 Note: For each position, arr1 can be 0-5. Valid pairs: (0,5),(1,4),(2,3),(3,2),(4,1),(5,0) where arr1 is non-decreasing and arr2 is non-increasing.

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

Understanding the Visualization

Input

Array nums = [2,3,2] to split into arr1 + arr2

Constraints

arr1 non-decreasing, arr2 non-increasing, arr1[i] + arr2[i] = nums[i]

Count

Find all valid (arr1, arr2) pairs

Key Takeaway

🎯 Key Insight: Use DP to track valid arr1 values at each position, ensuring monotonic constraints are maintained

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

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n × max_val²)	O(max_val)	Build solution iteratively using 2D DP table tracking valid (arr1, arr2) pairs
Recursive Brute Force	O(k^n)	O(n)	Try all possible values for arr1 and arr2 at each position with constraints
Dynamic Programming with Memoization	O(n * max_val²)	O(n * max_val²)	Use memoization to cache results for (position, prev_arr1, prev_arr2) states

Bottom-Up Dynamic Programming — Algorithm Steps

Step 1: Create DP table dp[pos][arr1_val] = count of valid ways
Step 2: Initialize base case for position 0
Step 3: For each position, compute valid transitions from previous position
Step 4: Sum all valid final states

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set up DP for first position with all valid arr1 values

Transition

For each position, compute valid transitions from previous

Accumulate

Sum all final states for total count

Code -

solution.c — C

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

const int MOD = 1000000007;

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* nums, int n) {
    if (n == 0) return 0;
    
    // dp[arr1_val] = count of ways with arr1[pos] = arr1_val
    int* prevDp = calloc(nums[0] + 1, sizeof(int));
    
    // Initialize first position
    for (int arr1Val = 0; arr1Val <= nums[0]; arr1Val++) {
        prevDp[arr1Val] = 1;
    }
    
    // Process each subsequent position
    for (int pos = 1; pos < n; pos++) {
        int* currDp = calloc(nums[pos] + 1, sizeof(int));
        
        for (int currArr1 = 0; currArr1 <= nums[pos]; currArr1++) {
            int currArr2 = nums[pos] - currArr1;
            
            // Check all valid previous arr1 values
            for (int prevArr1 = 0; prevArr1 <= min(currArr1, nums[pos-1]); prevArr1++) {
                int prevArr2 = nums[pos-1] - prevArr1;
                
                // Check if arr2 maintains non-increasing order
                if (prevArr2 >= currArr2) {
                    currDp[currArr1] = ((long long)currDp[currArr1] + prevDp[prevArr1]) % MOD;
                }
            }
        }
        
        free(prevDp);
        prevDp = currDp;
    }
    
    long long result = 0;
    for (int i = 0; i <= nums[n-1]; i++) {
        result = (result + prevDp[i]) % MOD;
    }
    
    free(prevDp);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × max_val²)

For each of n positions, we check all valid arr1 value pairs (current and previous)

✓ Linear Growth

Space Complexity

O(max_val)

Can optimize to use only one array since we only need previous position data

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler