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:
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:
([0, 1, 1], [2, 2, 1])([0, 1, 2], [2, 2, 0])([0, 2, 2], [2, 1, 0])([1, 2, 2], [1, 1, 0])Example 2:
Input: nums = [5,5,5,5]
Output: 126
Constraints:
1 <= n == nums.length <= 20001 <= nums[i] <= 50Problem Overview: You are given an integer array nums. Build two arrays a and b such that a[i] + b[i] = nums[i], a is non‑decreasing, and b is non‑increasing. The task is to count how many valid pairs of arrays satisfy these monotonic constraints.
Approach 1: Backtracking with Pruning (Exponential time, O(n) space)
The most direct strategy enumerates all valid values for a[i] from 0 to nums[i] and derives b[i] = nums[i] - a[i]. While exploring recursively, enforce the constraints a[i] ≥ a[i-1] and b[i] ≤ b[i-1]. Branches that violate monotonicity are pruned early. This approach clearly models the constraints but still explores a large search tree. Time complexity is exponential in the worst case, making it useful mainly for understanding the state transitions.
Approach 2: Dynamic Programming with Memoization (O(n · m²) time, O(n · m) space)
Convert the recursive idea into dynamic programming. Define dp[i][a] as the number of ways where a[i] = a. The corresponding value for the second array is b[i] = nums[i] - a. For each previous value prev, transition is valid only if a ≥ prev and nums[i] - a ≤ nums[i-1] - prev. Memoization caches results for each state (i, prev), eliminating repeated recursion. This approach reduces repeated work but still checks many transitions between states.
Approach 3: Dynamic Programming with Prefix Sum Optimization (O(n · m) time, O(m) space)
The optimal solution observes that transitions depend only on ranges of valid previous values. Let dp[i][a] represent ways where a[i] = a. Valid previous values must satisfy prev ≤ a and also respect the constraint derived from the second array: a ≥ prev + nums[i] - nums[i-1]. This creates a contiguous interval of allowable prev. Instead of iterating that range every time, maintain cumulative sums using a prefix sum array. Each DP value becomes a constant-time range query, reducing the overall complexity to linear in n × max(nums[i]).
Approach 4: Combinatorial Counting (O(n · m) time, O(m) space)
The constraints effectively bound how much a can increase between indices. By interpreting valid assignments as distributing increments while respecting limits derived from nums, the problem can be expressed using combinatorics. Precomputed binomial coefficients or cumulative counts help count feasible configurations without enumerating each pair explicitly. This approach works well when constraints are tight and when a mathematical counting formulation is easier than explicit DP transitions.
Recommended for interviews: The dynamic programming approach with prefix sums is the expected solution. Start with the recursive or memoized formulation to demonstrate understanding of the state definition and monotonic constraints. Then optimize transitions with prefix sums to reach O(n · m) time, which shows strong command of array DP optimization techniques.
In this approach, we utilize dynamic programming (DP) with memoization to efficiently compute the count of monotonic pairs. The idea is to utilize a DP table where dp[i][j] represents the number of ways to form valid monotonic pairs up to the i-th index considering different sums of arr1 up to j.
The transition would be based on the fact that if we are at a certain position i in nums, then for each possible sum that makes arr1[i], we distribute the remaining sum to arr2[i] in non-increasing order to ensure the monotonic condition, updating our DP states accordingly.
This Python solution uses a 2D DP table where dp[i][j] tracks the number of ways we can form valid monotonic pairs up to index i using sum of j for arr1[i]. For each number x in nums[i - 1], valid states are accumulated from states of previous positions that respect non-decreasing constraints of arr1. Finally, sum the values of the last row which gives the total count of valid pairs modulo 10^9 + 7.
Python
Time Complexity: O(n * 51 * 51) where n is the length of nums.
Space Complexity: O(n * 51).
In this approach, we apply a backtracking technique with pruning to explore possible valid pairs. By recursively constructing the sequences arr1 and arr2 while ensuring they meet the monotonic constraints, we can count the valid configurations. With strategic pruning to stop early when conditions aren't satisfied (like when sums don't match or monotonicity violated), we can significantly reduce unnecessary steps.
This C++ solution employs a recursive backtracking mechanism with memoization. The function countMonotonicPairsUtil recursively attempts to build valid sequences, using a matrix dp to store state results for revisitation, thus avoiding redundant calculations. The pruning is evident as we start from a previous maximal sum prev to maintain monotonicity.
C++
Time Complexity: Potentially exponential without pruning but reduced to O(n * 51) via memoization.
Space Complexity: O(n * 51) due to the usage of the dp cache.
This approach utilizes dynamic programming to solve the problem efficiently. First, define the function dp(i, a) to count valid arrays from index i, with arr1[i] = a. We go forward from the current index and compute possibilities maintaining the conditions of being monotonically non-decreasing for arr1 and non-increasing for arr2. The result from dp(0, 0) will be our answer.
The implementation uses a 2D dp array where dp[i][a] holds the count of monotonic arrays starting at index i, with the first element of arr1 being a. We fill this table iteratively. The nested loops ensure all conditions are checked, and results are accumulated from the base case (dp[n] initialized to 1, representing completion of the array construction). The function finally returns dp[0][0], which translates to the number of ways to construct the complete monotonically valid arrangement.
Python
JavaScript
Time Complexity: O(n * max(nums)^2)
Space Complexity: O(n * max(nums))
This approach uses the properties of permutations and combinations to count valid monotonic sequence pairs. By iterating over possible starting values and applying combinatorial principles, we count the valid configurations directly. This involves calculating potential values for arr1 and arr2 directly using constraints.
The function initializes a 2D dp array and fills it using a backtracking dynamic programming approach. We compute valid a, b pairs for each index ensuring monotonically non-decreasing and non-increasing conditions, respectively, ensure a valid pair. This aids in optimizing the combinatorial calculations needed across different configurations.
Time Complexity: O(n * max(nums)^2)
Space Complexity: O(n * max(nums))
We define f[i][j] to represent the number of monotonic array pairs for the subarray [0, ldots, i] where arr1[i] = j. Initially, f[i][j] = 0, and the answer is sum_{j=0}^{nums[n-1]} f[n-1][j].
When i = 0, we have f[0][j] = 1 for 0 leq j leq nums[0].
When i > 0, we can calculate f[i][j] based on f[i-1][j']. Since arr1 is non-decreasing, j' leq j. Additionally, since arr2 is non-increasing, nums[i] - j leq nums[i - 1] - j'. Thus, j' leq min(j, j + nums[i - 1] - nums[i]).
The answer is sum_{j=0}^{nums[n-1]} f[n-1][j].
The time complexity is O(n times m), and the space complexity is O(n times m). Here, n represents the length of the array nums, and m represents the maximum value in the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memoization | Time Complexity: O(n * 51 * 51) where n is the length of nums. |
| Backtracking with Pruning | Time Complexity: Potentially exponential without pruning but reduced to O(n * 51) via memoization. |
| Dynamic Programming Approach | Time Complexity: O(n * max(nums)^2) |
| Combinatorial Approach | Time Complexity: O(n * max(nums)^2) |
| Dynamic Programming + Prefix Sum Optimization | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | Exponential | O(n) | Useful for understanding constraints or verifying small inputs |
| DP with Memoization | O(n · m²) | O(n · m) | Good intermediate step when converting recursion to DP |
| DP with Prefix Sum Optimization | O(n · m) | O(m) | Optimal solution for large constraints |
| Combinatorial Counting | O(n · m) | O(m) | When the problem can be reframed as counting constrained distributions |
3250 Find the Count of Monotonic Pairs I || How to 🤔 in Interview || 3D DP || O(50*50*N) • Ayush Rao • 1,866 views views
Watch 9 more video solutions →Practice Find the Count of Monotonic Pairs I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor