Remove shortest subarray to sort array
Company: Apple
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
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
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.
Input: ([1, 2, 3, 10, 4, 2, 3, 5],)
Expected Output: 3
Explanation: Removing [10, 4, 2] leaves [1, 2, 3, 3, 5], which is non-decreasing.
Input: ([1, 2, 3, 3, 10, 0, 7, 8, 9],)
Expected Output: 2
Explanation: Removing [10, 0] leaves [1, 2, 3, 3, 7, 8, 9], which is non-decreasing.
Input: ([1, 2, 2, 2, 1, 2, 2],)
Expected Output: 1
Explanation: Removing the single element 1 at index 4 makes the array [1, 2, 2, 2, 2, 2].
Input: ([],)
Expected Output: 0
Explanation: An empty array is already non-decreasing.
Solution
def solution(nums):
n = len(nums)
if n <= 1:
return 0
left = 0
while left + 1 < n and nums[left] <= nums[left + 1]:
left += 1
if left == n - 1:
return 0
right = n - 1
while right > 0 and nums[right - 1] <= nums[right]:
right -= 1
ans = min(n - left - 1, right)
i, j = 0, right
while i <= left and j < n:
if nums[i] <= nums[j]:
ans = min(ans, j - i - 1)
i += 1
else:
j += 1
return ansTime complexity: O(n). Space complexity: O(1).
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
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.
Input: ([1, 3, 2, 4],)
Expected Output: [1, 1]
Explanation: Removing [3] gives [1, 2, 4]. Removing [2] also works, but [1, 1] is lexicographically smaller than [2, 2].
Input: ([2, 1, 2],)
Expected Output: [0, 0]
Explanation: Removing the first element leaves [1, 2]. Removing the middle element also leaves a non-decreasing array [2, 2], but [0, 0] is lexicographically smaller.
Input: ([-3, -1, -2, 0],)
Expected Output: [1, 1]
Explanation: Removing -1 leaves [-3, -2, 0], which is non-decreasing. Removing -2 also works, but [1, 1] is lexicographically smaller than [2, 2].
Input: ([1, 2, 3, 0],)
Expected Output: [3, 3]
Explanation: Removing the last element leaves [1, 2, 3], which is non-decreasing, and length 1 is optimal.
Input: ([5, 4, 3, 2, 1],)
Expected Output: [0, 3]
Explanation: Any valid answer must remove 4 elements. Both [0, 3] and [1, 4] work, and [0, 3] is lexicographically smaller.
Input: ([],)
Expected Output: [-1, -1]
Explanation: An empty array is already non-decreasing.
Solution
def solution(nums):
n = len(nums)
if n <= 1:
return [-1, -1]
left = 0
while left + 1 < n and nums[left] <= nums[left + 1]:
left += 1
if left == n - 1:
return [-1, -1]
right = n - 1
while right - 1 >= 0 and nums[right - 1] <= nums[right]:
right -= 1
best = [0, right - 1]
best_len = right
j = right
for i in range(left + 1):
while j < n and nums[j] < nums[i]:
j += 1
if j == n:
cand = [i + 1, n - 1]
cand_len = n - i - 1
else:
cand = [i + 1, j - 1]
cand_len = j - i - 1
if cand_len < best_len or (cand_len == best_len and cand < best):
best = cand
best_len = cand_len
return bestTime complexity: O(n). Space complexity: O(1).
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
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.
Input: ([[5, 4], [], [3, 2, 1]],)
Expected Output: 4
Explanation: The full stream is strictly decreasing: [5, 4, 3, 2, 1]. Any non-decreasing remainder can contain at most one element, so the minimum removal length is 4.
Input: ([[1, 3, 5], [], [4, 6, 7]],)
Expected Output: 1
Explanation: The full stream is [1, 3, 5, 4, 6, 7]. Removing just [4] gives [1, 3, 5, 6, 7].
Input: ([[-3, -2, -2], [5], [1, 2]],)
Expected Output: 1
Explanation: The full stream is [-3, -2, -2, 5, 1, 2]. Removing [5] leaves [-3, -2, -2, 1, 2], which is non-decreasing.
Input: ([[], []],)
Expected Output: 0
Explanation: The full stream is empty, so nothing needs to be removed.
Solution
def solution(chunks):
import bisect
starts = [0]
total = 0
for chunk in chunks:
total += len(chunk)
starts.append(total)
n = total
if n <= 1:
return 0
def value_at(idx):
chunk_idx = bisect.bisect_right(starts, idx) - 1
return chunks[chunk_idx][idx - starts[chunk_idx]]
left = 0
while left + 1 < n and value_at(left) <= value_at(left + 1):
left += 1
if left == n - 1:
return 0
right = n - 1
while right > 0 and value_at(right - 1) <= value_at(right):
right -= 1
ans = min(n - left - 1, right)
i, j = 0, right
while i <= left and j < n:
if value_at(i) <= value_at(j):
ans = min(ans, j - i - 1)
i += 1
else:
j += 1
return ansTime complexity: O(n log k), where n is the total number of values and k is the number of chunks. Space complexity: O(k).
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
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.
Input: ([1, 2, 3, 4], [-1, -1])
Expected Output: 1
Explanation: The array is already non-decreasing, so removing nothing is valid and shortest.
Input: ([3, 2, 1], [0, 2])
Expected Output: 0
Explanation: Removing the whole array is valid, but removing any length-2 segment already leaves one element, which is non-decreasing.
Input: ([], [-1, -1])
Expected Output: 1
Explanation: The empty array is already non-decreasing, so removing nothing is shortest.
Solution
def solution(nums, removal):
if not isinstance(removal, (list, tuple)) or len(removal) != 2:
return 0
def min_removal_length(arr):
n = len(arr)
if n <= 1:
return 0
left = 0
while left + 1 < n and arr[left] <= arr[left + 1]:
left += 1
if left == n - 1:
return 0
right = n - 1
while right - 1 >= 0 and arr[right - 1] <= arr[right]:
right -= 1
ans = min(n - left - 1, right)
i, j = 0, right
while i <= left and j < n:
if arr[i] <= arr[j]:
ans = min(ans, j - i - 1)
i += 1
else:
j += 1
return ans
min_len = min_removal_length(nums)
L, R = removal
if L == -1 and R == -1:
return 1 if min_len == 0 else 0
n = len(nums)
if L < 0 or R < 0 or L > R or R >= n:
return 0
prev_set = False
prev = 0
for i, x in enumerate(nums):
if L <= i <= R:
continue
if prev_set and prev > x:
return 0
prev = x
prev_set = True
return 1 if (R - L + 1) == min_len else 0
Time complexity: O(n). Space complexity: O(1).
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.