Jobs

Interviews

Discussions

Shortest Unsorted Continuous Subarray

Medium

Shortest Unsorted Continuous Subarray

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected return value if the input array is already sorted?
Can the input array contain negative numbers, zeros, or floating-point numbers?
What is the maximum size of the input array?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
By 'sorted', do you mean non-decreasing order or strictly increasing order?

Brute Force Solution

Approach

The problem asks us to find the smallest section of a list that, if sorted, would make the whole list sorted. The brute force way is to simply check every possible section of the list.

Here's how the algorithm would work step-by-step:

Consider every possible starting point for the section.
For each starting point, consider every possible ending point for the section (including just the starting point itself).
For each section you've selected, imagine sorting only that section of the list.
Check if sorting that section would make the entire list sorted from start to finish.
If it does, remember the length of that section and the starting and ending points.
After checking every possible section, find the smallest section that would make the whole list sorted.
If no section works (meaning the list was already sorted), the answer is that the length of the unsorted section is zero.

Code Implementation

def find_unsorted_subarray_brute_force(numbers):
    list_length = len(numbers)
    shortest_unsorted_length = list_length
    start_index_result = -1
    end_index_result = -1

    for start_index in range(list_length):
        for end_index in range(start_index, list_length):
            
            # Create a copy to avoid modifying the original list
            temp_numbers = numbers[:]
            
            # Sort the subarray from start_index to end_index
            subarray_to_sort = temp_numbers[start_index:end_index+1]
            subarray_to_sort.sort()
            temp_numbers[start_index:end_index+1] = subarray_to_sort

            is_sorted = True
            for index in range(list_length - 1):
                if temp_numbers[index] > temp_numbers[index + 1]:
                    is_sorted = False
                    break

            if is_sorted:
                
                #Check if the current subarray is shorter than the existing one.
                current_length = end_index - start_index + 1
                if current_length < shortest_unsorted_length:
                    shortest_unsorted_length = current_length
                    start_index_result = start_index
                    end_index_result = end_index

    #If the entire array was already sorted.
    if start_index_result == -1:
        return 0
    else:
        return shortest_unsorted_length

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible subarrays. The outer loop iterates 'n' times to choose the start index. The inner loop iterates up to 'n' times to choose the end index. For each subarray, the algorithm sorts a portion of the array using another operation that takes O(n log n) or O(n^2) depending on the chosen sorting algorithm (but can be optimized to O(n) because we can just check if the selected subarray is sorted, and if not, the entire array is unsorted). Since the check for whether the entire array would be sorted involves iterating over all 'n' elements to verify sorted order, the overall time complexity is O(n * n * n). Alternatively, checking the sorting involves sorting a subarray using O(n log n) or O(n^2) within each iteration of the nested loops, leading to O(n^3 log n) or O(n^4). Because the plain English explanation indicates sorting *only* the section and then checking, we consider the verification as O(n). This nested iteration and subsequent verification of the sorted state results in approximately n * n * n operations, simplifying to O(n^3).

Space Complexity

O(1) – The described brute force solution iterates through all possible subarrays. However, it only needs to store a few variables: the starting and ending indices of the shortest unsorted subarray found so far, and potentially the length of that subarray. No auxiliary data structures that scale with the input size N (the length of the input list) are used. Therefore, the space complexity is constant.

Optimal Solution

Approach

The trick to finding the shortest unsorted section is to realize a sorted array has numbers increasing from left to right. Therefore, we aim to find the first instance where this order breaks from the left and the right, which marks the boundaries of our unsorted section.

Here's how the algorithm would work step-by-step:

First, go from left to right and find the first number that is bigger than a number that appears later in the sequence. This marks the potential start of the unsorted section.
Next, go from right to left and find the first number that is smaller than a number that appears earlier in the sequence. This marks the potential end of the unsorted section.
Find the smallest and largest numbers within the potential unsorted section we just identified.
Now, go from the beginning of the entire sequence to the start of our unsorted section and find the first number that's bigger than the smallest number within our unsorted section. If this is found, it's the actual start of our unsorted section. If it isn't, it's the previously found potential start.
Similarly, go from the end of the entire sequence to the end of our unsorted section and find the first number that's smaller than the largest number within our unsorted section. If this is found, it's the actual end of our unsorted section. If it isn't, it's the previously found potential end.
The span between the actual start and end numbers we found is the length of the shortest unsorted section.

Code Implementation

def shortest_unsorted_continuous_subarray(nums):
    array_length = len(nums)
    start_index = -1
    end_index = -1

    # Find the potential start of the unsorted subarray.
    for i in range(array_length - 1):
        if nums[i] > nums[i + 1]:
            start_index = i
            break

    # If the array is sorted, return 0.
    if start_index == -1:
        return 0

    # Find the potential end of the unsorted subarray.
    for i in range(array_length - 1, 0, -1):
        if nums[i] < nums[i - 1]:
            end_index = i
            break

    # Find the minimum and maximum values within the unsorted subarray.
    subarray_maximum = max(nums[start_index:end_index + 1])
    subarray_minimum = min(nums[start_index:end_index + 1])

    # Extend the unsorted subarray to the left if needed.
    for i in range(start_index + 1):
        if nums[i] > subarray_minimum:
            start_index = i
            break

    # Extend the unsorted subarray to the right if needed.
    for i in range(array_length - 1, end_index - 1, -1):
        if nums[i] < subarray_maximum:
            end_index = i
            break

    # Calculate the length of the unsorted subarray.
    return end_index - start_index + 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves several linear scans of the input array 'nums' of size 'n'. First, we scan from left to right and right to left to find the potential start and end of the unsorted subarray. Then, we find the minimum and maximum within that potential subarray, which is another scan bounded by 'n'. Finally, we scan from the beginning and end of the array to refine the start and end indices. Since each step takes O(n) time and these steps are performed sequentially, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm utilizes a few variables to store indices (potential start, potential end, actual start, actual end) and the minimum and maximum values within the potentially unsorted subarray. The number of these variables is constant and does not depend on the input array's size, N. Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately since no subarray needs sorting.
Already sorted array	The algorithm should identify this and return 0.
Array with only two elements, sorted or unsorted	Should correctly identify if a swap is needed and return 2 or 0 accordingly.
Array with all identical elements	Should correctly return 0 as no sorting is required.
Array sorted in descending order	Should return the full array length as the entire array needs sorting.
Array with a small unsorted section at the beginning	The algorithm should correctly identify the start and end of the unsorted subarray.
Array with a small unsorted section at the end	The algorithm should correctly identify the start and end of the unsorted subarray.
Array with duplicate values within the unsorted subarray	The algorithm should still correctly identify the boundaries of the minimal unsorted subarray containing these duplicates.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected return value if the input array is already sorted?
Can the input array contain negative numbers, zeros, or floating-point numbers?
What is the maximum size of the input array?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
By 'sorted', do you mean non-decreasing order or strictly increasing order?

Brute Force Solution

Approach

The problem asks us to find the smallest section of a list that, if sorted, would make the whole list sorted. The brute force way is to simply check every possible section of the list.

Here's how the algorithm would work step-by-step:

Consider every possible starting point for the section.
For each starting point, consider every possible ending point for the section (including just the starting point itself).
For each section you've selected, imagine sorting only that section of the list.
Check if sorting that section would make the entire list sorted from start to finish.
If it does, remember the length of that section and the starting and ending points.
After checking every possible section, find the smallest section that would make the whole list sorted.
If no section works (meaning the list was already sorted), the answer is that the length of the unsorted section is zero.

Code Implementation

def find_unsorted_subarray_brute_force(numbers):
    list_length = len(numbers)
    shortest_unsorted_length = list_length
    start_index_result = -1
    end_index_result = -1

    for start_index in range(list_length):
        for end_index in range(start_index, list_length):
            
            # Create a copy to avoid modifying the original list
            temp_numbers = numbers[:]
            
            # Sort the subarray from start_index to end_index
            subarray_to_sort = temp_numbers[start_index:end_index+1]
            subarray_to_sort.sort()
            temp_numbers[start_index:end_index+1] = subarray_to_sort

            is_sorted = True
            for index in range(list_length - 1):
                if temp_numbers[index] > temp_numbers[index + 1]:
                    is_sorted = False
                    break

            if is_sorted:
                
                #Check if the current subarray is shorter than the existing one.
                current_length = end_index - start_index + 1
                if current_length < shortest_unsorted_length:
                    shortest_unsorted_length = current_length
                    start_index_result = start_index
                    end_index_result = end_index

    #If the entire array was already sorted.
    if start_index_result == -1:
        return 0
    else:
        return shortest_unsorted_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, go from left to right and find the first number that is bigger than a number that appears later in the sequence. This marks the potential start of the unsorted section.
Next, go from right to left and find the first number that is smaller than a number that appears earlier in the sequence. This marks the potential end of the unsorted section.
Find the smallest and largest numbers within the potential unsorted section we just identified.
Now, go from the beginning of the entire sequence to the start of our unsorted section and find the first number that's bigger than the smallest number within our unsorted section. If this is found, it's the actual start of our unsorted section. If it isn't, it's the previously found potential start.
Similarly, go from the end of the entire sequence to the end of our unsorted section and find the first number that's smaller than the largest number within our unsorted section. If this is found, it's the actual end of our unsorted section. If it isn't, it's the previously found potential end.
The span between the actual start and end numbers we found is the length of the shortest unsorted section.

Code Implementation

def shortest_unsorted_continuous_subarray(nums):
    array_length = len(nums)
    start_index = -1
    end_index = -1

    # Find the potential start of the unsorted subarray.
    for i in range(array_length - 1):
        if nums[i] > nums[i + 1]:
            start_index = i
            break

    # If the array is sorted, return 0.
    if start_index == -1:
        return 0

    # Find the potential end of the unsorted subarray.
    for i in range(array_length - 1, 0, -1):
        if nums[i] < nums[i - 1]:
            end_index = i
            break

    # Find the minimum and maximum values within the unsorted subarray.
    subarray_maximum = max(nums[start_index:end_index + 1])
    subarray_minimum = min(nums[start_index:end_index + 1])

    # Extend the unsorted subarray to the left if needed.
    for i in range(start_index + 1):
        if nums[i] > subarray_minimum:
            start_index = i
            break

    # Extend the unsorted subarray to the right if needed.
    for i in range(array_length - 1, end_index - 1, -1):
        if nums[i] < subarray_maximum:
            end_index = i
            break

    # Calculate the length of the unsorted subarray.
    return end_index - start_index + 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately since no subarray needs sorting.
Already sorted array	The algorithm should identify this and return 0.
Array with only two elements, sorted or unsorted	Should correctly identify if a swap is needed and return 2 or 0 accordingly.
Array with all identical elements	Should correctly return 0 as no sorting is required.
Array sorted in descending order	Should return the full array length as the entire array needs sorting.
Array with a small unsorted section at the beginning	The algorithm should correctly identify the start and end of the unsorted subarray.
Array with a small unsorted section at the end	The algorithm should correctly identify the start and end of the unsorted subarray.
Array with duplicate values within the unsorted subarray	The algorithm should still correctly identify the boundaries of the minimal unsorted subarray containing these duplicates.