BinarySearch 0209 Shortest Sublist to Sort

Problem statement

https://binarysearch.com/problems/Shortest-Sublist-to-Sort/

Solution

Equal to Leetcode 0581. Shortest Unsorted Continuous Subarray.

Complexity

It is O(n log n) for time and O(n) for space here.

Code

class Solution:
    def solve(self, nums):
        nums2 = sorted(nums)
        n = len(nums)
        if nums2 == nums: return 0
        arr = [i for i in range(n) if nums[i] != nums2[i]]
        return max(arr) - min(arr) + 1