0 like 0 dislike
1,075 views
| 1,075 views

0 like 0 dislike

Images of ques

by Expert (46,090 points)
0 like 0 dislike

Count O(max(N,M))

We can count the number of valid subarrays ending in each index `i`.
Since the array is already sorted and all elements are unique in `[1, N]` ,
we only have to find the largest index `j` that is smaller that `i` that are either poisonous or allergic to each other (hope I understand the question correctly),
then, for that index `i`, we will update `j` to `max(j, jump[i])`
The answer will be the sum of all valid subarrays that end at each index `i`.

`Time O(max(N, M))`
`Space O(N)`

``````    private static long solve(int N, int[] P, int[] A){ // Java
int[] jump = new int[N+1];
for (int i = 0; i < P.length; i++){
for (int[] a : new int[][]{{A[i], P[i]}, {P[i], A[i]}}){
if (a[0] < a[1] && a[0] > jump[a[1]]){
jump[a[1]] = a[0]; // log the largest index less than it that are incompatible.
}
}
}
long ans = 0;
for (int i = 0, j = 0; i <= N; i++){
j = Math.max(jump[i], j);
ans += i - j;
}
return ans;
}``````
by Expert (46,090 points)