algoadvance

Given an integer array nums, 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

1. Example 1:
   • Input: nums = [2,6,4,8,10,9,15]
   • Output: 5
   • Explanation: You need to sort the subarray [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
2. Example 2:
   • Input: nums = [1,2,3,4]
   • Output: 0
   • Explanation: The array is already sorted.
3. Example 3:
   • Input: nums = [1]
   • Output: 0
   • Explanation: The array is already sorted.

Clarifying Questions

1. Can the input array contain negative numbers?
   • Yes, the array can contain negative numbers.
2. What is the minimum length of the input array?
   • The minimum length of the input array is 1.

Strategy

1. Sort and Compare Approach:
   • Create a sorted version of the array.
   • Compare the original array with the sorted array to determine the positions where they differ.
   • The first and last positions of difference will give the bounds of the subarray that needs sorting.
2. Two Pointers Approach:
   • Traverse the array to identify the start and end of the subarray where the order is incorrect.
   • Begin from the left to find the first element that is out of order.
   • Begin from the right to find the first element that is out of order.
   • Use these bounds to determine the shortest subarray length that needs to be sorted.

Code

Here is the implementation using the sorting and comparison approach:

def findUnsortedSubarray(nums):
    sorted_nums = sorted(nums)
    start, end = 0, len(nums) - 1
    
    while start < len(nums) and nums[start] == sorted_nums[start]:
        start += 1
    
    while end > start and nums[end] == sorted_nums[end]:
        end -= 1
    
    return end - start + 1 if end > start else 0

# Test cases
print(findUnsortedSubarray([2,6,4,8,10,9,15])) # Output: 5
print(findUnsortedSubarray([1,2,3,4]))         # Output: 0
print(findUnsortedSubarray([1]))               # Output: 0

Time Complexity

• Time Complexity: O(n log n), due to the sorting step.
• Space Complexity: O(n), due to the space needed to store the sorted array.

Alternatively, if we implement the two pointers approach, it will have O(n) time complexity:

def findUnsortedSubarray(nums):
    n = len(nums)
    start, end = 0, -1
    min_val, max_val = float('inf'), float('-inf')
    
    for i in range(n):
        if nums[i] < max_val:
            end = i
        else:
            max_val = nums[i]
            
    for i in range(n-1, -1, -1):
        if nums[i] > min_val:
            start = i
        else:
            min_val = nums[i]
            
    return end - start + 1 if end > start else 0

# Test cases
print(findUnsortedSubarray([2,6,4,8,10,9,15])) # Output: 5
print(findUnsortedSubarray([1,2,3,4]))         # Output: 0
print(findUnsortedSubarray([1]))               # Output: 0

• Time Complexity: O(n), due to the single pass required to determine the bounds.
• Space Complexity: O(1), as we are using a constant amount of extra space.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?