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] <= 1000Problem Overview: You receive 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 (a, b) exist.
Approach 1: Dynamic Programming with Prefix Sum (O(n * m) time, O(n * m) space)
Let dp[i][x] represent the number of ways where a[i] = x. Since a[i] + b[i] = nums[i], x ranges from 0 to nums[i]. The monotonic constraints produce a transition constraint from the previous value prev: a[i] ≥ prev (non‑decreasing) and nums[i] - a[i] ≤ nums[i-1] - prev (because b must be non‑increasing). Rearranging gives a[i] ≥ prev + max(0, nums[i] - nums[i-1]). For each x, you sum all valid prev values that satisfy this bound. Direct summation would be O(m²), so maintain prefix sums to compute range totals in O(1). Iterate through the array, update the DP row using prefix sums of the previous row, and accumulate counts modulo 1e9+7. This approach uses standard dynamic programming combined with prefix sums to keep transitions efficient.
Approach 2: Combinatorial Transformation (O(n * m) time, O(m) space)
The constraints can be simplified by analyzing the required increase in a. Define d[i] = max(0, nums[i] - nums[i-1]). From the inequality above, a[i] must increase by at least d[i] compared to a[i-1]. Subtract the cumulative minimum increases to transform the sequence into a new variable where the monotonic requirement becomes simple non‑decreasing growth with bounded limits. After shifting the bounds, the remaining choices resemble distributing increments across positions, which can be counted using combinatorial reasoning or DP with cumulative counts. This interpretation connects the problem to combinatorics and array constraint transformations. It reduces repeated DP transitions and keeps only the valid ranges for each position.
Recommended for interviews: The dynamic programming approach with prefix sums is the expected solution. It clearly models the constraints and runs in O(n * m), which fits the limits. Starting with the DP formulation shows understanding of state transitions, while optimizing with prefix sums demonstrates the ability to reduce nested summations.
The idea is to use a dynamic programming table to keep track of the number of ways to fill the `arr1` and `arr2` arrays up to each index such that they satisfy the constraints of being monotonic. For each index `i` and each possible value of `arr1[i]`, we'll compute the number of ways to choose `arr1` values up to `i` such that the sum `arr1[i] + arr2[i] = nums[i]` and `arr1` is non-decreasing and `arr2` is non-increasing.
Instead of explicitly constructing the arrays, think of the problem in terms of counting the number of valid configurations directly using combinatorial mathematics. The conditions can be interpreted as counting sequences of with certain properties, and these can be summed up using properties of combinatorics, especially binomial coefficients.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | — |
| Combinatorial Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Sum | O(n * m) | O(n * m) | General solution that directly models monotonic constraints |
| Combinatorial Transformation | O(n * m) | O(m) | When deriving mathematical bounds to reduce DP transitions |
3251. Find the Count of Monotonic Pairs II | Weekly Leetcode 410 • codingMohan • 2,505 views views
Watch 4 more video solutions →Practice Find the Count of Monotonic Pairs II with our built-in code editor and test cases.
Practice on FleetCode