Array of Doubled Pairs

This is a highly efficient approach that uses a hash map to count the occurrences of each number. By processing the numbers in a specific order—sorted by their absolute value—we can greedily form pairs without ambiguity. This avoids the costly nested loops of the previous approach and brings the time complexity down to O(N log N).

• Create a HashMap to store the frequency of each number in the input array arr. This takes a single pass through the array.
• Check the count of zeros. If the number of zeros is odd, it's impossible to pair them, so return false.
• Extract the unique numbers (the keys of the map) into a list.
• Sort this list of keys in ascending order based on their absolute values. This is the crucial step that allows for a greedy approach.
• Iterate through the sorted list of keys. For each key x:
  • Skip x = 0 as it has already been handled.
  • Get the count of x from the frequency map, let's call it count_x.
  • Find the required partner, target = 2 * x.
  • Get the count of the target from the map, count_target.
  • If count_target < count_x, it means there are not enough partners for all the x's. Return false.
  • If there are enough partners, "consume" them by updating the map: counts.put(target, count_target - count_x).
• If the loop completes without returning false, it means every number was successfully paired. Return true.

First, we iterate through the input array arr once to build a frequency map (a HashMap in Java). This map stores each unique number and how many times it appears. This step takes O(N) time.

The core idea is to process numbers x before their potential doubles 2x. Sorting by absolute value achieves this perfectly. We extract the unique numbers (the keys of the map) into a list and sort this list in ascending order based on absolute values.

We then iterate through this sorted list of keys. For each number x, we check if we can find a partner 2*x for all of its occurrences. Since we sorted by absolute value, we are guaranteed that when we process x, we haven't yet processed 2*x as a starting element of a pair. We check if the count of 2*x in the map is sufficient. If it is, we decrement the count of 2*x accordingly. If at any point we don't have enough partners for a number x, we can conclude it's impossible and return false.

A special case is x = 0, whose double is also 0. For 0s to be paired, their total count must be even. This is checked upfront. If the loop completes, it means every number found a valid partner.

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : arr) {
            counts.put(x, counts.getOrDefault(x, 0) + 1);
        }

        // Handle the zero case separately
        if (counts.getOrDefault(0, 0) % 2 != 0) {
            return false;
        }

        List<Integer> keys = new ArrayList<>(counts.keySet());
        Collections.sort(keys, Comparator.comparingInt(Math::abs));

        for (int x : keys) {
            if (x == 0) {
                continue; // Zeroes are handled
            }
            
            // If count of x is greater than count of 2*x, we can't form pairs
            if (counts.get(x) > counts.getOrDefault(2 * x, 0)) {
                return false;
            }
            
            // Use up the 2*x values by pairing them with x
            counts.put(2 * x, counts.get(2 * x) - counts.get(x));
        }

        return true;
    }
}