Problem

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.

Examples

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4

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

Example 3:

1
2
3
4
5

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].

Solution

This problem is similar to Find Original Array From Doubled Array.

Method 1 – Sorting and Frequency Map

Intuition

The main idea is to pair each number with its double. By sorting the array, we can always try to pair the smallest available number first, which helps handle negative numbers and zeros correctly. We use a frequency map to track how many times each number appears and greedily match each number with its double.

Approach

  1. Sort the array to process numbers in order, handling negatives and zeros properly.
  2. Use a frequency map to count occurrences of each number.
  3. For each number in the sorted array:
    • If its frequency is zero, skip it.
    • If its double’s frequency is zero, return false.
    • Otherwise, decrement the frequency of both the number and its double.
  4. If all numbers are paired successfully, return true.

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of arr, due to sorting and linear scan.
  • 🧺 Space complexity: O(n), for the frequency map.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        unordered_map<int, int> freq;
        for (int num : arr) freq[num]++;
        for (int num : arr) {
            if (freq[num] == 0) continue;
            if (freq[2 * num] == 0) return false;
            freq[num]--;
            freq[2 * num]--;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Arrays.sort(arr);
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) freq.put(num, freq.getOrDefault(num, 0) + 1);
        for (int num : arr) {
            if (freq.get(num) == 0) continue;
            if (freq.getOrDefault(2 * num, 0) == 0) return false;
            freq.put(num, freq.get(num) - 1);
            freq.put(2 * num, freq.get(2 * num) - 1);
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def canReorderDoubled(self, arr: list[int]) -> bool:
        arr.sort()
        freq = {}
        for num in arr:
            freq[num] = freq.get(num, 0) + 1
        for num in arr:
            if freq[num] == 0:
                continue
            if freq.get(2 * num, 0) == 0:
                return False
            freq[num] -= 1
            freq[2 * num] -= 1
        return True