BinarySearch 0963 Sort List by Reversing Once

Problem statement

https://binarysearch.com/problems/Sort-List-by-Reversing-Once/

Solution

Similar to 581. Shortest Unsorted Continuous Subarray.

Complexity

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

Code

class Solution:
    def solve(self, nums):
        res = [i for (i, (a, b)) in enumerate(zip(nums, sorted(nums))) if a != b]
        if not res: return True
        a, b = res[0], res[-1]
        return nums[:a] + nums[a:b+1][::-1] + nums[b+1:] == sorted(nums)

Remark

There is also O(n) time complexity solution.