The O(n) Club: Shortest Unsorted Subarray — Only Sort What’s Broken

The O(n) Club: Shortest Unsorted Subarray — Only Sort What’s Broken

⚡ TL;DR

Given an array of integers, find the length of the shortest continuous section which—if sorted—would make the whole thing sorted. Don’t overthink it or drag in O(n log n) sorting: scan from both ends with max/min sentinels and polish it off in O(n) time, O(1) space. Java makes it look breezy:

// Java (stop the sort-copy madness)
public int findUnsortedSubarray(int[] nums) {
    int n = nums.length, left = -1, right = -1;
    int max = nums[0], min = nums[n - 1];
    for (int i = 0; i < n; i++) {
        if (nums[i] < max) right = i; else max = nums[i];
        if (nums[n - 1 - i] > min) left = n - 1 - i; else min = nums[n - 1 - i];
    }
    return (right == -1) ? 0 : right - left + 1;
}

🧠 How Devs Usually Mess This Up

Ah, the classics:

• Subarray ≠ Subset: Only continuous chunks count. If you could fix scrambled eggs by picking out random yolk bits, sure. Sadly, you can’t.
• Copy then Sort Everything: Copying, sorting, and comparing every element works… like demolishing your house to fix a squeaky door.
• Missing the ‘Already Sorted’ Case: If it’s sorted, return 0. Don’t invent problems that don’t exist—engineers have enough of that already.
• Dupes Derailing: Duplicates are fine; don’t let [2,2,2,2] break your beautiful logic.

🔍 What’s Actually Going On

Imagine a factory conveyor belt: widgets glide in perfect order—until someone gets clumsy and knocks over a continuous patch in the middle. Your job: find the minimal stretch to straighten so everything is sorted again. No need for a total recall—just find the zone where the illusion of order cracks, going from both ends.

Think of it as dragging a rolling max from the left and a rolling min from the right. “Hey! That one’s smaller than everything I’ve seen—broken!” Mark right/lower bounds accordingly. At the end: sort just that slice. Done before your coffee cools.

🛠️ PseudoCode

• left = -1, right = -1, max = nums[0], min = nums[n-1]
• For i = 0 to n-1:
  • If nums[i] < max, set right = i.
  • Else, max = nums[i].
  • If nums[n-1-i] > min, set left = n-1-i.
  • Else, min = nums[n-1-i].
• Return if right == -1 (already sorted), else right - left + 1.

It’s just a dual pass: one from each side, updating boundaries where the natural order is violated.

💻 The Code

public int findUnsortedSubarray(int[] nums) {
    int n = nums.length;
    int left = -1, right = -1;
    int max = nums[0], min = nums[n-1];
    for (int i = 0; i < n; i++) {
        if (nums[i] < max) right = i;
        else max = nums[i];
        if (nums[n - 1 - i] > min) left = n - 1 - i;
        else min = nums[n - 1 - i];
    }
    return (right == -1) ? 0 : right - left + 1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Totally Sorted? Arrays like [1, 2, 3] and [7, 7, 7] must return 0. Don’t fix what ain’t broke.
• Don’t Panic On Duplicates: Repeated numbers are normal; if your logic breaks on [1,3,3,2,2,4], rethink.
• Watch The Boundaries: Arrays with broken bits at the ends—don’t undercount your fix zone.
• O(n log n) Is For Mortals: Sorting and comparing works, but it ruins the interviewer’s hope that you know O(n) magic.
• Space(s) For Rent: No arrays, no lists, no sorting—just use a handful of variables. O(1) space, even your manager’s grandmother would approve.

🧠 Interviewer Brain-Tattoo

“Don’t repair the whole train because of a wonky carriage—fix just what rattles.” Happy sorting, minimal effort edition.