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 I

Number: 3535

Difficulty: Hard

Paid? No

Companies: Arcesium

Problem Description

Given an array of positive integers nums of length n, count the number of pairs of non-negative integer arrays (arr1, arr2) where both arrays have length n, arr1 is monotonically non-decreasing, arr2 is monotonically non-increasing, and for each index i, arr1[i] + arr2[i] equals nums[i]. Since the answer can be very large, return it modulo 10^9 + 7.

Key Insights

  • The relation arr1[i] + arr2[i] = nums[i] lets you write arr2[i] as nums[i] - arr1[i]. This reduces the problem to finding valid arr1 only.
  • Arr1 must be non-decreasing while arr2 being non-increasing translates (after substitution) to a constraint between consecutive values in arr1.
  • Specifically, for every consecutive pair of indices i and i+1, the inequality nums[i]-arr1[i] >= nums[i+1]-arr1[i+1] is equivalent to arr1[i+1] - arr1[i] >= nums[i+1] - nums[i].
  • A dynamic programming approach over indices and possible values of arr1[i] (which lies between 0 and nums[i]) can be employed.
  • The DP state dp[i][x] represents the number of valid ways to assign arr1[0..i] such that arr1[i] equals x.

Space and Time Complexity

Time Complexity: O(n * M^2) where M is the maximum possible value (at most 50)
Space Complexity: O(n * M)

Solution

We use a dynamic programming (DP) strategy. For every index i, iterate over all possible values x in the range 0 to nums[i] for arr1[i]. For the transition from index i to i+1, note that arr1 is non-decreasing so candidate y must satisfy y >= x, and from the monotonicity condition of arr2, we require:   nums[i] - x >= nums[i+1] - y  ⟹ y >= x + (nums[i+1] - nums[i]). Define the lower bound L = max(x, x + (nums[i+1] - nums[i])). Then for every candidate y from L to nums[i+1], update the DP state for the (i+1)th index. Finally, sum all valid dp[n-1][x] for x from 0 to nums[n-1] to obtain the answer.

Code Solutions

# Python solution
MOD = 10**9 + 7

def countMonotonicPairs(nums):
    n = len(nums)
    # dp[i][x] means number of ways for arr1[0..i] with arr1[i] == x.
    # For index 0, possible arr1[0] are in [0, nums[0]].
    dp = [[0] * (51) for _ in range(n)]
    for x in range(0, nums[0] + 1):
        dp[0][x] = 1

    # Process dp states for each index
    for i in range(0, n - 1):
        diff = nums[i+1] - nums[i]
        # For each possible arr1[i] value x
        # we want arr1[i+1] (denoted as y) to be in [max(x, x + diff), nums[i+1]]
        for x in range(0, nums[i] + 1):
            if dp[i][x] == 0:
                continue
            lowerBound = x if diff < 0 else x + diff  # equivalent to max(x, x + diff)
            for y in range(lowerBound, nums[i+1] + 1):
                dp[i+1][y] = (dp[i+1][y] + dp[i][x]) % MOD

    # Sum all valid ways for last index
    result = sum(dp[n-1][0:nums[n-1] + 1]) % MOD
    return result

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