Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
897 views
in Online Assessments by Expert (46,090 points) | 897 views

2 Answers

0 like 0 dislike
Best answer

image
image
image

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)