LeetCode 954 - Array of Doubled Pairs

The problem asks whether it is possible to reorder an even-length array arr of integers such that every element can be paired with another element that is exactly double its value.

leetcodemediumarrayhash-tablegreedysorting

LeetCode Problem 954

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting

Solution

Problem Understanding

The problem asks whether it is possible to reorder an even-length array arr of integers such that every element can be paired with another element that is exactly double its value. In other words, after reordering, for every index i in the first half of the array, arr[2 * i + 1] should equal 2 * arr[2 * i].

The input is an array of integers that can be positive, negative, or zero. The output is a boolean: true if a valid reordering exists, false otherwise.

The constraints tell us that the array can be quite large, up to 30,000 elements, so an algorithm that is worse than O(n log n) will likely be too slow. The input array is guaranteed to have an even length, which ensures that pairing is theoretically possible if the values allow. Edge cases include arrays with zeros, negative numbers, duplicate numbers, or numbers that cannot form the required double pairings.

Approaches

A brute-force approach would attempt to generate all possible permutations of the array and check whether any of them satisfy the doubling condition. While this is guaranteed to give the correct answer, the number of permutations grows factorially with the length of the array, making it completely impractical for arrays of length up to 30,000.

The key insight for an optimal solution is to consider frequency counting and sorting by absolute value. Instead of trying all permutations, we can count how many times each number appears and attempt to pair each number with its double. Sorting by absolute value ensures that we handle negative numbers correctly (e.g., pairing -2 with -4 works only if we process -2 before -4). This approach uses a hash map for counting and a greedy strategy for pairing, giving a much more efficient solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generate all permutations and check each for validity, infeasible for large n
Optimal O(n log n) O(n) Count frequencies, sort by absolute value, greedily pair numbers with their doubles

Algorithm Walkthrough

  1. Initialize a hash map to count the frequency of each integer in the array.

  2. Sort the array by absolute value. Sorting by absolute value ensures that smaller numbers, including negative numbers, are paired before their doubles.

  3. Iterate through each number in the sorted array:

  4. If the frequency of the current number is zero, skip it because it has already been paired.

  5. Check if the double of the current number exists in the frequency map with a positive count.

  6. If it does not exist or the count is insufficient, return false because a valid pairing is impossible.

  7. If it exists, decrement the frequency of both the current number and its double to mark them as paired.

  8. If all numbers have been successfully paired, return true.

Why it works: By sorting by absolute value, we ensure that each number is paired with the smallest possible double that hasn't been used yet. This guarantees that no number is left without a valid partner, fulfilling the problem's requirement.

Python Solution

from collections import Counter
from typing import List

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

The implementation first builds a frequency map of all elements in the array. It then processes each number in order of increasing absolute value to ensure that negative numbers are paired correctly. For each number, it checks if its double is available. If not, the function returns false. Otherwise, it marks both numbers as used by decrementing their counts. If all numbers are paired successfully, the function returns true.

Go Solution

import "sort"

func canReorderDoubled(arr []int) bool {
    count := make(map[int]int)
    for _, num := range arr {
        count[num]++
    }
    
    sort.Slice(arr, func(i, j int) bool {
        a, b := arr[i], arr[j]
        if a < 0 {
            a = -a
        }
        if b < 0 {
            b = -b
        }
        return a < b
    })
    
    for _, x := range arr {
        if count[x] == 0 {
            continue
        }
        if count[2*x] == 0 {
            return false
        }
        count[x]--
        count[2*x]--
    }
    
    return true
}

The Go version mirrors the Python approach. It uses a map to count frequencies and sort.Slice to sort by absolute value. The key difference is Go’s handling of map access and slice sorting, but the algorithmic logic remains the same.

Worked Examples

Example 1: arr = [3,1,3,6]

x count[x] before count[2*x] before action count[x] after count[2*x] after
1 1 0 Cannot pair 1 with 2 return false -

Output: false

Example 3: arr = [4,-2,2,-4]

Sorted by absolute value: [-2,2,-4,4]

x count[x] before count[2*x] before action count[x] after count[2*x] after
-2 1 1 pair with -4 0 0
2 1 1 pair with 4 0 0

All numbers paired, Output: true

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates; iteration and map access are O(n)
Space O(n) Hash map stores count of each number

Sorting ensures correct pairing order and hash map allows O(1) access to check for doubles.

Test Cases

# Provided examples
assert Solution().canReorderDoubled([3,1,3,6]) == False  # cannot pair 1 with 2
assert Solution().canReorderDoubled([2,1,2,6]) == False  # cannot pair 1 with 2
assert Solution().canReorderDoubled([4,-2,2,-4]) == True  # pairs: [-2,-4],[2,4]

# Additional cases
assert Solution().canReorderDoubled([1,2,4,8]) == True  # pairs: [1,2],[4,8]
assert Solution().canReorderDoubled([0,0,0,0]) == True  # zeros can pair with zeros
assert Solution().canReorderDoubled([-1,-2,1,2]) == True  # negative and positive pairs
assert Solution().canReorderDoubled([1,3,6,12]) == False  # cannot pair 3 with 6 correctly
assert Solution().canReorderDoubled([1,1,2,2,4,4]) == True  # multiple duplicates
Test Why
[3,1,3,6] Tests unpairable element
[4,-2,2,-4] Tests negative numbers and absolute sorting
[0,0,0,0] Edge case of zeros
[-1,-2,1,2] Tests pairing with negatives
[1,1,2,2,4,4] Tests multiple duplicates

Edge Cases

A critical edge case is arrays containing zeros. Since 0 doubled is still 0, we need an even number of zeros to form pairs. The implementation handles this automatically via the frequency map.

Negative numbers are another potential trap. Without sorting by absolute value, the algorithm might attempt to pair a larger negative number with its smaller double incorrectly. Sorting by absolute value ensures correct greedy pairing.

Finally, duplicate numbers can complicate pairing, especially if the same number appears multiple times but its double does not appear in sufficient quantity. The hash map ensures each element is only used once, avoiding overcounting and incorrect pairings.