Array of Doubled Pairs
MedPrompt
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.
Example 1:
Input: arr = [3,1,3,6]
Output: falseExample 2:
Input: arr = [2,1,2,6]
Output: falseExample 3:
Input: arr = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].
Constraints:
2 <= arr.length <= 3 * 104arr.lengthis even.-105 <= arr[i] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This is a highly efficient approach that uses a hash map to count the occurrences of each number. By processing the numbers in a specific order—sorted by their absolute value—we can greedily form pairs without ambiguity. This avoids the costly nested loops of the previous approach and brings the time complexity down to O(N log N).
Algorithm
- Create a
HashMapto store the frequency of each number in the input arrayarr. This takes a single pass through the array. - Check the count of zeros. If the number of zeros is odd, it's impossible to pair them, so return
false. - Extract the unique numbers (the keys of the map) into a list.
- Sort this list of keys in ascending order based on their absolute values. This is the crucial step that allows for a greedy approach.
- Iterate through the sorted list of keys. For each key
x:- Skip
x = 0as it has already been handled. - Get the count of
xfrom the frequency map, let's call itcount_x. - Find the required partner,
target = 2 * x. - Get the count of the
targetfrom the map,count_target. - If
count_target < count_x, it means there are not enough partners for all thex's. Returnfalse. - If there are enough partners, "consume" them by updating the map:
counts.put(target, count_target - count_x).
- Skip
- If the loop completes without returning
false, it means every number was successfully paired. Returntrue.
Walkthrough
First, we iterate through the input array arr once to build a frequency map (a HashMap in Java). This map stores each unique number and how many times it appears. This step takes O(N) time.
The core idea is to process numbers x before their potential doubles 2x. Sorting by absolute value achieves this perfectly. We extract the unique numbers (the keys of the map) into a list and sort this list in ascending order based on absolute values.
We then iterate through this sorted list of keys. For each number x, we check if we can find a partner 2*x for all of its occurrences. Since we sorted by absolute value, we are guaranteed that when we process x, we haven't yet processed 2*x as a starting element of a pair. We check if the count of 2*x in the map is sufficient. If it is, we decrement the count of 2*x accordingly. If at any point we don't have enough partners for a number x, we can conclude it's impossible and return false.
A special case is x = 0, whose double is also 0. For 0s to be paired, their total count must be even. This is checked upfront. If the loop completes, it means every number found a valid partner.
class Solution { public boolean canReorderDoubled(int[] arr) { Map<Integer, Integer> counts = new HashMap<>(); for (int x : arr) { counts.put(x, counts.getOrDefault(x, 0) + 1); } // Handle the zero case separately if (counts.getOrDefault(0, 0) % 2 != 0) { return false; } List<Integer> keys = new ArrayList<>(counts.keySet()); Collections.sort(keys, Comparator.comparingInt(Math::abs)); for (int x : keys) { if (x == 0) { continue; // Zeroes are handled } // If count of x is greater than count of 2*x, we can't form pairs if (counts.get(x) > counts.getOrDefault(2 * x, 0)) { return false; } // Use up the 2*x values by pairing them with x counts.put(2 * x, counts.get(2 * x) - counts.get(x)); } return true; }}Complexity
Time
O(N log N), where N is the number of elements. Building the frequency map takes O(N). Sorting the U unique keys takes O(U log U). Since U ≤ N, the sorting step dominates, making the overall complexity O(N log N).
Space
O(U), where U is the number of unique elements in the array. In the worst case, U can be equal to N, so the space complexity is O(N). This space is for the HashMap and the list of its keys.
Trade-offs
Pros
Highly efficient with O(N log N) time complexity, which is optimal for a comparison-based approach and passes the given constraints.
The greedy strategy is elegant and robust, correctly handling all cases including positive, negative, and zero values.
Cons
Requires extra space for the hash map and the list of keys, which can be up to O(N) in the worst case where all elements are unique.
Solutions
Solution
class Solution {public boolean canReorderDoubled(int[] arr) { Map<Integer, Integer> freq = new HashMap<>(); for (int v : arr) { freq.put(v, freq.getOrDefault(v, 0) + 1); } if ((freq.getOrDefault(0, 0) & 1) != 0) { return false; } List<Integer> keys = new ArrayList<>(freq.keySet()); keys.sort(Comparator.comparingInt(Math : : abs)); for (int k : keys) { if (freq.getOrDefault(k << 1, 0) < freq.get(k)) { return false; } freq.put(k << 1, freq.getOrDefault(k << 1, 0) - freq.get(k)); } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.