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 Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Find shortest subarray to restore order

Quick Overview

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.

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.

Input: ([1],)

Expected Output: 0

Explanation: A single element is trivially sorted.

Input: ([],)

Expected Output: 0

Explanation: An empty array is trivially sorted.

Input: ([2, 1],)

Expected Output: 2

Explanation: The whole array is out of order; sorting both elements is required.

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

Expected Output: 5

Explanation: Strictly decreasing array: the entire array must be sorted.

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

Expected Output: 4

Explanation: The 3 must move past the trailing 2s; window spans indices 1..4 -> length 4.

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

Expected Output: 0

Explanation: All equal, already non-decreasing.

Input: ([-1, -5, -3, 0, 2],)

Expected Output: 3

Explanation: Sorting [-1, -5, -3] (indices 0..2) fixes the array; length 3, handling negatives.

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

Expected Output: 4

Explanation: The trailing 2 is smaller than earlier 3s; window spans indices 2..5 -> length 4, handling duplicates.

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.

Quick Overview