LeetCode 3250 - Find the Count of Monotonic Pairs I

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Combinatorics, Prefix Sum

Solution

Problem Understanding

The problem asks us to count the number of valid pairs of arrays (arr1, arr2) derived from a given array nums. Both arr1 and arr2 have the same length as nums. The constraints on these arrays are:

arr1 is non-decreasing.
arr2 is non-increasing.
At each index i, the sum of corresponding elements equals the original number: arr1[i] + arr2[i] = nums[i].
All elements in arr1 and arr2 are non-negative integers.

The input nums represents the target sums for each index, while the output is the count of valid (arr1, arr2) pairs that satisfy all monotonicity and sum constraints. Since the number of valid pairs can be very large, the answer must be returned modulo 10^9 + 7.

The constraints give us key information about the problem scale: the length n can go up to 2000 and the values in nums are small, at most 50. This suggests a combinatorial solution with dynamic programming is feasible but brute force enumeration of all possible arrays is not.

Important edge cases include nums with repeated values (which allows multiple arrangements), strictly increasing or decreasing sequences, and the smallest array of length 1.

Approaches

Brute Force

The naive approach would be to generate all possible non-decreasing sequences for arr1 and, for each, calculate arr2[i] = nums[i] - arr1[i]. We would then check if arr2 is non-increasing. This guarantees correctness because it explicitly enumerates all possible arrays that satisfy the sum condition and checks the monotonicity. However, this approach is too slow: for each element nums[i] we have up to nums[i] + 1 choices for arr1[i], giving a time complexity roughly O(product of nums[i]), which is exponential.

Key Insight for Optimal Approach

The problem has a dynamic programming structure because the number of valid sequences up to index i depends only on the valid sequences up to index i-1. Let dp[i][a] denote the number of valid sequences of arr1 of length i+1 ending with arr1[i] = a.

Given the monotonicity requirement for arr1 (non-decreasing), we can transition from dp[i-1][prev] to dp[i][a] only if prev <= a. Additionally, arr2[i] = nums[i] - a must be non-negative and arr2[i] <= arr2[i-1], i.e., a >= nums[i] - arr2[i-1]. Using these conditions, we can efficiently compute the DP table using prefix sums to avoid iterating over all previous states.

This reduces the problem to O(n * max(nums)^2) complexity, which is feasible given n <= 2000 and nums[i] <= 50.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(product of nums[i])	O(n)	Generate all arr1 sequences and check arr2
Optimal	O(n * max_num^2)	O(max_num)	DP with prefix sums for monotonic constraints

Algorithm Walkthrough

Initialize MOD = 10^9 + 7.
Let max_num be the maximum value in nums.
Initialize a DP array dp_prev of size max_num + 1, where dp_prev[a] counts valid sequences ending with arr1[i] = a for the previous index. Start with dp_prev[a] = 1 for 0 <= a <= nums[0].
Iterate over each index i from 1 to n-1:
Initialize dp_curr as an array of zeros of size max_num + 1.
Compute a prefix sum array prefix over dp_prev to enable efficient cumulative sums.
For each possible arr1[i] = a (from 0 to nums[i]):
Compute the allowed range of prev for arr1[i-1] satisfying non-decreasing: prev <= a.
Compute the allowed range for arr2[i-1] satisfying non-increasing: arr2[i-1] >= nums[i] - a.
Use the prefix sums to quickly sum over dp_prev[prev] that satisfy both conditions and assign to dp_curr[a].
Set dp_prev = dp_curr.
After processing all indices, sum all dp_prev[a] for 0 <= a <= nums[n-1].
Return the sum modulo 10^9 + 7.

Why it works: At each step, the DP table maintains a count of valid sequences ending with a specific last value. The prefix sum ensures that transitions respect the monotonicity constraints efficiently. By the final index, dp_prev contains all counts of valid arr1 sequences, and by construction, arr2 is guaranteed to be non-increasing.

Python Solution

from typing import List

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        max_num = max(nums)
        
        dp_prev = [0] * (max_num + 1)
        for a in range(nums[0] + 1):
            dp_prev[a] = 1
        
        for i in range(1, n):
            dp_curr = [0] * (max_num + 1)
            prefix = [0] * (max_num + 2)
            for j in range(max_num + 1):
                prefix[j + 1] = (prefix[j] + dp_prev[j]) % MOD
            
            for a in range(nums[i] + 1):
                min_prev = max(0, nums[i] - (nums[i-1]))  # arr2[i-1] >= arr2[i] => a >= nums[i] - arr2[i-1]
                max_prev = a  # arr1 non-decreasing
                if min_prev <= max_prev:
                    dp_curr[a] = (prefix[max_prev + 1] - prefix[min_prev]) % MOD
            
            dp_prev = dp_curr
        
        return sum(dp_prev) % MOD

The Python implementation follows the algorithm closely. dp_prev stores counts for the previous index. prefix allows constant-time range sums to count valid transitions efficiently. The modulo operation ensures large numbers are handled correctly.

Go Solution

func countOfPairs(nums []int) int {
    const MOD = 1_000_000_007
    n := len(nums)
    maxNum := 0
    for _, v := range nums {
        if v > maxNum {
            maxNum = v
        }
    }

    dpPrev := make([]int, maxNum+1)
    for a := 0; a <= nums[0]; a++ {
        dpPrev[a] = 1
    }

    for i := 1; i < n; i++ {
        dpCurr := make([]int, maxNum+1)
        prefix := make([]int, maxNum+2)
        for j := 0; j <= maxNum; j++ {
            prefix[j+1] = (prefix[j] + dpPrev[j]) % MOD
        }

        for a := 0; a <= nums[i]; a++ {
            minPrev := 0
            if nums[i]-nums[i-1] > 0 {
                minPrev = nums[i] - nums[i-1]
            }
            maxPrev := a
            if minPrev <= maxPrev {
                dpCurr[a] = (prefix[maxPrev+1] - prefix[minPrev] + MOD) % MOD
            }
        }
        dpPrev = dpCurr
    }

    result := 0
    for _, v := range dpPrev {
        result = (result + v) % MOD
    }
    return result
}

The Go implementation mirrors Python, with adjustments for slice initialization and modulo arithmetic to avoid negative numbers.

Worked Examples

Example 1: nums = [2,3,2]

Step through DP:

i	arr1 possibilities	dp_prev counts
0	0,1,2	1,1,1
1	0,1,2,3	compute via prefix sums: dp_curr = 1,2,1,0
2	0,1,2	dp_prev = 1,2,1

Sum = 1+2+1 = 4

Example 2: nums = [5,5,5,5]

By DP transitions, total count = 126.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * max_num^2)	Iterate over n elements, for each a <= nums[i], sum over previous prefix
Space	O(max_num)	Store DP array of size max_num + 1

The complexity is manageable because max_num <= 50.

Test Cases

# Provided examples