D. E. Shaw India | OA | Subarray Removal

Round 1

Questions: Given an array arr of n integers, find the number of its subarrays such that removing the subarray creates a non-empty array that is sorted in increasing order.
Note: A subarray is defined as any contiguous segment of the array.

Example
Suppose n = 4 and arr = [1, 2, 1, 2]

There are 7 subarrays that on removal produce a non-empty sorted array. Hence, the answer is 7.

Function Description
Complete the function getNumSubarrays in the editor below.
getNumSubarrays has the following parameter:
arr[n]: an array of integers

Returns
long int: The number of subarrays that on removal gives a non-empty sorted array

Constraints

• 1 ≤ n ≤ 2×10^5
• 1 ≤ arr[i] ≤ 10^9

Sample Case 0
Sample Input

STDIN       FUNCTION
-----       -----
3           →   arr[] size n = 3
3           →   arr = [3, 1, 2]
1
2

Sample Output

3

Explanation
The subarrays [3], [3, 1] and [1, 2] give a non-empty sorted array on removal.

Sample Case 1
Sample Input

STDIN       FUNCTION
-----       -----
6           →   arr[] size n = 6
1           →   arr = [1, 2, 2, 6, 1, 3]
2
2
6
1
3

Sample Output

10

Explanation
The subarrays [1, 2, 2, 6], [1, 2, 2, 6, 1], [2, 2, 6], [2, 2, 6, 1], [2, 2, 6, 1, 3], [2, 6, 1], [2, 6, 1, 3], [6, 1], [6, 1, 3] and [1, 3] give a non-empty sorted array on removal.

Working Solution

public long solve(List<Integer> A) {
    int n = A.size();

    boolean[] validRight = new boolean[n + 2];
    boolean[] validLeft = new boolean[n + 2];

    validLeft[0] = true;
    validRight[n + 1] = true;

    for (int i = 0; i < n; i++) {
        validLeft[i + 1] = validLeft[i] && (i == 0 || A.get(i - 1) <= A.get(i));
    }

    for (int i = n - 1; i >= 0; i--) {
        validRight[i + 1] = validRight[i + 2] && (i == n - 1 || A.get(i) <= A.get(i + 1));
    }

    long res = 0;

    // Two pointer approach
    for (int i = 1, j = 1; i <= n; i++) {
        while (j <= n && (!validRight[j] || j <= i || (i != 1 && A.get(i - 2) > A.get(j - 1)))) {
            j++;
        }

        if (validLeft[i - 1]) {
            res += (n + 2) - j;
        }
    }

    return res - 1; // -1 for the whole subarray.
}

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.

---