algoadvance

Leetcode 581. Shortest Unsorted Continuous Subarray

Problem Statement

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order. Return the shortest such subarray and output its length.

Example:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Clarifying Questions

  1. Can the input array be empty or contain just one element?
    • If the array is empty or has one element, it doesn’t need sorting, so the length should be 0.
  2. Can all elements in the array be the same?
    • Yes, if all elements are the same, the array is already sorted, so the length should be 0.

Strategy

To find the shortest subarray that, when sorted, results in the entire array being sorted, we can follow these steps:

  1. Identify Bounds with Sorting:
    • Make a copy of the array and sort it.
    • Compare the original and sorted arrays to find the first and last indices where they differ.
  2. Two-Pointer Technique:
    • Use two pointers: one starting from the beginning and one from the end.
    • Move the first pointer forward until you find an element that is out of order.
    • Move the second pointer backward until you find an element that is out of order.
  3. The difference between these two pointers plus one gives the length of the subarray that needs sorting.

Code

import java.util.Arrays;

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] sortedNums = Arrays.copyOf(nums, n);
        Arrays.sort(sortedNums);
        
        int start = 0;
        while (start < n && nums[start] == sortedNums[start]) {
            start++;
        }
        
        int end = n - 1;
        while (end >= 0 && nums[end] == sortedNums[end]) {
            end--;
        }
        
        return (start < end) ? (end - start + 1) : 0;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 6, 4, 8, 10, 9, 15};
        System.out.println(sol.findUnsortedSubarray(nums)); // Output: 5
    }
}

Time Complexity

Thus, the overall time complexity is O(n log n) due to the sorting step.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI