What is the time complexity of Shortest Unsorted Continuous Subarray?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Shortest Unsorted Continuous Subarray?

This problem uses Array, Two Pointers, Stack, Greedy, Sorting, Monotonic Stack. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Shortest Unsorted Continuous Subarray?

Insight 1: The unsorted subarray is defined by a left boundary `start` and a right boundary `end`. Elements outside this subarray are already in the correct sorted order. Insight 2: We can identify the right boundary `end` by iterating from the left and keeping track of the maximum value seen so far. If we encounter an element smaller than the current maximum, it violates the non-decreasing order and indicates the end of the potential unsorted subarray.

Which companies ask LeetCode 581. Shortest Unsorted Continuous Subarray in interviews?

This problem is frequently asked at LiveRamp.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Shortest Unsorted Continuous Subarray - LeetCode 581 Solution

Shortest Unsorted Continuous Subarray - Complete Solution Guide

Shortest Unsorted Continuous Subarray is LeetCode problem 581, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an integer array nums , you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order. Return the shortest such subarray and output its length . Example 1: Input: nums = [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. Example 2: Input: nums = [1,2,3,4] Output: 0 Example 3: Input: nums = [1]

Detailed Explanation

The problem asks us to find the shortest continuous subarray within a given integer array `nums`, such that if we sort only that subarray in non-decreasing order, the entire array `nums` becomes sorted in non-decreasing order. The function should return the length of this shortest subarray. If the input array is already sorted, the function should return 0. The constraints limit the array size to a maximum of 10,000 elements, and each element's value ranges from -100,000 to 100,000.

Solution Approach

The solution employs a two-pass approach to find the `start` and `end` indices of the shortest unsorted subarray. The first pass iterates from left to right, maintaining a running maximum value. If an element is encountered that is less than the maximum value seen so far, the index of that element becomes a candidate for the right boundary (`end`). The second pass iterates from right to left, maintaining a running minimum value. If an element is encountered that is greater than the minimum value seen so far, the index of that element becomes a candidate for the left boundary (`start`). After both passes, the length of the unsorted subarray is calculated as `end - start + 1`. If no unsorted subarray is found (i.e., the array is already sorted), `end` will remain -1, and the function will return 0.

Step-by-Step Algorithm

Step 1: Initialize `start` to 0 and `end` to -1. Initialize `max_val` to `nums[0]` and `min_val` to `nums[n-1]`.
Step 2: Iterate from `i = 1` to `n-1`. In each iteration, if `nums[i] < max_val`, update `end` to `i`. Update `max_val` to `max(max_val, nums[i])`.
Step 3: If `end` is still -1, it means the array is already sorted, so return 0.
Step 4: Iterate from `i = n-2` to `0`. In each iteration, if `nums[i] > min_val`, update `start` to `i`. Update `min_val` to `min(min_val, nums[i])`.
Step 5: Return `end - start + 1`.

Key Insights

Insight 1: The unsorted subarray is defined by a left boundary `start` and a right boundary `end`. Elements outside this subarray are already in the correct sorted order.
Insight 2: We can identify the right boundary `end` by iterating from the left and keeping track of the maximum value seen so far. If we encounter an element smaller than the current maximum, it violates the non-decreasing order and indicates the end of the potential unsorted subarray.
Insight 3: Similarly, we can identify the left boundary `start` by iterating from the right and keeping track of the minimum value seen so far. If we encounter an element larger than the current minimum, it violates the non-decreasing order and indicates the start of the potential unsorted subarray.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Stack, Greedy, Sorting, Monotonic Stack.

Companies

Asked at: LiveRamp.

Shortest Unsorted Continuous Subarray | LeetCode 581

Medium

Array Two Pointers Stack Greedy Sorting Monotonic Stack

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }

        // Find the right boundary of the unsorted subarray
        int end = -1;
        int max_val = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] < max_val) {
                end = i;
            }
            max_val = Math.max(max_val, nums[i]);
        }

        // If the array is already sorted
        if (end == -1) {
            return 0;
        }

        // Find the left boundary of the unsorted subarray
        int start = 0;
        int min_val = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > min_val) {
                start = i;
            }
            min_val = Math.min(min_val, nums[i]);
        }

        return end - start + 1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 581: Shortest Unsorted Continuous Subarray - Detailed explanation and solution approaches.

Topics

Array Two Pointers Stack Greedy Sorting Monotonic Stack

Companies

LiveRamp

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:581

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize `start` to 0 and `end` to -1. Initialize `max_val` to `nums[0]` and `min_val` to `nums[n-1]`.
2
Step 2: Iterate from `i = 1` to `n-1`. In each iteration, if `nums[i] < max_val`, update `end` to `i`. Update `max_val` to `max(max_val, nums[i])`.
3
Step 3: If `end` is still -1, it means the array is already sorted, so return 0.
4
Step 4: Iterate from `i = n-2` to `0`. In each iteration, if `nums[i] > min_val`, update `start` to `i`. Update `min_val` to `min(min_val, nums[i])`.
5
Step 5: Return `end - start + 1`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The solution iterates through the array twice, once from left to right and once from right to left. Each iteration takes O(n) time, resulting in a total time complexity of O(n). The solution uses a constant amount of extra space for variables like `start`, `end`, `max_val`, and `min_val`, regardless of the input size. Therefore, the space complexity is O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Sorting

Create a sorted copy of the array and compare it with the original array to find the `start` and `end` indices where they differ.

Time: O(n log n)Space: O(n)

Trade-offs: This approach is simpler to understand but has a higher time complexity due to the sorting step. It uses extra space to store the sorted copy of the array. It might be preferred for smaller input sizes or when readability is more important than performance.

Using Stack

Use a stack to find the left and right boundaries of the unsorted subarray. Iterate from left to right, and when you encounter an element smaller than the stack's top, pop elements until the stack is empty or the top is smaller than the current element. The smallest index popped becomes a candidate for the left boundary. Do the same from right to left to find the right boundary.

Time: O(n)Space: O(n)

Trade-offs: Using Stack has the same time complexity O(n) as the main solution. But it uses O(n) space complexity since it needs a stack to store element. This is not the optimal solution for this problem.

✨

Key Insights

1Insight 1: The unsorted subarray is defined by a left boundary `start` and a right boundary `end`. Elements outside this subarray are already in the correct sorted order.
2Insight 2: We can identify the right boundary `end` by iterating from the left and keeping track of the maximum value seen so far. If we encounter an element smaller than the current maximum, it violates the non-decreasing order and indicates the end of the potential unsorted subarray.
3Insight 3: Similarly, we can identify the left boundary `start` by iterating from the right and keeping track of the minimum value seen so far. If we encounter an element larger than the current minimum, it violates the non-decreasing order and indicates the start of the potential unsorted subarray.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Greedy Algorithm

Making the best choice at each step without looking ahead.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty array or array with a single element. The solution correctly handles these cases by returning 0 at the beginning of the function (n < 2).
Edge case 2: Already sorted array. The solution correctly handles this case because the `end` variable will remain -1 after the first loop. The function will then return 0.
Edge case 3: Array sorted in descending order. The algorithm will correctly identify the entire array as the unsorted subarray, returning `n`.
Edge case 4: Array with duplicate elements. The algorithm still works correctly with duplicate elements, as it finds the shortest continuous subarray that, when sorted, will make the whole array sorted.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly calculating the length of the unsorted subarray. Remember to add 1 to the difference between `end` and `start`: `end - start + 1`.

✗Common mistake 2: Not handling the case where the array is already sorted. Make sure to check if `end` remains -1 after the first loop and return 0 in that case.

✗Common mistake 3: Not updating max_val and min_val correctly. Be sure to use max(max_val, nums[i]) and min(min_val, nums[i]) to ensure the running maximum and minimum are properly maintained.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data validation. Identifying a range of invalid data points in a sensor reading stream that needs recalibration or smoothing.

🏦Real-world scenario 2: Software version control. Detecting the minimum set of files that need to be reverted to correct a code regression caused by a faulty commit. By comparing the current state of files with a known good state, the algorithm can identify the range of modified or corrupted files.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 12, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Shortest Unsorted Continuous Subarray"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?