3250. Find the Count of Monotonic Pairs I
Problem Statement
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 all0 <= i <= n - 1
.
Return the count of monotonic pairs.
Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: nums = [2,3,2]
Output: 4
Explanation:
The good pairs are:
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])
Example 2:
Input: nums = [5,5,5,5]
Output: 126
Constraints:
1 <= n == nums.length <= 2000
1 <= nums[i] <= 50
Intuition
At each index
Keep track of Prev_of array A and B
And select the numbers accordingly
Since, Prev_a <= NExt num
For loop should start from NExt_num to nums[index]
To take all positbilites
Now,
At initial stages,
Prev A = 0, Prev B = 50
Take max and min,
So initial will not affect
Links
https://leetcode.com/problems/find-the-count-of-monotonic-pairs-i/
Video Links
https://www.youtube.com/watch?v=W9Job3hNmvA
Approach 1:
#define MOD 1000000007
class Solution {
public:
int dp[2002][52][52];
int find_ans(int index, vector<int>& nums, int a_prev, int b_prev){
if(index == nums.size()){
return 1;
}
if(dp[index][a_prev][b_prev] != -1)
return dp[index][a_prev][b_prev];
int ans = 0;
for(int i=a_prev; i<=nums[index]; i++){
int x = i, y = nums[index] - i;
if(a_prev <= x and b_prev>=y)
ans = ((ans%MOD) + (find_ans(index+1, nums, x, y)%MOD)%MOD);
}
return dp[index][a_prev][b_prev] = ans;
}
int countOfPairs(vector<int>& nums) {
memset(dp, -1, sizeof(dp));
return find_ans(0, nums, 0, 50);
}
};
Approach 2:
Approach 3:
Approach 4:
Similar Problems
Last updated