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,000wherenis the length ofnums -
0 ≤ m ≤ 100,000wheremis the length oftarget
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;
}
Time Complexity
O(n) for hashmap, O(nlogn) for sorted array
Space Complexity
O(n) for hashmap, O(1) for sorted array
Top comments (0)