[LeetCode] Find the Count of Monotonic Pairs I

3250. Find the Count of Monotonic Pairs I

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 all 0 <= i <= n - 1.

Return the count of monotonic pairs.

Since the answer may be very large, return it modulo 109 + 7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
int countOfPairs(vector<int>& nums) {
long long mod = 1e9 + 7, n = nums.size();
vector<long long> dp(1001);
for(int i = 0; i <= nums[0]; i++) dp[i] = 1;
for(int i = 1; i < n; i++) {
vector<long long> dpp(1001);
long long pre = 0;
queue<pair<int,int>> q;
for(int j = 0; j <= nums[i]; j++) {
int k = nums[i] - j, pk = nums[i-1] - j;
q.push({pk,j});
while(q.size() and q.front().first >= k) {
auto [_,pj] = q.front(); q.pop();
pre = (pre + dp[pj]) % mod;
}
dpp[j] = pre;
}
swap(dp,dpp);
}
long long res = 0;
for(int i = 0; i <= 1000; i++) res = (res + dp[i]) % mod;
return res;
}
};

Author: Song Hayoung
Link: https://songhayoung.github.io/2024/08/11/PS/LeetCode/find-the-count-of-monotonic-pairs-i/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.