How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Apple.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Apple during technical interviews.

Remove shortest subarray to sort array

Q: Remove shortest subarray to sort array

This question evaluates proficiency in array algorithms, algorithmic efficiency (linear time and constant-space reasoning), and handling edge cases related to non-decreasing order, within the Coding & Algorithms domain.

Company: Apple

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an integer array nums (length up to 2×10^5), return the shortest subarray [L,R] you can remove so that the remaining elements form a non‑decreasing array. If the array is already non‑decreasing, return [-1,-1]. Requirements: 1) Design an O(n) time, O(1) extra space algorithm and prove correctness. Hint: compute the longest non‑decreasing prefix and suffix, then use two pointers to bridge them. 2) Output one valid optimal pair (L,R) with 0 ≤ L ≤ R < n. If multiple optimal answers exist, prefer the lexicographically smallest (L,R). 3) Follow‑ups: (a) support streaming input with limited memory (describe data structures and trade‑offs), (b) support one‑pass verification that a given (L,R) is optimal, (c) extend to strictly increasing arrays and to arrays with up to k deletions.

Quick Answer: This question evaluates proficiency in array algorithms, algorithmic efficiency (linear time and constant-space reasoning), and handling edge cases related to non-decreasing order, within the Coding & Algorithms domain.

Part 1: Minimum length of a removable subarray

Given an integer array nums, remove exactly one contiguous subarray (possibly empty) so that the remaining elements, in their original order, form a non-decreasing array. Return the minimum possible length of the removed subarray. If nums is already non-decreasing, return 0. The intended solution should run in O(n) time and use O(1) extra space.

Constraints

0 <= len(nums) <= 2 * 10^5
-10^9 <= nums[i] <= 10^9

Examples

Input: ([1, 2, 3],)

Expected Output: 0

Explanation: The array is already non-decreasing, so removing an empty subarray is optimal.

Input: ([5, 4, 3, 2, 1],)

Expected Output: 4

Explanation: Any remaining non-decreasing array can contain at most one element, so the minimum removal length is 4.

Hints

Find the longest non-decreasing prefix and the longest non-decreasing suffix.
After that, use two pointers to see how cheaply you can connect a prefix element to a suffix element.

Part 2: Lexicographically smallest optimal removal pair

Given an integer array nums, remove one contiguous subarray [L, R] so that the remaining elements form a non-decreasing array. Return one valid optimal pair [L, R] with the smallest possible removed length. If multiple optimal pairs exist, return the lexicographically smallest one, meaning the smallest L, and if tied, the smallest R. If nums is already non-decreasing, return [-1, -1].

Constraints

1 <= len(nums) <= 2 * 10^5
-10^9 <= nums[i] <= 10^9

Examples

Input: ([1, 2, 2, 3],)

Expected Output: [-1, -1]

Explanation: The array is already non-decreasing, so no removal is necessary.

Input: ([1, 5, 6, 2, 3, 4],)

Expected Output: [1, 2]

Explanation: Removing nums[1..2] = [5, 6] leaves [1, 2, 3, 4], which is non-decreasing. No removal of length 1 works.

Hints

First compute the minimum removable length using the same prefix-suffix idea as in Part 1.
Once the optimal length is known, scan L from left to right; the first valid segment of that length is the lexicographically smallest answer.

Part 3: Shortest removal from a chunked stream

The full array is given as chunks, where concatenating all chunks in order forms the stream of numbers. Empty chunks may appear. Return the minimum length of a contiguous subarray of the full stream whose removal makes the remaining numbers non-decreasing. The goal is to avoid flattening the entire stream into a second full array: store only chunk-boundary metadata and solve the problem exactly.

Constraints

0 <= len(chunks) <= 2 * 10^5
0 <= sum(len(chunk) for chunk in chunks) <= 2 * 10^5
-10^9 <= value <= 10^9 for every streamed value

Examples

Input: ([[1, 2], [], [2, 3, 4]],)

Expected Output: 0

Explanation: The full stream is [1, 2, 2, 3, 4], which is already non-decreasing.

Input: ([[1, 2, 3], [10, 4, 2], [3, 5]],)

Expected Output: 3

Explanation: The full stream is [1, 2, 3, 10, 4, 2, 3, 5]. Removing [10, 4, 2] leaves [1, 2, 3, 3, 5], which is non-decreasing.

Hints

Store the starting global index of each non-empty chunk so you can map a global position back to its chunk.
Compared with fully flattening, chunk-boundary metadata saves memory but makes random access a bit slower.

Part 4: Array repair follow-up toolkit

Implement a follow-up toolkit for the removable-subarray problem. The function receives mode, nums, and extra. If mode = 'verify', then extra = [L, R] and you must return 1 if removing nums[L..R] is a shortest valid contiguous removal that makes the remaining array non-decreasing; also allow [-1, -1] to mean removing nothing. If mode = 'strict', ignore extra and return the minimum length of one contiguous subarray to remove so the remaining elements are strictly increasing. If mode = 'k', then extra = [k] and you must return 1 if nums can be made non-decreasing by deleting at most k individual elements anywhere, otherwise 0.

Constraints

0 <= len(nums) <= 2 * 10^5
mode is one of 'verify', 'strict', 'k'
For mode 'verify', extra has length 2 and may be [-1, -1]
For mode 'k', extra has length 1 and 0 <= k <= len(nums)
-10^9 <= nums[i] <= 10^9

Examples

Input: ([1, 2, 10, 3, 4], [2, 2])

Expected Output: 1

Explanation: Removing only 10 gives [1, 2, 3, 4], which is non-decreasing, and length 1 is optimal.

Input: ([1, 2, 10, 3, 4], [1, 3])

Expected Output: 0

Explanation: Removing [2, 10, 3] leaves [1, 4], which is valid, but length 3 is not shortest because length 1 already works.

Hints

For the strict variant, reuse the same prefix-suffix two-pointer idea but replace <= with < everywhere.
For the k-deletions variant, think about the longest non-decreasing subsequence: if its length is L, then n - L deletions are enough and also necessary.

Quick Overview

This question evaluates proficiency in array algorithms, algorithmic efficiency (linear time and constant-space reasoning), and handling edge cases related to non-decreasing order, within the Coding & Algorithms domain.