# Array of Doubled Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/array-of-doubled-pairs)
Canonical: https://scaleengineer.com/dsa/problems/array-of-doubled-pairs
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
Given an integer array of even length `arr`, return `true` _if it is possible to reorder_ `arr` _such that_ `arr[2 * i + 1] = 2 * arr[2 * i]` _for every_ `0 <= i < len(arr) / 2`_, or_ `false` _otherwise_.

**Example 1:**

**Input:** arr = [3,1,3,6]
**Output:** false

**Example 2:**

**Input:** arr = [2,1,2,6]
**Output:** false

**Example 3:**

**Input:** arr = [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].

**Constraints:**

* `2 <= arr.length <= 3 * 104`
* `arr.length` is even.
* `-105 <= arr[i] <= 105`

# Approaches
## Sorting and Linear Search
This approach involves sorting the array and then iterating through it to find pairs. By sorting the array based on the absolute values of its elements, we ensure that for any pair `(x, 2x)`, the element with the smaller absolute value (`x`) is processed before the one with the larger absolute value (`2x`). This simplifies the pairing logic, as we always look for the double of the current number.
**Time:** O(N^2), where N is the number of elements in the array. The initial sort takes O(N log N). The nested loops, however, result in a time complexity of O(N^2) in the worst case, as for each element, we might scan a large portion of the remaining array. · **Space:** O(N), where N is the number of elements in the array. This space is used for creating a copy of the array as `Integer[]` to allow custom sorting and for the `used` boolean array.
**Pros:** The logic is straightforward and directly follows from the problem's pairing requirement after sorting.; It correctly handles positive, negative, and zero values due to sorting by absolute value.
**Cons:** The time complexity of O(N^2) is inefficient and will likely lead to a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.; Requires extra O(N) space for the `used` array and for the copy of the array as `Integer[]`.
### Explanation
The algorithm begins by sorting the input array `arr` in ascending order of the absolute values of its elements. This is a crucial step because it establishes a consistent order for processing. This guarantees we always encounter `x` before `2x` (in terms of magnitude), which simplifies the search for pairs.

We use a boolean array `used` to keep track of which elements have already been included in a pair. We iterate through the sorted array. For each element `arr[i]` that hasn't been used yet, we search for its double, `target = 2 * arr[i]`, in the subsequent part of the array. The search for the target must also skip elements that are already used, so a simple linear scan from `i + 1` is performed.

If a matching, unused `target` is found at index `j`, we mark both `arr[i]` and `arr[j]` as used and increment a counter for paired elements. If we successfully iterate through the entire array and the final count of paired elements equals the array's length, it means all elements were paired up, and we return `true`. Otherwise, we return `false`.

```java
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        // Need to use Integer wrapper to sort with a custom comparator
        Integer[] integerArr = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            integerArr[i] = arr[i];
        }
        Arrays.sort(integerArr, Comparator.comparingInt(Math::abs));

        boolean[] used = new boolean[arr.length];
        int pairedCount = 0;

        for (int i = 0; i < arr.length; i++) {
            if (used[i]) {
                continue;
            }
            // This is an unused element, try to find its double
            for (int j = i + 1; j < arr.length; j++) {
                if (!used[j] && integerArr[j] == 2 * integerArr[i]) {
                    used[i] = true;
                    used[j] = true;
                    pairedCount += 2;
                    break; // Found a pair, move to the next element in the outer loop
                }
            }
        }

        return pairedCount == arr.length;
    }
}
```
### Algorithm
- Convert the `int[]` array to `Integer[]` to allow sorting with a custom comparator.
- Sort the `integerArr` based on the absolute value of elements in ascending order. This ensures that for any potential pair `(x, 2x)`, the element with the smaller magnitude (`x`) is processed before the one with the larger magnitude (`2x`).
- Initialize a boolean array `used` of the same size as the input array, with all values set to `false`. This array will track which elements have been successfully paired.
- Initialize a counter `pairedCount` to 0.
- Iterate through the sorted array from `i = 0` to `n-1`:
  - If the current element `integerArr[i]` is already used (i.e., `used[i]` is `true`), skip to the next element.
  - If `integerArr[i]` is not used, perform a linear search for its double (`target = 2 * integerArr[i]`) in the rest of the array (from index `j = i + 1` to `n-1`).
  - The search must find an element that is not yet used. If an unused `target` is found at index `j`:
    - Mark both elements as used by setting `used[i] = true` and `used[j] = true`.
    - Increment the total count of paired elements, `pairedCount`, by 2.
    - Break the inner search loop and proceed to the next element in the outer loop.
- After the loops complete, check if the total number of paired elements `pairedCount` is equal to the length of the array. If it is, all elements were successfully paired, and the function returns `true`. Otherwise, it returns `false`.

## Frequency Map with Sorted Keys
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).
**Time:** O(N log N), where N is the number of elements. Building the frequency map takes O(N). Sorting the U unique keys takes O(U log U). Since U ≤ N, the sorting step dominates, making the overall complexity O(N log N). · **Space:** O(U), where U is the number of unique elements in the array. In the worst case, U can be equal to N, so the space complexity is O(N). This space is for the HashMap and the list of its keys.
**Pros:** Highly efficient with O(N log N) time complexity, which is optimal for a comparison-based approach and passes the given constraints.; The greedy strategy is elegant and robust, correctly handling all cases including positive, negative, and zero values.
**Cons:** Requires extra space for the hash map and the list of keys, which can be up to O(N) in the worst case where all elements are unique.
### Explanation
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 `0`s 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.

```java
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;
    }
}
```
### Algorithm
- 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`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  bool canReorderDoubled(vector<int> &arr) {
    unordered_map<int, int> freq;
    for (int &v : arr)
      ++freq[v];
    if (freq[0] & 1)
      return false;
    vector<int> keys;
    for (auto &[k, _] : freq)
      keys.push_back(k);
    sort(keys.begin(), keys.end(),
         [](int a, int b) { return abs(a) < abs(b); });
    for (int &k : keys) {
      if (freq[k * 2] < freq[k])
        return false;
      freq[k * 2] -= freq[k];
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool: freq = Counter(arr) if freq[0] & 1: return False for x in sorted(freq, key=abs): if freq[x << 1] < freq[x]: return False freq[x << 1] -= freq[x] return True

```