Count the Number of Incremovable Subarrays II

Count the Number of Incremovable Subarrays II

What is this problem about?

The Count the Number of Incremovable Subarrays II interview question is the optimized version of the previous problem. Given a large array, you must find how many subarrays can be removed to leave a strictly increasing sequence. The challenge here is the constraints: $O(N^2)$ is too slow, so you need an $O(N)$ approach.

Why is this asked in interviews?

This "Hard" problem is popular at DE Shaw and Apple. It tests the two pointers interview pattern and the ability to identify prefix/suffix properties. It requires the insight that if you remove a middle section, the remaining part is a prefix concatenated with a suffix. Both the prefix and suffix must themselves be strictly increasing, and the last element of the prefix must be smaller than the first element of the suffix.

Algorithmic pattern used

The problem uses Two Pointers and Prefix/Suffix Analysis.

1. Find the longest strictly increasing prefix $[0, i]$.
2. Find the longest strictly increasing suffix $[j, n-1]$.
3. If the entire array is already increasing, the answer is $n(n+1)/2$.
4. Otherwise, use two pointers to find valid combinations of a prefix segment and a suffix segment.
5. For each valid prefix end $p \le i$, find the smallest suffix start $s \ge j$ such that nums[p] < nums[s]. Every suffix starting from $s$ up to $n$ (including removing the whole suffix) works.

Example explanation

nums = [1, 2, 3, 1, 5, 6]

1. Prefix: [1, 2, 3] (indices 0-2).
2. Suffix: [1, 5, 6] (indices 3-5).
3. If we pick prefix [1, 2] (idx 0-1):
   • We need suffix start s such that nums[s] > 2.
   • Suffix starts at 5 (idx 4) or 6 (idx 5) or no suffix.
   • This gives several valid "incremovable" subarrays.

Common mistakes candidates make

• Miscounting prefix-only/suffix-only: Forgetting that you can remove just a prefix or just a suffix.
• Pointer overlap: Incorrectly handling the case where the prefix and suffix overlap.
• Binary Search vs. Two Pointers: While binary search works for finding the suffix start, it results in $O(N \log N)$, whereas two pointers can achieve $O(N)$.

Interview preparation tip

When a problem involves removing a contiguous segment, focus on what remains: a prefix and a suffix. Many Hard-level array problems can be solved by precomputing properties of all possible prefixes and suffixes and then matching them up.