Watch 10 video solutions for Find the Count of Monotonic Pairs I, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by Ayush Rao has 1,866 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |