How should I practice Subarray Removal?

Start by reading the full statement, solve the visible examples, then compare the pattern against related The D. E. Shaw Group online assessment problems in FastPrep.

Is Subarray Removal associated with The D. E. Shaw Group?

FastPrep tags this as a The D. E. Shaw Group online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Subarray Removal

Learn this problem

● Hard

The D. E. Shaw GroupOA

Problem statement

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.

Function

getNumSubarrays(arr: int[]) → long

Examples

Example 1

arr = [1, 2, 1, 2]return = 7

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.

Example 2

arr = [3, 1, 2]return = 3

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

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