[Binary Search]Reverse Sublists to Convert to Target

#100daysofcode #programming #java #algorithms

https://binarysearch.com/problems/Reverse-Sublists-to-Convert-to-Target/solutions/6985776

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

Intuition

you can reverse as many times as you want
so you just need compare weather the numbers are same in these arrays

Implementation

*1. sorted array*

public boolean solve(int[] nums, int[] target) {
    if (nums.length != target.length) {
        return false;
    }

    Arrays.sort(nums);
    Arrays.sort(target);

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != target[i]) {
            return false;
        }
    }
    return true;
}

2. HashMap

public boolean solve(int[] nums, int[] target) {
    if (nums.length != target.length) {
        return false;
    }

    HashMap<Integer, Integer> map = new HashMap<>();

    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    for (int num : target) {
        int count = map.getOrDefault(num, 0);
        if (count <= 0) {
            return false;
        } else {
            map.put(num, count - 1);
        }
    }
    for (int value : map.values()) {
        if (value > 0) {
            return false;
        }
    }
    return true;
}