Shortest Unsorted Window

MediumTwo Pointers

Problem

A leaderboard scores should be in non-decreasing order, but a glitch shuffled one contiguous block. Find the shortest contiguous window that, if sorted on its own, makes the whole array non-decreasing.

Return the window's length (0 if the array is already sorted).

Example 1

Input:
scores = [1, 3, 6, 4, 5, 9]
Output:
3

Sorting [6, 4, 5] gives [1, 3, 4, 5, 6, 9].

Example 2

Input:
scores = [1, 2, 3]
Output:
0

Example 3

Input:
scores = [1, 3, 2, 2, 2]
Output:
4

The 3 must move past every 2, so the window is [3, 2, 2, 2].

Constraints

  • 1 ≤ scores.length ≤ 10^5
  • -10^5 ≤ scores[i] ≤ 10^5

Hint

Show the first hint

Compare with a sorted copy and the answer is the span between the first and last mismatch. Can you avoid the sort?

Walkthrough

How to approach it

01Clarify before coding

  • Is the target order non-decreasing? Yes, equal values may stay adjacent.
  • Return the window or its length? The length.
  • What if already sorted? Return 0.

02Brute force

Sort a copy and find the first and last positions where the copy differs from the original.

Cost: O(n log n) time and O(n) space for the copy.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.