Problem Description

You are given an integer array arr of even length. Your task is to determine if it's possible to reorder the array such that for every pair of consecutive elements at positions 2*i and 2*i+1, the second element is exactly double the first element.

More specifically, after reordering, the array should satisfy: arr[2*i+1] = 2 * arr[2*i] for every valid index i where 0 <= i < len(arr)/2.

The function should return true if such a reordering is possible, and false otherwise.

For example:

• If arr = [3, 1, 3, 6], we can reorder it to [3, 6, 1, 2] which doesn't work, or [1, 2, 3, 6] which also doesn't work. Actually, we need pairs where each second element is double the first. We could arrange it as [3, 6, 1, 2] where 6 = 2*3 and 2 = 2*1, so this would return true.
• If arr = [4, -2, 2, -4], we can reorder it to [-2, -4, 2, 4] where -4 = 2*(-2) and 4 = 2*2, so this would return true.

The key insight is that we need to pair up elements where one element is exactly double the other, and we must be able to use all elements in the array exactly once in such pairs.

Intuition

The core idea is that we need to form pairs where one element is exactly double the other. Think of it like a matching problem - for each number x, we need to find its double 2x to form a valid pair.

Let's think about which elements can be paired together. For a positive number x, we need to pair it with 2x. For a negative number x, we also need to pair it with 2x (which will also be negative). For example, -3 pairs with -6.

The key insight is to process numbers in a specific order. If we process them by their absolute values (smallest absolute value first), we can avoid conflicts. Why? Consider this:

• If we have numbers like 2, 4, 8, we want to pair 2 with 4 first, not 4 with 8. This is because 2 can only pair with 4, but 4 could potentially pair with either 2 (as the double) or 8 (as the half).
• By processing from smallest absolute value, we ensure that when we process a number x, we're looking for 2x, not x/2. This eliminates ambiguity.

For the frequency counting approach: if a number x appears freq[x] times, then 2x must appear at least freq[x] times to form valid pairs. After pairing all occurrences of x with 2x, we reduce the count of 2x by freq[x].

Special case for zero: Zero can only pair with itself (0 * 2 = 0), so if we have an odd number of zeros, it's impossible to form valid pairs.

By sorting by absolute value and greedily pairing each number with its double, we can determine if a valid reordering exists. If at any point we can't find enough doubles for a number, we know it's impossible.

Learn more about Greedy and Sorting patterns.

Solution Approach

The solution uses a frequency counter and greedy pairing strategy:

1. Count frequencies: First, we create a frequency map using Counter(arr) to track how many times each number appears in the array.

2. Handle zeros: Check if the count of zeros is odd with freq[0] & 1. If it's odd, return False immediately since zeros can only pair with themselves, requiring an even count.

3. Sort by absolute value: We sort the keys of the frequency map by their absolute values using sorted(freq, key=abs). This ensures we process numbers from smallest to largest absolute value.

4. Greedy pairing: For each number x in our sorted order:

   • We need to pair all freq[x] occurrences of x with 2x
   • Check if we have enough doubles: freq[x << 1] < freq[x] (using left shift x << 1 which equals 2 * x)
   • If we don't have enough doubles, return False
   • Otherwise, reduce the frequency of 2x by freq[x] since those are now paired: freq[x << 1] -= freq[x]

5. Return result: If we successfully process all numbers without running out of doubles, return True.

The algorithm works because:

• By processing from smallest absolute value, when we encounter x, we always pair it with 2x (never with x/2)
• This avoids the ambiguity of whether a number should be the smaller or larger element in a pair
• The greedy approach is optimal because each number must be paired exactly once
• Time complexity: O(n log n) for sorting
• Space complexity: O(n) for the frequency counter

Example Walkthrough

Let's walk through the example arr = [4, -2, 2, -4]:

Step 1: Count frequencies

• freq = {4: 1, -2: 1, 2: 1, -4: 1}

Step 2: Check zeros

• No zeros in the array, so we continue.

Step 3: Sort by absolute value

• Sorted keys: [-2, 2, 4, -4] (both -2 and 2 have absolute value 2, then 4 and -4 have absolute value 4)

Step 4: Process each number greedily

Processing -2:

• Need to pair 1 occurrence of -2 with 2*(-2) = -4
• Check: Do we have at least 1 occurrence of -4? Yes, freq[-4] = 1
• Pair them: freq[-4] = 1 - 1 = 0
• Current pairs: [-2, -4]

Processing 2:

• Need to pair 1 occurrence of 2 with 2*2 = 4
• Check: Do we have at least 1 occurrence of 4? Yes, freq[4] = 1
• Pair them: freq[4] = 1 - 1 = 0
• Current pairs: [-2, -4], [2, 4]

Processing 4:

• Need to pair 0 occurrences (since freq[4] = 0 now after being paired)
• Skip, already paired as a double

Processing -4:

• Need to pair 0 occurrences (since freq[-4] = 0 now after being paired)
• Skip, already paired as a double

Step 5: Success! All numbers have been successfully paired. The valid reordering would be [-2, -4, 2, 4].

Let's verify:

• Position 0,1: -4 = 2 * (-2) ✓
• Position 2,3: 4 = 2 * 2 ✓

Return True.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The time complexity is dominated by the sorting operation:

• Creating the frequency counter takes O(n) where n is the length of the input array
• Sorting the frequency keys by absolute value takes O(k log k) where k is the number of unique elements. In the worst case, k = n, so this becomes O(n log n)
• The iteration through sorted keys takes O(k) time, with each operation inside being O(1)
• Overall time complexity: O(n) + O(n log n) + O(n) = O(n log n)

Space Complexity: O(n)

The space complexity comes from:

• The frequency counter freq stores at most n unique elements (when all elements are distinct), requiring O(n) space
• The sorted operation creates a new list of keys, which takes O(k) space where k ≤ n
• Overall space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not handling zeros correctly

A frequent mistake is forgetting that zeros need special handling. Since 0 * 2 = 0, zeros can only pair with themselves, requiring an even count.

Incorrect approach:

# Missing zero check
for x in sorted(freq, key=abs):
    if freq[x * 2] < freq[x]:
        return False
    freq[x * 2] -= freq[x]

Correct approach:

if freq[0] % 2 == 1:  # Check zeros first
    return False

2. Processing order confusion with negative numbers

The algorithm must process numbers by absolute value to ensure correct pairing. Processing in regular sorted order fails for negative numbers.

Incorrect approach:

# Wrong: sorts by value, not absolute value
for x in sorted(freq):  
    # This processes -4 before -2, causing incorrect pairing

Correct approach:

for x in sorted(freq, key=abs):  # Sort by absolute value
    # This processes -2 before -4, enabling correct pairing

3. Double counting when a number appears multiple times

Some implementations try to check if 2*x exists without considering frequencies, leading to incorrect results when elements repeat.

Incorrect approach:

# Wrong: only checks existence, not frequency
for x in arr:
    if 2*x not in arr:
        return False

Correct approach:

# Must track and update frequencies
if freq[x * 2] < freq[x]:
    return False
freq[x * 2] -= freq[x]  # Decrease available doubles

4. Not considering that each element must be used exactly once

A pitfall is thinking we just need to find pairs without ensuring all elements are used exactly once in the pairing.

Example scenario: For arr = [1, 2, 4, 8]:

• We could pair (1,2) and (4,8)
• But we could also try pairing (2,4), leaving 1 and 8 unpaired
• The algorithm must systematically ensure all elements get paired

The greedy approach starting from smallest absolute values prevents this issue by deterministically choosing pairs.