Find the Count of Monotonic Pairs II

1. Initialization: Set MOD = 10^9 + 7. Find max_val, the maximum value in nums. Initialize a DP array dp of size max_val + 1 to store the counts for the previous index i-1.
2. Base Case (i=0): For arr1[0], any value j from 0 to nums[0] is valid. So, initialize dp[j] = 1 for 0 <= j <= nums[0].
3. Iteration: Loop for i from 1 to n-1: a. Create a new_dp array of size max_val + 1 for the current index i. b. Loop for j from 0 to nums[i] (representing arr1[i]): i. Determine the valid range for arr1[i-1]. The value k = arr1[i-1] must be less than or equal to upper_k = min(nums[i-1], j, j + nums[i-1] - nums[i]). ii. Calculate new_dp[j] by summing dp[k] for all k from 0 to upper_k. c. Replace dp with new_dp for the next iteration.
4. Result: The total count is the sum of all values in the final dp array (for i=n-1), modulo MOD.

The core idea is to count the number of valid sequences for arr1 up to each index i, as the constraints on arr2 can be fully translated into constraints on arr1. Let dp[i][j] be the number of ways to choose arr1[0], arr1[1], ..., arr1[i] satisfying all monotonic conditions, with arr1[i] = j.

Base Case: For the first element i=0, arr1[0] can be any integer from 0 to nums[0]. Thus, dp[0][j] = 1 for 0 <= j <= nums[0].

Transition: To compute dp[i][j], we sum up dp[i-1][k] over all valid previous values k = arr1[i-1]. The conditions for k given arr1[i]=j are:

• 0 <= k <= nums[i-1]
• k <= j (for arr1 to be non-decreasing)
• nums[i-1] - k >= nums[i] - j (for arr2 to be non-increasing), which simplifies to k <= j + nums[i-1] - nums[i].

This leads to the transition: dp[i][j] = sum(dp[i-1][k]) for all k from 0 to min(nums[i-1], j, j + nums[i-1] - nums[i]). This summation is performed in a loop, making the transition slow. For space optimization, we only need to store the DP states for the previous and current index, so we can use two arrays instead of a full 2D table.

1class Solution {2    public int countMonotonicPairs(int[] nums) {3        int n = nums.length;4        int MOD = 1_000_000_007;5 6        int maxVal = 0;7        for (int num : nums) {8            maxVal = Math.max(maxVal, num);9        }10 11        long[] dp = new long[maxVal + 1];12 13        // Base case: i = 014        for (int j = 0; j <= nums[0]; j++) {15            dp[j] = 1;16        }17 18        // Iterate from i = 1 to n-119        for (int i = 1; i < n; i++) {20            long[] newDp = new long[maxVal + 1];21            for (int j = 0; j <= nums[i]; j++) {22                long sum = 0;23                int upperK = Math.min(j, j + nums[i - 1] - nums[i]);24                upperK = Math.min(upperK, nums[i - 1]);25                26                for (int k = 0; k <= upperK; k++) {27                    sum = (sum + dp[k]) % MOD;28                }29                newDp[j] = sum;30            }31            dp = newDp;32        }33 34        long totalCount = 0;35        for (int j = 0; j <= maxVal; j++) {36            totalCount = (totalCount + dp[j]) % MOD;37        }38 39        return (int) totalCount;40    }41}

1. Initialization: Set MOD = 10^9 + 7. Find max_val, the maximum value in nums. Initialize a DP array dp of size max_val + 1.
2. Base Case (i=0): For arr1[0], any value j from 0 to nums[0] is valid. So, initialize dp[j] = 1 for 0 <= j <= nums[0].
3. Iteration: Loop for i from 1 to n-1: a. Create a prefix_sum array from the current dp array. prefix_sum[k] will store the sum of dp[0...k]. b. Create a new_dp array for the current index i. c. Loop for j from 0 to nums[i] (representing arr1[i]): i. Determine the upper bound upper_k for arr1[i-1]'s value. ii. Set new_dp[j] = prefix_sum[upper_k]. This is an O(1) lookup. d. Replace dp with new_dp for the next iteration.
4. Result: The total count is the sum of all values in the final dp array, modulo MOD.

This method uses the same DP state definition as the naive approach but optimizes the calculation. The transition dp[i][j] = sum_{k=0}^{upper_k} dp[i-1][k] involves a sum over a contiguous range, which is a classic pattern for prefix sum optimization.

Instead of re-calculating this sum for every j, we first compute a prefix_sum array for the dp[i-1] state. Let prefix_sum[x] = sum_{k=0}^{x} dp[i-1][k]. This array can be computed for all x in O(max_val) time.

With the prefix_sum array available, the transition for dp[i][j] becomes a simple O(1) lookup: dp[i][j] = prefix_sum[upper_k], where upper_k is the same upper bound calculated in the naive approach. This reduces the complexity of the inner part of the main loop, leading to a much faster overall algorithm that fits within the time limits.

1class Solution {2    public int countMonotonicPairs(int[] nums) {3        int n = nums.length;4        int MOD = 1_000_000_007;5 6        int maxVal = 0;7        for (int num : nums) {8            maxVal = Math.max(maxVal, num);9        }10 11        long[] dp = new long[maxVal + 1];12 13        // Base case: i = 014        for (int j = 0; j <= nums[0]; j++) {15            dp[j] = 1;16        }17 18        // Iterate from i = 1 to n-119        for (int i = 1; i < n; i++) {20            // Calculate prefix sums for the previous dp state21            long[] prefixSum = new long[maxVal + 1];22            prefixSum[0] = dp[0];23            for (int k = 1; k <= maxVal; k++) {24                prefixSum[k] = (prefixSum[k - 1] + dp[k]) % MOD;25            }26 27            long[] newDp = new long[maxVal + 1];28            for (int j = 0; j <= nums[i]; j++) {29                int upperK = Math.min(j, j + nums[i - 1] - nums[i]);30                upperK = Math.min(upperK, nums[i - 1]);31                32                if (upperK >= 0) {33                    newDp[j] = prefixSum[upperK];34                }35            }36            dp = newDp;37        }38 39        long totalCount = 0;40        for (int j = 0; j <= maxVal; j++) {41            totalCount = (totalCount + dp[j]) % MOD;42        }43 44        return (int) totalCount;45    }46}