We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Count of Monotonic Pairs II

Number: 3536

Difficulty: Hard

Paid? No

Companies: BNY Mellon

Problem Description

Given an array of positive integers nums of length n, count how many pairs of non-negative integer arrays (arr1, arr2) exist such that:

  • Both arr1 and arr2 have length n.
  • arr1 is monotonically non-decreasing.
  • arr2 is monotonically non-increasing.
  • For every index i, arr1[i] + arr2[i] equals nums[i].

Return the count of such monotonic pairs modulo 10^9 + 7.

Key Insights

  • Since arr1[i] can be chosen in the range [0, nums[i]] (with arr2[i] being automatically determined as nums[i] - arr1[i]), the problem becomes one of counting the valid assignments to arr1 such that:
    • arr1 is non-decreasing.
    • The derived arr2 is non-increasing; this is equivalent to requiring that for every index i, arr1[i+1] - arr1[i] is at least nums[i+1] - nums[i] (when nums[i+1] > nums[i]).
  • The conditions can be combined into a DP transition: for any index i and chosen value x = arr1[i], the next value arr1[i+1] (say y) must satisfy y ≥ max(x, x + gap) where gap = max(0, nums[i+1] - nums[i]). Also y must not exceed nums[i+1].
  • A dynamic programming solution can be used where the state is the current index and the chosen value for arr1 at that index. Using prefix sums in the transition can optimize the recurrence.

Space and Time Complexity

Time Complexity: O(n * M) where M is the maximum value in nums (at most 1000)
Space Complexity: O(M) per DP row (using rolling arrays for DP)

Solution

We use dynamic programming with the state dp[i][x] representing the number of ways to form a valid sequence for arr1 up to index i with arr1[i] = x. For the base case (i = 0), any x from 0 to nums[0] is valid. To move from index i to i+1, note that if we have chosen a value x at index i, then at index i+1 we must choose a value y such that:

  • y is at least x (to keep arr1 non-decreasing), and
  • y is at least x + gap where gap = max(0, nums[i+1] - nums[i]) (to ensure that arr2 is non-increasing). Thus, y must be at least (x + gap).
    Also y is at most nums[i+1].

By precalculating the prefix sums of the current dp row, we can quickly sum all valid contributions to dp[i+1][y] from states in dp[i] with x satisfying x ≤ y - gap (making sure not to go below 0 or above nums[i]). We iterate this process for each index and sum all ways for the final index.

Code Solutions

# Python solution with detailed comments
MOD = 10**9 + 7

def countMonotonicPairs(nums):
    n = len(nums)
    # dp will hold number of ways for current index with chosen value for arr1
    dp = [0] * (nums[0] + 1)
    # Base case: for index 0, any value from 0 to nums[0] is allowed.
    for x in range(nums[0] + 1):
        dp[x] = 1

    # Process indices 0 to n-2 to build dp for next index
    for i in range(n - 1):
        next_num = nums[i + 1]
        gap = max(0, nums[i + 1] - nums[i])
        # Build prefix sum for current dp. prefix[x] holds sum(dp[0..x]).
        prefix = [0] * (nums[i] + 1)
        running = 0
        for x in range(nums[i] + 1):
            running = (running + dp[x]) % MOD
            prefix[x] = running

        # Prepare new dp for index i+1
        new_dp = [0] * (next_num + 1)
        for y in range(next_num + 1):
            # We need y to be at least gap to have a valid x from previous index:
            # we want all previous x that satisfy x <= y - gap.
            if y < gap:
                new_dp[y] = 0
            else:
                # x can be at most both y - gap and nums[i],
                # note that if y-gap > nums[i] then we take nums[i] as the upper bound.
                upper = min(y - gap, nums[i])
                new_dp[y] = prefix[upper]  # Sum dp[0] to dp[upper]
        # Update dp row
        dp = new_dp
    # Answer is sum of ways in the final dp row.
    return sum(dp) % MOD

# Example usage:
print(countMonotonicPairs([2,3,2]))  # Expected output: 4
print(countMonotonicPairs([5,5,5,5]))  # Expected output: 126
← Back to All Questions