Array of Doubled Pairs: Greedy Matching with Frequency Maps

LeetCode 954, Array of Doubled Pairs, is a medium problem that asks whether you can reorder an integer array so that for every index i, arr[2*i+1] == 2 * arr[2*i]. In other words, you need to pair up all elements such that one element in each pair is exactly double the other.

The problem

Given an integer array of even length, determine if it can be reordered such that arr[2*i+1] == 2 * arr[2*i] for every 0 <= i < len(arr) / 2.

Input:  arr = [4, -2, 2, -4]
Output: True

One valid reordering is [-2, -4, 2, 4]. Here -4 == 2 * (-2) and 4 == 2 * 2.

Why this problem matters

This problem is a clean example of the greedy matching pattern: you have a collection of items, each needs to find a specific partner, and you need to decide whether all items can be paired up. This same structure appears in problems about forming groups, scheduling pairs, and matching resources to requests. Once you see the pattern, you can apply it broadly.

The frequency counting angle is equally important. Instead of literally removing elements from the array as you pair them (which is slow), you keep a count map and decrement counts as pairs are consumed. This is a fundamental technique that shows up in anagram detection, duplicate counting, and many grouping problems.

Finally, the sorting trick here is subtle but powerful. Sorting by absolute value is not an obvious first move, but it is the key that makes the greedy approach correct. Understanding why this ordering works builds your intuition for when and how custom sort orders unlock greedy solutions.

The brute force approach

The most direct approach would be to try every possible pairing. You could generate all permutations of the array and check whether adjacent pairs satisfy the doubling condition. With n elements, there are n! permutations, which is astronomically slow even for small inputs.

A slightly better brute force would be to pick an element, search for its double, remove both, and repeat. But searching and removing from a list is O(n) per operation, giving O(n^2) overall. We can do much better.

The key insight

The trick is to process elements in order of absolute value, smallest first. When you encounter a value x, you try to pair it with 2x. If you process larger values first, you might accidentally pair them with even larger values and leave smaller values stranded.

Sorting by absolute value ensures that when you process x, the value x/2 has already been processed (if it existed). So x can only pair "upward" with 2x, never "downward" with x/2. This greedy choice is always safe.

Walking through it step by step

The solution

from collections import Counter

def canReorderDoubled(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

1. Build a frequency map. Counter(arr) creates a dictionary where each key is a value from the array and each value is how many times it appears.

2. Sort unique keys by absolute value. sorted(count, key=abs) gives us the distinct elements ordered from smallest magnitude to largest. This is the critical ordering that makes greedy matching correct.

3. Try to pair each x with 2x. For each unique value x, we need count[x] copies of 2x to be available. If count[x] > count[2 * x], there are not enough doubles and we return False immediately.

4. Consume the doubles. count[2 * x] -= count[x] removes the copies of 2x that were used to pair with x. The remaining copies of 2x are available for later pairings (when we process 2x itself, it will look for 4x).

5. If we never run out, return True. Every element found its partner, so a valid reordering exists.

Complexity analysis

Building the Counter takes O(n) time. Sorting the distinct keys takes O(k log k) where k is the number of unique values, and k is at most n. The loop processes each unique value once, doing O(1) work per value. So the total time is dominated by the sort: O(n log n).

For space, the Counter stores at most n entries (one per unique value), so we use O(n) additional memory.

Building blocks

1. Greedy matching with frequency maps

The core pattern here is: build a frequency map, iterate in a specific order, and consume counts as you form matches. This shows up whenever you need to group or pair elements based on some relationship.

from collections import Counter

def can_match_pairs(arr, relationship):
    count = Counter(arr)
    for x in sorted(count, key=some_ordering):
        target = relationship(x)
        if count[x] > count[target]:
            return False
        count[target] -= count[x]
    return True

The template is the same whether you are pairing x with 2x, x with x+1, or x with any other function of x. The sort order is what changes to make the greedy choice correct.

2. Absolute value sorting for signed integers

When a problem involves both positive and negative numbers with a multiplicative relationship, sorting by absolute value groups related elements together. For additive relationships (like x and x+1), you would sort by the values themselves.

# Multiplicative relationship: sort by abs
sorted(arr, key=abs)

# Additive relationship: sort by value
sorted(arr)

The reason absolute value works for doubling is that -2 and -4 have the same absolute-value relationship as 2 and 4. Sorting by absolute value means you always process the "smaller" member of a pair before the "larger" one, regardless of sign.

Edge cases

• Array with all zeros: [0, 0, 0, 0]. Each 0 pairs with 0 since 0 == 2*0. Returns True.
• Negative numbers: [-2, -4]. -4 == 2*(-2). Returns True.
• Mix of positive and negative that cannot pair: [1, -1]. Need 2 for 1 and -2 for -1, but neither exists. Returns False.
• Single pair: [2, 4]. The simplest valid case.
• Odd-length array: impossible by constraint (always even length).

Common mistakes

1. Sorting by value instead of absolute value. If you sort normally, negative numbers come first in decreasing magnitude: [-4, -2, 2, 4]. Then when you process -4 first, you look for -8, which does not exist, and incorrectly return False.

2. Forgetting to handle zero. Zero is its own double (0 == 20), so you need an even number of zeros. The Counter-based approach handles this automatically since count[0] must be paired with count[20] = count[0], and any count is always equal to itself.

3. Removing elements from a list during iteration. Modifying a list while iterating over it causes subtle bugs. Use a frequency map instead and decrement counts.

4. Not iterating over unique keys. If you iterate over the full sorted array instead of the unique keys, you process already-consumed elements and get incorrect results. Always iterate over sorted(count, key=abs).

5. Checking count[x] != 0 before processing. You do not need this check. If count[x] is 0 (already fully consumed by a previous pairing), then count[x] > count[2*x] is False (since 0 is not greater than anything non-negative), and count[2*x] -= 0 is a no-op. The code handles it cleanly without a special case.

From understanding to recall

The core of this problem is one clean insight: sort by absolute value, then greedily match each element with its double. Everything else follows from that. When you review this problem, focus on remembering why absolute value sorting is correct and why processing smallest magnitudes first gives a "no regret" greedy strategy.

Practice writing the solution from scratch. The function is only six lines, but each line does something important: build the counter, sort by absolute value, check the pairing condition, consume the doubles, and return. Once you can reproduce this without looking, you have internalized both the greedy matching pattern and the frequency map technique.

Try to connect this problem to others that use similar ideas. Hand of Straights asks you to form consecutive groups instead of doubling pairs, but the structure is nearly identical: sort, iterate, consume counts. Recognizing that shared skeleton across problems is what turns individual solutions into reusable patterns.

Related posts

• Hand of Straights - Another greedy grouping problem that sorts and matches elements into groups
• Contains Duplicate - Foundational hash map frequency counting pattern
• Sort Array by Parity - Custom sort ordering with array rearrangement