Facebook Pixel

3250. Find the Count of Monotonic Pairs I

HardArrayMathDynamic ProgrammingCombinatoricsPrefix Sum
Leetcode Link

Problem Description

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 10^9 + 7.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To solve this problem, we use a dynamic programming approach to calculate the number of valid monotonic pairs (arr1, arr2) that satisfy the given conditions.

We define f[i][j] as the number of monotonic pairs for the subarray [0, ..., i] where arr1[i] = j. The idea is to build up solutions for subarrays incrementally and utilize prefix sums for optimization.

Here's a step-by-step breakdown of the approach:

  1. Initialization: For the first element, any non-negative integer j such that 0 <= j <= nums[0] can be chosen for arr1[0]. Therefore, we start with f[0][j] = 1 for all valid j.

  2. Transition: For subsequent elements i > 0, the value f[i][j] is accumulated from the previous row f[i-1][j']. Based on the monotonicity conditions:

    • arr1 is non-decreasing: Thus, j' <= j.
    • arr2 is non-increasing: Therefore, the constraint nums[i] - j <= nums[i-1] - j' holds. This gives the relation j' <= min(j, j + nums[i-1] - nums[i]).

    We utilize the prefix sum of f[i-1] to quickly compute the number of valid configurations for feature reduction.

  3. Result Formation: Finally, compute the result for all possible end states f[n-1][j] where 0 <= j <= nums[n-1] for the entire array length n.

This dynamic programming approach ensures that we efficiently count all possible monotonic pairs that match the requirements, considering modulo 10^9 + 7 to manage large numbers.

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

Solution Approach

To solve the problem, we employ a dynamic programming approach combined with prefix sum optimization. This technique helps efficiently compute the number of valid monotonic pairs.

Dynamic Programming + Prefix Sum Optimization

  1. Initialization:

    • We first determine the length of nums as n and the maximum value in nums as m.
    • Set up a 2D dynamic programming table f where f[i][j] represents the number of monotonic pairs for the subarray [0, \ldots, i] with arr1[i] = j.
    • Initially fill f[0][j] = 1 for all 0 <= j <= nums[0].

  2. DP Transition:

    • For each subsequent index i, calculate prefix sums from the previous row f[i-1] for efficient calculation: s = list(accumulate(f[i - 1])).
    • For each possible value j for arr1[i], update f[i][j] using:
      • Find k as min(j, j + nums[i - 1] - nums[i]).
      • If k is valid (k >= 0), set f[i][j] = s[k] % mod.

  3. Result Calculation:

    • Sum all values f[n-1][j] where 0 <= j <= nums[n-1] to get the final count of valid pairs.
    • Return the result modulo 10^9 + 7.

This approach utilizes two loops nested over the indices of the array and possible values of arr1, combined with prefix sum calculation for efficient dynamic programming state updates. It ensures that all conditions for monotonic arrays are respected while counting possibilities.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Consider the array nums = [3, 2, 5]. We aim to count the number of monotonic pairs (arr1, arr2) such that:

  • arr1 is monotonically non-decreasing.
  • arr2 is monotonically non-increasing.
  • arr1[i] + arr2[i] = nums[i] for all i.

Step-by-Step Approach

  1. Initialization:

    • Length of nums (n) is 3.
    • Dynamic programming table f is initialized for each possible j where 0 <= j <= nums[0].
    • Initialize f[0][j] = 1 for j = 0, 1, 2, 3 because these are valid values for arr1[0] that sum with arr2[0] to nums[0].

  2. DP Transition:

    • For i = 1:

      • Calculate the prefix sum from f[0]: s = [1, 2, 3, 4].
      • For each j from 0 to nums[1] = 2:
        • Compute k = min(j, j + nums[0] - nums[1]).
        • For each valid k, compute f[1][j] = s[k] % mod.
      • Key updates:
        • f[1][0] = s[0] = 1
        • f[1][1] = s[1] = 2
        • f[1][2] = s[2] = 3

    • For i = 2:

      • Calculate the prefix sum from f[1]: s = [1, 3, 6].
      • For each j from 0 to nums[2] = 5:
        • Compute k = min(j, j + nums[1] - nums[2]).
        • For each valid k, compute f[2][j] = s[k] % mod.
      • Key updates:
        • f[2][0] = s[0] = 1
        • f[2][1] = s[1] = 3
        • f[2][2] = s[2] = 6
        • f[2][3] = s[3] = 10
        • f[2][4] = s[4] = 15
        • f[2][5] = s[5] = 21

  3. Result Calculation:

    • Sum up all valid f[2][j] where 0 <= j <= nums[2]:
    • Result = (1 + 3 + 6 + 10 + 15 + 21) % (10^9 + 7) = 56.

Thus, the total number of valid monotonic pairs for the given nums is 56.

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  # Constant to take result modulo
7        n = len(nums)    # Length of the input list
8        m = max(nums)    # Maximum value in the input list
9      
10        # Initializing a 2D list 'f' with zeros,
11        # dimensions [n x (m+1)], for dynamic programming
12        f = [[0] * (m + 1) for _ in range(n)]
13      
14        # Base case: Only one way to have no elements exceeding 'nums[0]' 
15        for j in range(nums[0] + 1):
16            f[0][j] = 1
17      
18        # Fill the DP table
19        for i in range(1, n):
20            # Compute prefix sums for the previous row in our DP table
21            s = list(accumulate(f[i - 1]))
22          
23            # Iterate through all possible 'nums[i]' values
24            for j in range(nums[i] + 1):
25                k = min(j, j + nums[i - 1] - nums[i])  # Calculate the boundary
26              
27                # If boundary is valid, update current DP cell
28                if k >= 0:
29                    f[i][j] = s[k] % mod
30      
31        # Calculate the final result by summing all valid end states modulo 'mod'
32        return sum(f[-1][: nums[-1] + 1]) % mod
33
1import java.util.Arrays;
2
3class Solution {
4  
5    public int countOfPairs(int[] nums) {
6        final int MOD = (int) 1e9 + 7; // Define the modulo constant for large numbers
7        int n = nums.length; // Length of the input array
8        int maxNum = Arrays.stream(nums).max().getAsInt(); // Find the maximum number in the array
9
10        int[][] dp = new int[n][maxNum + 1]; // Initialize DP array
11        // Initialize the first row of DP table
12        for (int j = 0; j <= nums[0]; ++j) {
13            dp[0][j] = 1;
14        }
15      
16        int[] prefixSum = new int[maxNum + 1]; // Array to store prefix sums for optimization
17      
18        // Fill the DP table
19        for (int i = 1; i < n; ++i) {
20            // Compute prefix sums based on the previous row
21            prefixSum[0] = dp[i - 1][0];
22            for (int j = 1; j <= maxNum; ++j) {
23                prefixSum[j] = (prefixSum[j - 1] + dp[i - 1][j]) % MOD;
24            }
25          
26            // Calculate the DP for current row
27            for (int j = 0; j <= nums[i]; ++j) {
28                int k = Math.min(j, j + nums[i - 1] - nums[i]);
29                if (k >= 0) {
30                    dp[i][j] = prefixSum[k];
31                }
32            }
33        }
34      
35        // Calculate the final answer by summing up the last row of the DP table
36        int result = 0;
37        for (int j = 0; j <= nums[n - 1]; ++j) {
38            result = (result + dp[n - 1][j]) % MOD;
39        }
40        return result;
41    }
42}
43
1class Solution {
2public:
3    int countOfPairs(vector<int>& nums) {
4        const int mod = 1e9 + 7;  // Define the modulus value for result to prevent overflow
5        int n = nums.size();  // Calculate the size of the input vector 'nums'
6        int maxNum = *max_element(nums.begin(), nums.end());  // Find the maximum element in 'nums'
7      
8        // Create a 2D vector 'f' for dynamic programming, initialized with zeros
9        vector<vector<int>> f(n, vector<int>(maxNum + 1, 0));
10      
11        // Initialize the first row with 1 up to nums[0] since the first number can form pairs with itself
12        for (int j = 0; j <= nums[0]; ++j) {
13            f[0][j] = 1;
14        }
15      
16        // Create a vector 'g' to hold cumulative sums of the previous row for optimized calculations
17        vector<int> g(maxNum + 1, 0);
18      
19        // Fill the DP table using previously computed results
20        for (int i = 1; i < n; ++i) {
21            g[0] = f[i - 1][0];  // Initialize the first value of g with the previous row's first element
22
23            // Fill 'g' with cumulative sum of the previous row, modulated
24            for (int j = 1; j <= maxNum; ++j) {
25                g[j] = (g[j - 1] + f[i - 1][j]) % mod;
26            }
27
28            // Calculate the DP results for the current row
29            for (int j = 0; j <= nums[i]; ++j) {
30                int k = min(j, j + nums[i - 1] - nums[i]);  // Determine the farthest index in the previous row to consider
31
32                if (k >= 0) {
33                    f[i][j] = g[k];  // Assign the cumulative sum up to 'k' to the current position
34                }
35            }
36        }
37
38        int result = 0;  // Initialize the result to accumulate the final number of pairs
39
40        // Sum all possible pair counts from the last DP row to get the final answer
41        for (int j = 0; j <= nums[n - 1]; ++j) {
42            result = (result + f[n - 1][j]) % mod;
43        }
44      
45        return result;  // Return the total count of valid pairs
46    }
47};
48
1function countOfPairs(nums: number[]): number {
2    const mod = 1e9 + 7; // Modulo value for large number computations to avoid overflow
3    const n = nums.length; // Length of the input array
4    const m = Math.max(...nums); // Maximum value in the input array
5  
6    // Initialize a 2D array `f` to hold the count of pairs
7    // `f[i][j]` represents the number of valid ways to achieve a sum 'j' using the first 'i' numbers
8    const f: number[][] = Array.from({ length: n }, () => Array(m + 1).fill(0));
9  
10    // Base case: with the first number, we can only achieve sums from 0 to nums[0]
11    for (let j = 0; j <= nums[0]; j++) {
12        f[0][j] = 1;
13    }
14
15    // Temporary array `g` to manipulate rolling sums efficiently for dynamic programming
16    const g: number[] = Array(m + 1).fill(0);
17  
18    // Iterate through each number from the second one to the last
19    for (let i = 1; i < n; i++) {
20        // Initialize the rolling sum array `g`
21        g[0] = f[i - 1][0];
22      
23        // Populate `g` with cumulative sums to facilitate quick access
24        for (let j = 1; j <= m; j++) {
25            g[j] = (g[j - 1] + f[i - 1][j]) % mod;
26        }
27      
28        // Update `f[i][j]` based on the previous results and the rules given
29        for (let j = 0; j <= nums[i]; j++) {
30            const k = Math.min(j, j + nums[i - 1] - nums[i]); // Calculate the valid boundary based on current and previous values
31            if (k >= 0) {
32                // If valid, then count the sums that can form `j` using the available previous results
33                f[i][j] = g[k];
34            }
35        }
36    }
37  
38    let ans = 0; // To store the final answer
39    // Sum up all counts for the last number in `nums` to get the total number of valid pairs
40    for (let j = 0; j <= nums[n - 1]; j++) {
41        ans = (ans + f[n - 1][j]) % mod;
42    }
43  
44    return ans; // Return the total count of pairs modulo `mod`
45}
46

Time and Space Complexity

The time complexity of the code is O(n * m), where n is the length of the array nums, and m is the maximum value in the array nums. The outer loop iterates n times, and for each element, work proportional to m is performed, specifically initializing the DP table and carrying out prefix sum operations.

The space complexity is also O(n * m) due to the creation of a 2D list f with dimensions [n][m + 1], used to store intermediate results for dynamic programming.

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

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

What's the relationship between a tree and a graph?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More