Teaching Kids Programming – Reverse Sublists to Convert to Target

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two lists of integers nums, and target, consider an operation where you take some sublist in nums and reverse it. Return whether it’s possible to turn nums into target, given you can make any number of operations.

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums
0 ≤ m ≤ 100,000 where m is the length of target
Example 1
Input
nums = [1, 2, 3, 8, 9]
target = [3, 2, 1, 9, 8]
Output
True
Explanation
We can reverse [1, 2, 3] and [8, 9]

Example 2
Input
nums = [10, 2, 3, 8, 9]
target = [3, 2, 1, 9, 8]
Output
False

Hints:
Will Bubble help with an insight ?
You can swap any two numbers in array using above operation.

Reverse Sublists to Convert to Target

We can perform as many operations as possible – and thus we can swap an element to any desired position. So the problem becomes to check if two arrays are anagrams i.e. same after re-arrange order.

We can use Counter to check if both lists are equal. O(N) time and O(N) space.

1
2
3
4
5

class Solution:
    def reverseSubListsToTarget(self, nums, target):
        if len(nums) != len(target):
            return False
        return Counter(nums) == Counter(target)

class Solution:
    def reverseSubListsToTarget(self, nums, target):
        if len(nums) != len(target):
            return False
        return Counter(nums) == Counter(target)

Alternatively, we can sort both lists in O(NLogN) time – which has O(1) space.

1
2
3
4
5

class Solution:
    def reverseSubListsToTarget(self, nums, target):
        if len(nums) != len(target):
            return False
        return sorted(nums) == sorted(target)

class Solution:
    def reverseSubListsToTarget(self, nums, target):
        if len(nums) != len(target):
            return False
        return sorted(nums) == sorted(target)

–EOF (The Ultimate Computing & Technology Blog) —