# LeetCode 954: Array of Doubled Pairs

## Problem Restatement

We are given an integer array `arr`.

We want to reorder the array so that for every pair:

```python
(arr[2 * i], arr[2 * i + 1])
```

the second number equals double the first number:

```python
arr[2 * i + 1] = 2 * arr[2 * i]
```

Return `true` if such a reordering is possible. Otherwise, return `false`.

The official constraints are:

| Constraint | Value |
|---|---|
| `2 <= arr.length <= 3 * 10^4` | Array size |
| `arr.length` is even | Pairing is possible in principle |
| `-10^5 <= arr[i] <= 10^5` | Integer range |

Source: LeetCode problem statement. ([leetcode.com](https://leetcode.com/problems/array-of-doubled-pairs/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `arr` |
| Output | `true` if valid doubled pairing exists, otherwise `false` |
| Pair rule | One value must equal double the other |

Example function shape:

```python
def canReorderDoubled(arr: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```python
arr = [3, 1, 3, 6]
```

Output:

```python
False
```

Explanation:

We can pair:

```python
3 -> 6
```

But then:

```python
1
3
```

remain unmatched.

So a valid reordering does not exist.

Example 2:

```python
arr = [2, 1, 2, 6]
```

Output:

```python
False
```

Explanation:

The number `1` requires a matching `2`.

But there are two `2`s and one `6`.

Eventually one `2` cannot find a matching `4`.

Example 3:

```python
arr = [4, -2, 2, -4]
```

Output:

```python
True
```

One valid pairing is:

```python
-2 -> -4
2  -> 4
```

Example 4:

```python
arr = [0, 0]
```

Output:

```python
True
```

Because:

```python
0 = 2 * 0
```

the two zeros form a valid pair.

## First Thought: Greedy Pairing

A natural idea is:

1. Pick a number `x`
2. Search for `2 * x`
3. Remove both numbers
4. Continue

We can track counts using a frequency map.

But ordering matters.

Consider:

```python
arr = [2, 4, 8]
```

If we process `8` first, we search for `16` and fail immediately.

But the real issue is that `8` should have been used as the double of `4`.

So we must process numbers carefully.

## Key Insight

The important observation is:

Small absolute values must be matched before larger absolute values.

Example:

```python
1 -> 2 -> 4 -> 8
```

The number `2` may be needed both as:

- double of `1`
- base for `4`

If we use it incorrectly, later matches fail.

To avoid this, process numbers in increasing order of absolute value.

That guarantees smaller numbers claim their doubles first.

## Why Absolute Value Matters

Negative numbers create a subtle issue.

Example:

```python
-2 -> -4
```

Notice:

```python
|-2| < |-4|
```

If we sort normally:

```python
[-4, -2]
```

then we process `-4` first and incorrectly search for `-8`.

Sorting by absolute value fixes this:

```python
[-2, -4]
```

Now pairing works correctly.

## Algorithm

1. Count frequencies using `Counter`.
2. Sort numbers by absolute value.
3. For each number `x`:
   - If `count[x] == 0`, skip it.
   - If `count[2 * x] == 0`, return `False`.
   - Otherwise:
     - use one `x`
     - use one `2 * x`
4. If all numbers are matched successfully, return `True`.

## Handling Zero

Zero is special because:

```python
0 * 2 = 0
```

So zeros must pair with other zeros.

That means the count of zero must be even.

The algorithm handles this naturally.

Example:

```python
count[0] = 4
```

Processing zeros repeatedly removes them in pairs.

But:

```python
count[0] = 3
```

would eventually fail because one zero remains unmatched.

## Correctness

We process numbers in increasing order of absolute value.

Consider a number `x`.

At the moment we process `x`, every smaller absolute value has already formed its required pairs. Therefore, if `x` is still available, it must now find a matching `2 * x`.

If no copy of `2 * x` exists, then no valid pairing is possible. Any valid arrangement requires every remaining `x` to be paired with one remaining `2 * x`.

If a copy of `2 * x` exists, we consume one copy of each. This correctly creates one valid pair.

Sorting by absolute value is necessary because larger numbers may themselves be doubles needed by smaller numbers. Processing smaller absolute values first guarantees those dependencies are resolved before larger values are used.

For negative numbers, absolute value ordering preserves the correct doubling direction. For example:

```python
-2 -> -4
```

requires `-2` to be processed before `-4`.

The algorithm processes every number exactly as many times as it appears. If the algorithm finishes successfully, every element has been matched into a valid doubled pair. Therefore, the array can be reordered correctly.

## Complexity

Let:

```python
n = len(arr)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(n)` | Frequency map storage |

The greedy matching itself is linear.

## Implementation

```python
from collections import Counter

class Solution:
    def canReorderDoubled(self, arr: list[int]) -> bool:
        count = Counter(arr)

        for x in sorted(arr, key=abs):
            if count[x] == 0:
                continue

            if count[2 * x] == 0:
                return False

            count[x] -= 1
            count[2 * x] -= 1

        return True
```

## Code Explanation

We first count frequencies:

```python
count = Counter(arr)
```

Example:

```python
arr = [4, -2, 2, -4]
```

creates:

```python
{
    4: 1,
    -2: 1,
    2: 1,
    -4: 1
}
```

Then we sort by absolute value:

```python
sorted(arr, key=abs)
```

This gives:

```python
[-2, 2, 4, -4]
```

or another valid equal-absolute ordering.

For each number:

```python
if count[x] == 0:
    continue
```

This means the number was already used in a previous pair.

Next:

```python
if count[2 * x] == 0:
    return False
```

If no matching double exists, pairing fails immediately.

Otherwise we consume one pair:

```python
count[x] -= 1
count[2 * x] -= 1
```

After all numbers are processed successfully:

```python
return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.canReorderDoubled([3, 1, 3, 6]) is False
    assert s.canReorderDoubled([2, 1, 2, 6]) is False
    assert s.canReorderDoubled([4, -2, 2, -4]) is True
    assert s.canReorderDoubled([0, 0]) is True

    assert s.canReorderDoubled([1, 2, 2, 4]) is True
    assert s.canReorderDoubled([-2, -4, -8, -16]) is True
    assert s.canReorderDoubled([1, 2, 4, 16, 8, 4]) is False
    assert s.canReorderDoubled([0, 0, 0, 0]) is True
    assert s.canReorderDoubled([0, 0, 0]) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3,1,3,6]` | One value remains unmatched |
| `[2,1,2,6]` | Missing required double |
| `[4,-2,2,-4]` | Negative number handling |
| `[0,0]` | Zero pairing |
| `[1,2,2,4]` | Multiple valid chains |
| Negative doubling chain | Absolute-value ordering |
| Missing intermediate doubles | Invalid dependency chain |
| Even zero count | Valid zero matching |
| Odd zero count | Impossible zero pairing |