Practice/Meta/Leetcode 3250. Find the Count of Monotonic Pairs I

Leetcode 3250. Find the Count of Monotonic Pairs I

CodingOptional

Problem

Given an array nums of non-negative integers, determine how many ways you can decompose it into two sequences arr1 and arr2 such that:

• Both sequences have the same length as nums
• For every index i: arr1[i] + arr2[i] = nums[i]
• The sequence arr1 is non-decreasing (each element is greater than or equal to the previous)
• The sequence arr2 is non-increasing (each element is less than or equal to the previous)
• All values in both sequences are non-negative integers

Return the count of valid decomposition pairs modulo 10^9 + 7.

Requirements

1. Each element in nums must be split into two non-negative parts that sum to the original value
2. The first sequence must be non-decreasing throughout
3. The second sequence must be non-increasing throughout
4. Return the total count modulo 10^9 + 7

Constraints

• 1 ≤ nums.length ≤ 2000
• 0 ≤ nums[i] ≤ 50
• Time complexity should be reasonable for the given constraints

Examples

Example 1:

` Input: nums = [2, 3, 2] Output: 4 Explanation: Valid decompositions:

• arr1 = [0, 1, 1], arr2 = [2, 2, 1]
• arr1 = [1, 1, 1], arr2 = [1, 2, 1]
• arr1 = [2, 2, 2], arr2 = [0, 1, 0]
• arr1 = [1, 2, 2], arr2 = [1, 1, 0] `

Example 2:

Input: nums = [5] Output: 6 Explanation: With one element, splits can be: (0,5), (1,4), (2,3), (3,2), (4,1), (5,0) All satisfy the monotonicity constraints trivially.

Example 3:

Input: nums = [1, 2, 3] Output: 4 Explanation: The increasing sum values allow several valid decompositions where arr1 grows and arr2 shrinks appropriately.