Teaching Kids Programming – Sort List by Reversing Once

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers nums. Given that you can first reverse one sublist in nums, return whether you can make the resulting list be arranged in ascending order.

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 3, 3, 7, 6, 9]
Output
True
Explanation
If we reverse the sublist [7, 6], then we can sort the list in ascending order: [1, 3, 3, 6, 7, 9].

Example 2
Input
nums = [1, 3, 9, 8, 2]
Output
False
Explanation
There’s no way to reverse any sublist to sort nums in ascending order.

Example 3
Input
nums = [1, 2, 3, 4]
Output
True
Explanation
This list is already sorted in ascending order so we can reverse any sublist of length 1. For example, reverse [2] to get the same [1, 2, 3, 4].

Sort List by Reversing Once

We can sort the array so that we know the Target array that we need to transform by reversing a sublist once. Then, we can find the left-most and right-most index using two pointers such that the values differ between original and sorted array. Then we just need to reverse the sublist starting the left-most and ending at right-most index to see if the corresponding reversed sublist equals to the sorted version.

1
2
3
4
5
6
7
8
9

class Solution:
    def solve(self, nums):
        arr = sorted(nums)
        i, j = 0, len(arr) - 1
        while i < j and nums[i] == arr[i]:
            i += 1
        while i < j and nums[j] == arr[j]:
            j -= 1
        return arr[i:j+1]==list(reversed(nums[i:j+1]))

class Solution:
    def solve(self, nums):
        arr = sorted(nums)
        i, j = 0, len(arr) - 1
        while i < j and nums[i] == arr[i]:
            i += 1
        while i < j and nums[j] == arr[j]:
            j -= 1
        return arr[i:j+1]==list(reversed(nums[i:j+1]))

The time complexity is O(NLogN) due to sorting and the space complexity is O(N) as we need to allocate an additonal array for storing the sorted array.

Similar problem: Teaching Kids Programming – Reverse Sublists to Convert to Target

–EOF (The Ultimate Computing & Technology Blog) —