Problem Explanation

Given an array of integers, we need to determine if it's possible to reorder the array such that for every 'i', A[2 * i + 1] = 2 * A[2 * i]. That means we need to pair the array elements such that one element is double of the other. Moreover, it's necessary and sufficient condition that every number x, there exists a number 2x in this array. We can solve this problem using a hash map and sorting.

Walkthrough of an Example

Take an example where the input array is [4, 2, 2, 8]. We need to check if it's possible to reorder the array in a way that for every 'i', A[2 * i + 1] = 2 * A[2 * i].

• First, we create a count map to count the occurrences of each element.
• After sorting the array, the array becomes [2, 2, 4, 8].
• Now start traversing the array, for each element 'a', check if the count of 'a' is not zero and the count of '2a' is greater than zero. If both are true, we decrease the count of 'a' and '2a' by one.
• If in any case, the count of '2a' becomes zero while the count of 'a' is not zero, we return false as we will not be able to reorder the array as per the given condition.
• Finally, if we are able to traverse the complete array without any conflicts, return true.

Approach

• Create a count map to count the occurrences of each element.
• Then sort the array in increasing order of absolute values of elements because for reordering, smaller numbers must come before twice bigger number.
• Start traversing the array, for each element 'a', check if the count[a] > 0 and count[2a] > 0, decrease the counts of 'a' and '2a' by one. Else, return false due to unmatched pair.
• If we can traverse the array without any conflicts, return true.

Python Solution

1
2python
3class Solution:
4    def canReorderDoubled(self, arr: List[int]) -> bool:
5        arr.sort(key = abs) 
6        hash_map = Counter(arr) 
7  
8        for number in arr:
9            if hash_map[number]==0:
10                continue
11            if hash_map[2*number] == 0:
12                return False
13            hash_map[2*number] -= 1
14            hash_map[number] -= 1
15        return True

Java Solution

1
2java
3class Solution {
4    public boolean canReorderDoubled(int[] A) {
5        Integer[] B = new Integer[A.length];
6        for (int i = 0; i < A.length; ++i)
7            B[i] = A[i];
8        Arrays.sort(B, Comparator.comparingInt(Math::abs));
9        Map<Integer, Integer> count = new HashMap<>();
10        for (int x: B)
11            count.put(x, count.getOrDefault(x, 0) + 1);
12        for (int x: B) {
13            if (count.get(x) == 0) continue;
14            if (count.getOrDefault(2*x, 0) <= 0) return false;
15            count.put(x, count.get(x) - 1);
16            count.put(2*x, count.get(2*x) - 1);
17        }
18        return true;
19    }
20}

JavaScript Solution

1
2javascript
3var canReorderDoubled = function(A) {
4    A.sort((a, b) => Math.abs(a) - Math.abs(b));
5    let map = new Map();
6    
7    for(let n of A) {
8        if(!map.has(n))
9            map.set(n, 0);
10        map.set(n, map.get(n) + 1);
11    }
12    
13    for(let n of A) {
14        if(map.get(n) === 0)
15            continue;
16        if(!map.has(2 * n) || map.get(2 * n) === 0)
17            return false;
18        map.set(n, map.get(n) - 1);
19        map.set(2 * n, map.get(2 * n) - 1);
20    }
21    
22    return true;
23};

C++ Solution

1
2c++
3class Solution {
4public:
5    bool canReorderDoubled(vector<int>& A) {
6        map<int, int, greater<int>> count;
7        for (int a : A)
8            count[abs(a)]++;
9        for (auto it : count)
10            if (count[it.first * 2] < it.second)
11                return false;
12            else
13                count[it.first * 2] -= it.second;
14        return true;
15    }
16};

C# Solution

1
2csharp
3public class Solution {
4    public bool CanReorderDoubled(int[] A) {
5        Array.Sort(A, (a, b) => Math.Abs(a) - Math.Abs(b));
6        Dictionary<int, int> counter = new Dictionary<int, int>();
7        for (int i = 0; i < A.Length; ++i) {
8            if (!counter.ContainsKey(A[i])) counter.Add(A[i], 0);
9            counter[A[i]]++;
10        }
11        for (int i = 0; i < A.Length; ++i) {
12            if (counter[A[i]] == 0) continue;
13            if (!counter.ContainsKey(2 * A[i]) || counter[2 * A[i]] <= 0) return false;
14            counter[A[i]]--;
15            counter[2 * A[i]]--;
16        }
17        return true;
18    }
19}

All these solutions are based on sorting the elements (in the order of their absolute values) and using a hash map or a dictionary to keep track of the count of each element.

In Python, Java, JavaScript, C++, and C#, we are sorting the array, then traversing the sorted array by checking if a number and its double have non-zero counts in the hash map. If such a pair is found, we decrease their counts by one. If we don’t find any such pair(i.e; the count of double of a number is zero), we return false. If we traverse the whole array without returning false means we can re-arrange the array as per the given condition, so in the end, we return true.

By following this approach, we make sure that we are always matching a number with its double that occurs in the array without violating the arrangement rule as we have sorted the array. Thus, this algorithm helps us determine if we can reorder the array for every 'i', such that A[2 * i + 1] = 2 * A[2 * i].

This problem is a successful combination of the Counting technique and the Two-Pointer technique. This approach has a time complexity of O(N log N) due to the sorting, and a space complexity of O(N) to store the counts of each number in the hash map.

Time Complexity: O(N log N), where N is the length of A.

Space Complexity: O(N) for storing counts.