Array of Doubled Pairs

LeetCode Q 954 - Array of Doubled Pairs

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

Solution

Solution 1 : Using Array

Code:

public boolean canReorderDoubled(int[] A) {
  if (A.length == 0) return true;

  int[] counts = new int[100001];

  for (int a: A) {
    if (a < 0) counts[-a]++;
    else counts[a]++;
  }

  for (int i = 0; i < 100001; i++) {
    if (counts[i] == 0) continue;
    if (i > 100001 / 2) return false;
    if (counts[i] > counts[i * 2]) return false;
    counts[i * 2] -= counts[i]; 
  }

  return true;
}

Solution 2 : Using TreeMap

Code:

public boolean canReorderDoubled(int[] A) {
  if (A.length == 0) return true;

  Map<Integer, Integer> map = new TreeMap<>();

  for (int a: A) {
    if (a < 0) map.put(-a, map.getOrDefault(-a, 0) + 1);
    else map.put(a, map.getOrDefault(a, 0) + 1);
  }

  for (int i = 0; i < 100001; i++) {
    if (counts[i] == 0) continue;
    
    if (map.get(i) > map.getOrDefault(2 * i, 0)) return false;

    map.put(2 * i, map.get(2 * i) - map.get(i));
  }

  return true;
}