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.