Question

Atlassian | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-19

Answer 1

Images of ques

Answer 2

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;
    }