Array of Doubled Pairs

Problem Description

Given an integer array of even length arr, return true if it is possible to reorder arr such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2, or false otherwise.

Key Insights

• The array must have pairs of numbers where one number is double the other.
• Counting occurrences of each number can help in determining if valid pairs can be formed.
• Sorting the array allows us to process numbers in increasing order, making it easier to find pairs.
• Handling negative numbers correctly is crucial, as doubling a negative number yields another negative number.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(n) - for storing counts of numbers in a hash table.

Solution

To solve the problem, we can use the following approach:

1. Count the occurrences of each number in the array using a hash table.
2. Sort the unique numbers of the array.
3. Iterate through the sorted numbers, and for each number, check if the double exists in the counts. If it does, decrement the counts accordingly. If at any point the required double is not available, return false.
4. If we can pair all numbers, return true.

Code Solutions