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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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:

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.
Output one valid optimal pair (L,R) with 0 ≤ L ≤ R < n. If multiple optimal answers exist, prefer the lexicographically smallest (L,R).
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.

Remove shortest subarray to sort array

Overview

Comments (0)