Find shortest subarray to restore order
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an integer array, find the shortest contiguous segment which, if sorted in ascending order, makes the entire array non-decreasing. Return the length of this segment. Discuss approaches from brute force to O(n log n) and an O(n) two-pointer/scan solution, and cover edge cases such as already-sorted arrays, duplicates, and strictly decreasing arrays.
Quick Answer: This question evaluates array manipulation and algorithmic problem-solving skills, focusing on understanding how local subarray sorting affects global order, edge-case reasoning (already-sorted arrays, duplicates, strictly decreasing sequences), and complexity analysis within the Coding & Algorithms domain.
Given an integer array `nums`, find the shortest contiguous subarray such that, if this subarray is sorted in ascending order, the whole array becomes non-decreasing. Return the length of this subarray. If the array is already non-decreasing, return 0.
The optimal O(n) approach uses two scans: scanning left-to-right while tracking the running maximum identifies the rightmost index that is out of place (any element smaller than a value seen earlier must be inside the window). Scanning right-to-left while tracking the running minimum identifies the leftmost out-of-place index (any element larger than a value seen later). The answer is the span between these two boundaries.
Example: for `[2, 6, 4, 8, 10, 9, 15]`, sorting the subarray `[6, 4, 8, 10, 9]` (indices 1..5) makes the array non-decreasing, so the answer is 5.
Constraints
- 1 <= nums.length <= 10^4 (function also handles the empty array)
- -10^5 <= nums[i] <= 10^5
- The array may contain duplicates.
Examples
Input: ([2, 6, 4, 8, 10, 9, 15],)
Expected Output: 5
Explanation: Sorting the subarray [6, 4, 8, 10, 9] (indices 1..5) makes the array non-decreasing; length 5.
Input: ([1, 2, 3, 4],)
Expected Output: 0
Explanation: Already non-decreasing, so no subarray needs sorting.
Hints
- An element belongs in the unsorted window if it is smaller than some element to its left, or larger than some element to its right.
- Scan left-to-right tracking the running maximum to find the rightmost index that is out of order; scan right-to-left tracking the running minimum to find the leftmost.
- If no element is ever out of order during the left-to-right scan, the array is already sorted and the answer is 0.