Crack the Backend

Problem Statement

You are given an integer array nums. Find the shortest contiguous subarray such that if you sort this subarray (in ascending order), then the entire array becomes sorted in ascending order. Return the length of that subarray. If the array is already sorted, return 0.

Key Observations

Sort and compare: Copy nums and sort the copy. The subarray we need is from the first index where nums[i] != sorted[i] to the last such index. Length = right - left + 1 (or 0 if no mismatch).
Two-pass without sort: From left, find the rightmost index where the prefix is not non-decreasing (max so far > current). From right, find the leftmost index where the suffix is not non-decreasing (min so far < current). The unsorted segment is between these two.

Approach

High-level: sorted = copy and sort nums. left = first i with nums[i]!=sorted[i], right = last such i. Return right - left + 1 if any mismatch else 0.

Steps: int[] sorted = nums.clone(); Arrays.sort(sorted); int left = -1, right = -1; for (int i=0; i<n; i++) if (nums[i]!=sorted[i]) { if (left==-1) left=i; right=i; } return left==-1 ? 0 : right-left+1.

Implementation

Java

public int findUnsortedSubarray(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int left = -1, right = -1;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != sorted[i]) { if (left == -1) left = i; right = i; }
    }

    return left == -1 ? 0 : right - left + 1;
}

Test Cases

Example 1

Input

nums = [2,6,4,8,10,9,15]

Expected

5

Explanation

Sort [6,4,8,10,9]; length 5.

Complexity Analysis

Time: O(n).
Space: O(n) for stack.

Follow-ups

Previous smaller; range queries.