Solution Explanation: Array of Doubled Pairs

The problem asks whether we can reorder an array of even length such that each element is half the value of the next element. The solution uses a greedy approach combined with hash table (or map) and sorting for efficient processing.

Approach:

1. Frequency Counting: We first count the frequency of each element in the input array arr using a hash map (dictionary in Python). This allows for quick lookup of element counts.

2. Handling Zeroes: If the count of 0 is odd, it's impossible to form pairs, so we return False.

3. Sorted Processing: We sort the unique elements of the array based on their absolute values. This is crucial because we want to check for pairs starting from the smallest numbers to avoid conflicts. Smaller numbers are processed first so that if a number has a corresponding double, it's more likely to be found.

4. Greedy Pairing: We iterate through the sorted unique elements. For each element x, we check if its double (2 * x) exists and if its frequency is at least as large as the frequency of x.

   • If 2 * x has a frequency smaller than x, it means we don't have enough doubles to pair with all instances of x, so we return False.

   • If the condition is met, we update the frequency of 2 * x by subtracting the frequency of x. This simulates pairing the elements and removes them from consideration for future pairings.

5. Final Result: If the loop completes without returning False, it means we successfully formed all pairs, and we return True.

Time Complexity Analysis:

• Frequency counting: O(n), where n is the length of the input array.
• Sorting: O(k log k), where k is the number of unique elements in the array. In the worst case, k could be n, but often it's much smaller.
• Greedy pairing: O(k), where k is the number of unique elements.

Therefore, the overall time complexity is dominated by the sorting step, making it O(k log k) or O(n log n) in the worst case. In many scenarios, the number of unique elements (k) will be much smaller than n, making it more efficient than a purely brute-force approach.

Space Complexity Analysis:

The space complexity is O(k) to store the frequency map and the sorted unique elements, where k is the number of unique elements in the array. Again, in the worst case, k could be n, but often it will be smaller.

Code Examples (with explanations inline):

The provided code examples in Python, Java, C++, and Go all implement this approach. The logic is the same across languages; only syntax differs. For example, let's focus on the Python code:

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        freq = Counter(arr) # Count element frequencies using Counter (efficient for this task)
        if freq[0] % 2: # Check if the count of 0 is odd
            return False
        for x in sorted(freq, key=abs): # Iterate through sorted unique elements by absolute value
            if freq[x << 1] < freq[x]: # Check if enough doubles exist for x
                return False
            freq[x << 1] -= freq[x] # Update frequency of double after pairing
        return True

The other languages use similar structures: hash maps (HashMap in Java, unordered_map in C++, map in Go) to count frequencies and then iterating through sorted keys to perform the greedy pairing. The sorted function in Python and equivalent functions in other languages handle the sorting by absolute value.