Skip to main content
Talentd

Find the Count of Monotonic Pairs II - Solution & Explanation

HardArrayMathDynamic ProgrammingCombinatorics12 min readAsked at: BNY Mellon
Practice this problem

Problem Statement

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 109 + 7.

 

Example 1:

Input: nums = [2,3,2]

Output: 4

Explanation:

The good pairs are:

  1. ([0, 1, 1], [2, 2, 1])
  2. ([0, 1, 2], [2, 2, 0])
  3. ([0, 2, 2], [2, 1, 0])
  4. ([1, 2, 2], [1, 1, 0])

Example 2:

Input: nums = [5,5,5,5]

Output: 126

 

Constraints:

  • 1 <= n == nums.length <= 2000
  • 1 <= nums[i] <= 1000

Approach Overview

Problem 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.

Approach 1: Dynamic Programming Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Try this approach in the editor →

Approach 2: Combinatorial Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Try this approach in the editor →

Approach 3: Dynamic Programming + Prefix Sum Optimization

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach—
Combinatorial Approach—
Dynamic Programming + Prefix Sum Optimization—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Prefix SumO(n * m)O(n * m)General solution that directly models monotonic constraints
Combinatorial TransformationO(n * m)O(m)When deriving mathematical bounds to reduce DP transitions

Video Solution

3251. Find the Count of Monotonic Pairs II | Weekly Leetcode 410 • codingMohan • 2,566 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Find the Count of Monotonic Pairs II easy or hard?
Find the Count of Monotonic Pairs II is rated Hard because it combines multiple constraints: two monotonic sequences, equation coupling between arrays, and optimized DP transitions. Recognizing the inequality transformation and using prefix sums is the key challenge.
Find the Count of Monotonic Pairs II Python/Java solution
Python and Java implementations typically build a DP table and maintain prefix sums for each row. For every index i and value x, compute the valid previous range and fetch the count using the prefix sum array. The final answer is the sum of dp[n-1][x] for all valid x values.
How to solve Find the Count of Monotonic Pairs II in O(n*m)?
Use dynamic programming where dp[i][x] represents choosing a[i] = x. Determine the valid range of previous values using the constraints from the non‑decreasing a array and non‑increasing b array. Maintain prefix sums of the previous DP row so each transition becomes a constant‑time range query.
What is the best approach for Find the Count of Monotonic Pairs II?
Dynamic programming with prefix sums is the most reliable approach. Define dp[i][x] as the number of ways where a[i] = x and enforce the monotonic constraints between adjacent elements. Prefix sums allow you to compute valid transition ranges in O(1), giving an overall complexity of O(n * m).
Is Find the Count of Monotonic Pairs II asked at Google/Amazon/Meta?
Problems involving constrained dynamic programming and combinatorics frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine monotonic sequences with DP transitions are common in advanced algorithm rounds.
What data structure is used in Find the Count of Monotonic Pairs II?
The core structure is a dynamic programming table combined with a prefix sum array for fast range queries. Arrays are sufficient to store DP states and cumulative sums, making the implementation efficient and cache friendly.
What is the time complexity of Find the Count of Monotonic Pairs II?
The optimized solution runs in O(n * m) time, where n is the length of nums and m is the maximum value in nums. Each state transition is computed using prefix sums instead of nested loops, which prevents an O(m^2) slowdown.

Ready to solve this problem?

Practice Find the Count of Monotonic Pairs II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays