Array of Doubled Pairs

Med

#0908Time: 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.

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Hash Table

Prompt

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: false

Example 2:

Input: arr = [2,1,2,6]
Output: false

Example 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 * 10⁴
arr.length is even.
-10⁵ <= arr[i] <= 10⁵

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 HashMap to store the frequency of each number in the input array arr. 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 = 0 as it has already been handled.
- Get the count of x from the frequency map, let's call it count_x.
- Find the required partner, target = 2 * x.
- Get the count of the target from the map, count_target.
- If count_target < count_x, it means there are not enough partners for all the x's. Return false.
- If there are enough partners, "consume" them by updating the map: counts.put(target, count_target - count_x).
If the loop completes without returning false, it means every number was successfully paired. Return true.

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.

1class Solution {2    public boolean canReorderDoubled(int[] arr) {3        Map<Integer, Integer> counts = new HashMap<>();4        for (int x : arr) {5            counts.put(x, counts.getOrDefault(x, 0) + 1);6        }7 8        // Handle the zero case separately9        if (counts.getOrDefault(0, 0) % 2 != 0) {10            return false;11        }12 13        List<Integer> keys = new ArrayList<>(counts.keySet());14        Collections.sort(keys, Comparator.comparingInt(Math::abs));15 16        for (int x : keys) {17            if (x == 0) {18                continue; // Zeroes are handled19            }20            21            // If count of x is greater than count of 2*x, we can't form pairs22            if (counts.get(x) > counts.getOrDefault(2 * x, 0)) {23                return false;24            }25            26            // Use up the 2*x values by pairing them with x27            counts.put(2 * x, counts.get(2 * x) - counts.get(x));28        }29 30        return true;31    }32}

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.

This approach involves sorting the array and then iterating through it to find pairs. By sorting the array based on the absolute values of its elements, we ensure that for any pair (x, 2x), the element with the smaller absolute value (x) is processed before the one with the larger absolute value (2x). This simplifies the pairing logic, as we always look for the double of the current number.

Algorithm

Convert the int[] array to Integer[] to allow sorting with a custom comparator.
Sort the integerArr based on the absolute value of elements in ascending order. This ensures that for any potential pair (x, 2x), the element with the smaller magnitude (x) is processed before the one with the larger magnitude (2x).
Initialize a boolean array used of the same size as the input array, with all values set to false. This array will track which elements have been successfully paired.
Initialize a counter pairedCount to 0.
Iterate through the sorted array from i = 0 to n-1:
- If the current element integerArr[i] is already used (i.e., used[i] is true), skip to the next element.
- If integerArr[i] is not used, perform a linear search for its double (target = 2 * integerArr[i]) in the rest of the array (from index j = i + 1 to n-1).
- The search must find an element that is not yet used. If an unused target is found at index j:
  - Mark both elements as used by setting used[i] = true and used[j] = true.
  - Increment the total count of paired elements, pairedCount, by 2.
  - Break the inner search loop and proceed to the next element in the outer loop.
After the loops complete, check if the total number of paired elements pairedCount is equal to the length of the array. If it is, all elements were successfully paired, and the function returns true. Otherwise, it returns false.

Walkthrough

The algorithm begins by sorting the input array arr in ascending order of the absolute values of its elements. This is a crucial step because it establishes a consistent order for processing. This guarantees we always encounter x before 2x (in terms of magnitude), which simplifies the search for pairs.

We use a boolean array used to keep track of which elements have already been included in a pair. We iterate through the sorted array. For each element arr[i] that hasn't been used yet, we search for its double, target = 2 * arr[i], in the subsequent part of the array. The search for the target must also skip elements that are already used, so a simple linear scan from i + 1 is performed.

If a matching, unused target is found at index j, we mark both arr[i] and arr[j] as used and increment a counter for paired elements. If we successfully iterate through the entire array and the final count of paired elements equals the array's length, it means all elements were paired up, and we return true. Otherwise, we return false.

1class Solution {2    public boolean canReorderDoubled(int[] arr) {3        // Need to use Integer wrapper to sort with a custom comparator4        Integer[] integerArr = new Integer[arr.length];5        for (int i = 0; i < arr.length; i++) {6            integerArr[i] = arr[i];7        }8        Arrays.sort(integerArr, Comparator.comparingInt(Math::abs));9 10        boolean[] used = new boolean[arr.length];11        int pairedCount = 0;12 13        for (int i = 0; i < arr.length; i++) {14            if (used[i]) {15                continue;16            }17            // This is an unused element, try to find its double18            for (int j = i + 1; j < arr.length; j++) {19                if (!used[j] && integerArr[j] == 2 * integerArr[i]) {20                    used[i] = true;21                    used[j] = true;22                    pairedCount += 2;23                    break; // Found a pair, move to the next element in the outer loop24                }25            }26        }27 28        return pairedCount == arr.length;29    }30}

Complexity

Time

O(N^2), where N is the number of elements in the array. The initial sort takes O(N log N). The nested loops, however, result in a time complexity of O(N^2) in the worst case, as for each element, we might scan a large portion of the remaining array.

Space

O(N), where N is the number of elements in the array. This space is used for creating a copy of the array as `Integer[]` to allow custom sorting and for the `used` boolean array.

Trade-offs

Pros

The logic is straightforward and directly follows from the problem's pairing requirement after sorting.
It correctly handles positive, negative, and zero values due to sorting by absolute value.

Cons

The time complexity of O(N^2) is inefficient and will likely lead to a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
Requires extra O(N) space for the used array and for the copy of the array as Integer[].

Solutions

Solution

1class Solution {2public3  boolean canReorderDoubled(int[] arr) {4    Map<Integer, Integer> freq = new HashMap<>();5    for (int v : arr) {6      freq.put(v, freq.getOrDefault(v, 0) + 1);7    }8    if ((freq.getOrDefault(0, 0) & 1) != 0) {9      return false;10    }11    List<Integer> keys = new ArrayList<>(freq.keySet());12    keys.sort(Comparator.comparingInt(Math : : abs));13    for (int k : keys) {14      if (freq.getOrDefault(k << 1, 0) < freq.get(k)) {15        return false;16      }17      freq.put(k << 1, freq.getOrDefault(k << 1, 0) - freq.get(k));18    }19    return true;20  }21}

1class Solution {2public:3  bool canReorderDoubled(vector<int> &arr) {4    unordered_map<int, int> freq;5    for (int &v : arr)6      ++freq[v];7    if (freq[0] & 1)8      return false;9    vector<int> keys;10    for (auto &[k, _] : freq)11      keys.push_back(k);12    sort(keys.begin(), keys.end(),13         [](int a, int b) { return abs(a) < abs(b); });14    for (int &k : keys) {15      if (freq[k * 2] < freq[k])16        return false;17      freq[k * 2] -= freq[k];18    }19    return true;20  }21};

1class Solution:2    def canReorderDoubled(self, arr: List[int]) -> bool: freq = Counter(arr) if freq[0] & 1: return False for x in sorted(freq, key=abs): if freq[x << 1] < freq[x]: return False freq[x << 1] -= freq[x] 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.

← Previous

Previous problem

Next problem