FastPrep
Problem · Array

Subarray Removal

● HardThe D. E. Shaw GroupOA

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.

Examples
01 · Example 1
arr = [1, 2, 1, 2]
return = 7
Example 1 illustration

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

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

02 · Example 2
arr = [3, 1, 2]
return = 3

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

03 · Example 3
arr = [1, 2, 2, 6, 1, 3]
return = 10

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

Constraints
  • 1 ≤ n ≤ 2×10^5
  • 1 ≤ arr[i] ≤ 10^9
More The D. E. Shaw Group problems
drafts saved locally
public long getNumSubarrays(int[] arr) {
  // write your code here
}
arr[1, 2, 1, 2]
expected7
sign in to submit