3251. Find the Count of Monotonic Pairs II

HardArrayMathDynamic ProgrammingCombinatoricsPrefix Sum

Problem Description

You are given an array of positive integers nums of length n.

We define a pair of non-negative integer arrays (arr1, arr2) as monotonic if the following conditions are met:

Both arrays have a length of n.
arr1 is monotonically non-decreasing, meaning arr1[0] <= arr1[1] <= ... <= arr1[n - 1].
arr2 is monotonically non-increasing, meaning arr2[0] >= arr2[1] >= ... >= arr2[n - 1].
For every index i from 0 to n-1, the sum arr1[i] + arr2[i] is equal to nums[i].

The task is to return the count of such monotonic pairs. Due to potentially large results, return the answer modulo (10^9 + 7).

Intuition

To solve this problem, the approach involves dynamic programming with prefix sum optimization.

Define DP State: Let ( f[i][j] ) represent the count of monotonic pairs for the subarray ([0, \ldots, i]) where ( \text{arr1}[i] = j ).
Initialization: At the start, for ( i = 0 ), we know ( \text{arr1}[0] ) can take any value from 0 to (\text{nums}[0]), so ( f[0][j] = 1 ) for ( 0 \leq j \leq \text{nums}[0] ).
Transition: For ( i > 0 ), we need to calculate ( f[i][j] ) by considering prior states ( f[i-1][j'] ). Given that ( \text{arr1} ) is non-decreasing, ( j' \leq j ). Regarding ( \text{arr2} ), because it's non-increasing, the transition must ensure ( \text{nums}[i] - j \leq \text{nums}[i-1] - j' ). Therefore, ( j' ) is limited to be less than or equal to ( \min(j, j + \text{nums}[i-1] - \text{nums}[i]) ).
Result Calculation: The final count of monotonic pairs will be the sum of the values ( f[n-1][j] ) for all possible ( j ) such that ( 0 \leq j \leq \text{nums}[n-1] ).

By using dynamic programming, we efficiently build up the solution, employing prefix sums to aggregate the results and adhere to constraints as we progress through the array.

Learn more about Math, Dynamic Programming, Combinatorics and Prefix Sum patterns.

Solution Approach

The solution employs a dynamic programming approach with prefix sum optimization to efficiently count the monotonic pairs.

Initialization:
- Define f as a 2D list where f[i][j] represents the number of valid monotonic pairs with arr1[i] = j.
- Initialize the array f of dimensions n x (m+1) where n is the length of nums and m is the maximum value in nums.
- Populate f[0][j] with 1 for each j from 0 to nums[0] since the first element has straightforward assignments.
Prefix Sum Calculation:
- Use the prefix sum array s to store cumulative sums of the previous row in f; this allows quick look-up of the sum of f[i-1][j'] values.
DP Transition:
- For each i from 1 to n-1 and each possible value of j from 0 to nums[i], compute:
```
k = min(j, j + nums[i - 1] - nums[i])
```
  This ensures that both arr1 and arr2 maintain their respective monotonic properties.
- If k is non-negative, update f[i][j] as:
```
f[i][j] = s[k] % mod
```
  where mod = 10**9 + 7 is used to ensure results remain within computational limits.

Final Result:

Sum up all possibilities in the last row of f to retrieve the total count of monotonic pairs:

result = sum(f[n-1][:nums[-1] + 1]) % mod

This algorithm efficiently gathers the total valid combinations by leveraging both dynamic programming and prefix sum techniques to satisfy the problem's constraints and optimize performance.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have nums = [2, 3].

Step-by-Step Explanation:

Initialization:
- Define f, a 2D list where f[i][j] represents the number of valid monotonic pairs for subarray [0, ..., i] with arr1[i] = j.
- Initialize f as follows, with n = 2 (length of nums) and m = 3 (maximum value in nums):
```
f = [[0] * (3 + 1) for _ in range(2)]
```
- Initial population of f[0][j]:
```
f[0][0] = 1
f[0][1] = 1
f[0][2] = 1
```
This initialization represents that arr1[0] can be 0, 1, or 2 for nums[0] = 2.

Prefix Sum Calculation:

Compute prefix sums for efficient transition calculation. Let's calculate s for i = 0 where s[j] is the cumulative sum of f[0][...] up to j:

s[0] = f[0][0] = 1
s[1] = s[0] + f[0][1] = 2
s[2] = s[1] + f[0][2] = 3
s[3] = s[2]  // there is no `f[0][3]`, keep it 3

DP Transition:
- For i = 1, observe that nums[1] = 3.
- Calculate f[i][j]:
  - For j = 0, k = min(0, 0 + 2 - 3) = -1. Since k is negative, we skip this.
  - For j = 1, k = min(1, 1 + 2 - 3) = 0:
```
f[1][1] = s[0] % mod = 1
```
  - For j = 2, k = min(2, 2 + 2 - 3) = 1:
```
f[1][2] = s[1] % mod = 2
```
  - For j = 3, k = min(3, 3 + 2 - 3) = 2:
```
f[1][3] = s[2] % mod = 3
```

Final Result Calculation:

Sum the possibilities for the last index, i = 1, from f[n-1][...]:

result = (f[1][0] + f[1][1] + f[1][2] + f[1][3]) % mod = (0 + 1 + 2 + 3) % mod = 6

Thus, the total number of valid monotonic pairs is 6. This walkthrough demonstrates how the transition states are managed and calculated with the dynamic programming and prefix sum approach.

Solution Implementation

1from itertools import accumulate
2from typing import List
3
4class Solution:
5    def countOfPairs(self, nums: List[int]) -> int:
6        mod = 10**9 + 7  # Large prime for modulo operations to prevent overflow
7        n = len(nums)  # Get the length of nums
8        m = max(nums)  # Find the maximum value in nums
9        # Initialize a 2D list to store results for subproblems
10        f = [[0] * (m + 1) for _ in range(n)]  
11      
12        # Base case: fill the first row based on the first number
13        for j in range(nums[0] + 1):
14            f[0][j] = 1
15      
16        # Fill the DP table for the remaining elements
17        for i in range(1, n):
18            # Create a cumulative sum of the previous row in the DP table
19            s = list(accumulate(f[i - 1]))
20            for j in range(nums[i] + 1):
21                # Calculate the maximum valid 'k' such that the sequence remains non-decreasing
22                k = min(j, j + nums[i - 1] - nums[i])
23                if k >= 0:
24                    # Use the cumulative sum to update the current cell
25                    f[i][j] = s[k] % mod
26      
27        # Calculate the sum of the last valid row modulo mod
28        return sum(f[-1][: nums[-1] + 1]) % mod
29

1import java.util.Arrays;
2
3class Solution {
4    public int countOfPairs(int[] nums) {
5        final int MOD = (int) 1e9 + 7; // Define the modulo for results to prevent overflow
6        int n = nums.length;
7        int maxValue = Arrays.stream(nums).max().getAsInt(); // Find the maximum value in nums array
8      
9        // f[i][j] represents the number of ways to form valid pairs considering first i elements with max pair value j
10        int[][] f = new int[n][maxValue + 1];
11
12        // Initialize for the first element
13        for (int j = 0; j <= nums[0]; ++j) {
14            f[0][j] = 1; // Base case: one way for maximum pair value up to nums[0]
15        }
16
17        int[] prefixSum = new int[maxValue + 1]; // This helps in calculating prefix sums efficiently
18
19        // Iterate through the rest of the elements
20        for (int i = 1; i < n; ++i) {
21            prefixSum[0] = f[i - 1][0]; // Start computing prefix sums from 0
22
23            // Compute prefix sums for f[i-1][*]
24            for (int j = 1; j <= maxValue; ++j) {
25                prefixSum[j] = (prefixSum[j - 1] + f[i - 1][j]) % MOD;
26            }
27
28            // Fill f[i][*] considering nums[i]
29            for (int j = 0; j <= nums[i]; ++j) {
30                // Calculate maximum k such that it fits the condition
31                int k = Math.min(j, j + nums[i - 1] - nums[i]);
32                if (k >= 0) {
33                    f[i][j] = prefixSum[k]; // Use prefix sums to calculate number of ways
34                }
35            }
36        }
37
38        // Calculate the final answer by summing up possible values at the last element stage
39        int result = 0;
40        for (int j = 0; j <= nums[n - 1]; ++j) {
41            result = (result + f[n - 1][j]) % MOD;
42        }
43
44        return result; // Return the total count of valid pairs
45    }
46}
47

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to count the number of pairs (i, j) such that
7    // nums[i] <= nums[j] for i < j.
8    int countOfPairs(std::vector<int>& nums) {
9        const int mod = 1e9 + 7;  // Define modulo constant for large number operations
10        int n = nums.size();  // Get size of the input vector
11        int maxNum = *std::max_element(nums.begin(), nums.end());  // Find the maximum element in nums
12
13        // Create a 2D vector for dynamic programming
14        // f[i][j] will store the number of pairs ending at nums[i] with j
15        std::vector<std::vector<int>> f(n, std::vector<int>(maxNum + 1));
16
17        // Initialize the first row
18        for (int j = 0; j <= nums[0]; ++j) {
19            f[0][j] = 1;  // Every single element can be the start of a pair
20        }
21
22        // Auxiliary array to keep prefix sums
23        std::vector<int> prefixSum(maxNum + 1);
24
25        // Fill the DP table
26        for (int i = 1; i < n; ++i) {
27            // Calculate prefix sums for f[i-1]
28            prefixSum[0] = f[i - 1][0];
29            for (int j = 1; j <= maxNum; ++j) {
30                prefixSum[j] = (prefixSum[j - 1] + f[i - 1][j]) % mod;
31            }
32
33            // Update f[i] using prefix sums
34            for (int j = 0; j <= nums[i]; ++j) {
35                int k = std::min(j, j + nums[i - 1] - nums[i]);
36                if (k >= 0) {
37                    f[i][j] = prefixSum[k];
38                }
39            }
40        }
41
42        // Calculate the total number of valid pairs
43        int result = 0;
44        for (int j = 0; j <= nums[n - 1]; ++j) {
45            result = (result + f[n - 1][j]) % mod;
46        }
47
48        return result;  // Return the final count of pairs
49    }
50};
51

1function countOfPairs(nums: number[]): number {
2    const MOD = 1e9 + 7; // Define the modulus value to handle large numbers
3    const n = nums.length; // Get the length of the input array
4    const maxNum = Math.max(...nums); // Find the maximum number in the array
5
6    // Initialize a 2D array 'f' with dimensions n x (maxNum + 1) filled with 0
7    const f: number[][] = Array.from({ length: n }, () => Array(maxNum + 1).fill(0));
8
9    // Base case for the DP array: fill the first row up to nums[0] with 1
10    for (let j = 0; j <= nums[0]; j++) {
11        f[0][j] = 1;
12    }
13
14    // Initialize a helper array 'g' for prefix sums, also filled with 0
15    const g: number[] = Array(maxNum + 1).fill(0);
16
17    // Iterate through the array starting from the second element
18    for (let i = 1; i < n; i++) {
19        g[0] = f[i - 1][0]; // Initialize the first element of 'g' to the first of the previous row in 'f'
20      
21        // Calculate prefix sums for the current row in 'f' up to 'maxNum'
22        for (let j = 1; j <= maxNum; j++) {
23            g[j] = (g[j - 1] + f[i - 1][j]) % MOD;
24        }
25
26        // Fill in the current row in 'f' for values up to nums[i]
27        for (let j = 0; j <= nums[i]; j++) {
28            const k = Math.min(j, j + nums[i - 1] - nums[i]); // Determine the index for which to use the prefix sum
29            if (k >= 0) {
30                f[i][j] = g[k]; // Assign the appropriate prefix sum to f[i][j]
31            }
32        }
33    }
34
35    let ans = 0; // Initialize the answer
36
37    // Sum up the last row of 'f' to get the total count of pairs
38    for (let j = 0; j <= nums[n - 1]; j++) {
39        ans = (ans + f[n - 1][j]) % MOD;
40    }
41
42    return ans; // Return the final computed answer
43}
44

Time and Space Complexity

The time complexity is O(n × m), where n is the length of the list nums, and m is the maximum value in the array nums. This is because we iterate through each element in nums and perform operations up to the maximum value m for each element.

The space complexity is also O(n × m). This arises from the use of a 2D list f, where one dimension corresponds to the size of the list nums (n), and the other corresponds to the maximum value in nums plus one (m + 1), leading to the complexity of O(n × m).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: