Given an array of integers A
with even length, return true
if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i]
for every 0 <= i < len(A) / 2
.
Example 1:
Input: [3,1,3,6]
Output: false
Example 2:
Input: [2,1,2,6]
Output: false
Example 3:
Input: [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].
Example 4:
Input: [1,2,4,16,8,4]
Output: false
Note:
0 <= A.length <= 30000
A.length
is even-100000 <= A[i] <= 100000
Idea 1. Kind of counting sort + hashMap
Time complexity: O(n + m) where m = max(A), n = A.length
Space complexity: O(m)
class Solution {
public boolean canReorderDoubled(int[] A) {
int n = 20000;
int[] negatives = new int[n+1];
int[] positives = new int[n+1]; for(int a: A) {
if(a < 0) {
++negatives[-a];
}
else {
++positives[a];
}
} for(int i = 0; i <= n; ++i) {
if(negatives[i] != 0) {
if(negatives[2*i] < negatives[i]) {
return false;
}
else {
negatives[2*i] -= negatives[i];
}
} if(positives[i] != 0) {
if(positives[2*i] < positives[i]) {
return false;
}
else {
positives[2*i] -= positives[i];
}
}
} return true;
}
}
Idea 1.a TreeMap + absoluate value as comparator, no need to deal with /2 for negative values
Time complexity: O(nlogn)
Space complexity: O(n)
class Solution {
public boolean canReorderDoubled(int[] A) {
Comparator<Integer> comparator = (Integer a, Integer b) -> {
int absEqual = Integer.compare(Math.abs(a), Math.abs(b));
if(absEqual == 0 && a != b) {
return Integer.compare(a, b);
}
return absEqual;
}; Map<Integer, Integer> count = new TreeMap<>(comparator); for(int a : A) {
count.put(a, count.getOrDefault(a, 0) + 1);
} for(int key: count.keySet()) {
int want = count.getOrDefault(2*key, 0);
if(count.get(key) > want) {
return false;
}
else if(count.containsKey(2*key)) {
count.put(2*key, want - count.get(key));
}
} return true;
}
}
Idea1.c normal treeMap with both positive + negatives
class Solution {
public boolean canReorderDoubled(int[] A) {
Map<Integer, Integer> count = new TreeMap<>(); for(int a : A) {
count.put(a, count.getOrDefault(a, 0) + 1);
} for(int key: count.keySet()) {
if(count.get(key) == 0) {
continue;
} int next = key < 0? key/2 : key*2;
int want = count.getOrDefault(next, 0);
if(count.get(key) > want) {
return false;
} count.put(next, want - count.get(key)); } return true;
}
}