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:

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

the second number equals double the first number:

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

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

The official constraints are:

Source: LeetCode problem statement. (leetcode.com)

Input and Output

Example function shape:

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

Examples

Example 1:

arr = [3, 1, 3, 6]

Output:

False

Explanation:

We can pair:

3 -> 6

But then:

1
3

remain unmatched.

So a valid reordering does not exist.

Example 2:

arr = [2, 1, 2, 6]

Output:

False

Explanation:

The number 1 requires a matching 2.

But there are two 2s and one 6.

Eventually one 2 cannot find a matching 4.

Example 3:

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

Output:

True

One valid pairing is:

-2 -> -4
2  -> 4

Example 4:

arr = [0, 0]

Output:

True

Because:

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:

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:

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:

-2 -> -4

Notice:

|-2| < |-4|

If we sort normally:

[-4, -2]

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

Sorting by absolute value fixes this:

[-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:

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:

count[0] = 4

Processing zeros repeatedly removes them in pairs.

But:

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:

-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:

n = len(arr)

The greedy matching itself is linear.

Implementation

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:

count = Counter(arr)

Example:

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

creates:

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

Then we sort by absolute value:

sorted(arr, key=abs)

This gives:

[-2, 2, 4, -4]

or another valid equal-absolute ordering.

For each number:

if count[x] == 0:
    continue

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

Next:

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

If no matching double exists, pairing fails immediately.

Otherwise we consume one pair:

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

After all numbers are processed successfully:

return True

Testing

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: