Code Implementation

from collections import Counter

class Solution:
    def canReorderDoubled(self, arr):
        count = Counter(arr)
        for x in sorted(count, key=abs):
            if count[x] > count[2 * x]:
                return False
            count[2 * x] -= count[x]
        return True
    

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        unordered_map<int, int> count;
        for (int x : arr) count[x]++;
        vector<int> keys;
        for (auto &kv : count) keys.push_back(kv.first);
        sort(keys.begin(), keys.end(), [](int a, int b) { return abs(a) < abs(b); });
        for (int x : keys) {
            if (count[x] > count[2 * x]) return false;
            count[2 * x] -= count[x];
        }
        return true;
    }
};
    

import java.util.*;

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : arr)
            count.put(x, count.getOrDefault(x, 0) + 1);
        List<Integer> keys = new ArrayList<>(count.keySet());
        keys.sort(Comparator.comparingInt(Math::abs));
        for (int x : keys) {
            if (count.get(x) > count.getOrDefault(2 * x, 0))
                return false;
            count.put(2 * x, count.getOrDefault(2 * x, 0) - count.get(x));
        }
        return true;
    }
}
    

var canReorderDoubled = function(arr) {
    let count = new Map();
    for (let x of arr) {
        count.set(x, (count.get(x) || 0) + 1);
    }
    let keys = Array.from(count.keys());
    keys.sort((a, b) => Math.abs(a) - Math.abs(b));
    for (let x of keys) {
        if (count.get(x) > (count.get(2 * x) || 0)) return false;
        count.set(2 * x, (count.get(2 * x) || 0) - count.get(x));
    }
    return true;
};
    

Problem Description

Given an array arr of integers, your task is to determine if it is possible to reorder the array so that for every element x, there exists another element y such that y = 2 * x. In other words, you need to pair up all elements in the array so that one element in each pair is exactly double the other. Each element in the array can be used only once in a pair. If such a reordering and pairing is possible, return true; otherwise, return false.

• All elements must be paired; no leftovers are allowed.
• Each element can only be used in one pair.
• The input array may contain positive, negative, and zero values.

Thought Process

At first glance, the problem seems to suggest checking all possible pairings, which would be very inefficient. If we try to brute-force all possible pairs, the number of combinations grows rapidly as the array size increases. We need a more efficient way to check if every number can be paired with its double, and to do so without reusing any elements.

A key insight is to use counting: for each number, we want to know how many times it appears and how many times its double appears. But we must be careful with negative numbers and zeros, since doubling negatives or zeros has subtle effects. Sorting the array by absolute value helps ensure we always try to pair smaller numbers first, which avoids running into situations where we can't find a double for a smaller number because it was already used in a previous pair.

Using a hash map (or dictionary) to count occurrences, and then processing the numbers in order of their absolute values, allows us to efficiently form valid pairs or determine if it's impossible.

Solution Approach

• Count the occurrences: Use a hash map or counter to record how many times each number appears in the array.
• Sort by absolute value: Create a list of the unique numbers and sort them by their absolute value. This ensures we process numbers in an order that avoids conflicts (e.g., pairing 2 with 4 before 4 with 8).
• Pairing process: For each number x in the sorted list:
  • Check if there are enough 2 * x to pair with all occurrences of x (i.e., is count[2 * x] >= count[x]?).
  • If not, return false immediately because pairing is impossible.
  • If yes, subtract count[x] from count[2 * x] to indicate those numbers have been used in pairs.
• Return the result: If all numbers can be paired successfully, return true.

This approach leverages the efficiency of hash maps for counting and the logic of absolute-value sorting to ensure correctness across positive, negative, and zero values.

Example Walkthrough

Let's walk through the example arr = [4, -2, 2, -4]:

1. Count occurrences:
   • 4: 1
   • -2: 1
   • 2: 1
   • -4: 1
2. Sort unique numbers by absolute value: [2, -2, 4, -4]
3. Pairing process:
   • 2: Need to pair with 4. There is one 4, so pair them. Decrement count of 4 to 0.
   • -2: Need to pair with -4. There is one -4, so pair them. Decrement count of -4 to 0.
   • 4: Already used up (count is 0), so skip.
   • -4: Already used up (count is 0), so skip.
4. All numbers have been paired successfully. Return true.

Time and Space Complexity

• Brute-force approach:
  • Would involve checking all permutations or all possible pairings, which is O((2n)!/(n!)) time — infeasible for large arrays.
• Optimized approach:
  • Counting all elements: O(n)
  • Sorting unique keys by absolute value: O(k log k), where k is the number of unique elements (at most n)
  • Processing and pairing: O(k)
  • Total time complexity: O(n log n)
  • Space complexity: O(n) for the counter/hash map

Summary

The "Array of Doubled Pairs" problem can be solved efficiently by counting occurrences of each number and then attempting to pair each number with its double, processing numbers in order of their absolute value. This strategy avoids brute-force pairing and handles all cases, including negative numbers and zeros, in O(n log n) time. The key insight is to use a hash map for counting and to always pair smaller absolute values first, ensuring elements are not reused and all pairs are valid.