Sponsored
Sponsored
Sort the array and use a map (or dictionary) to count the occurrences of each number. For each number in the sorted array, try to pair it with its double. If a number cannot be paired, return false. Handle zeroes separately as they need pairs to be zero as well.
Time Complexity: O(N log N), due to the sorting step. Space Complexity: O(N), needed for the Counter map.
1def canReorderDoubled(arr):
2 from collections import Counter
3 count = Counter(arr)
4 for x in sorted(arr, key=abs):
5 if count[x] == 0:
6 continue
7 if count[2 * x] <= 0:
8 return False
9 count[x] -= 1
10 count[2 * x] -= 1
11 return TrueThe function first counts the frequency of each integer in the array using Counter. It then sorts the array by the absolute values of its elements. For each element x in the sorted array, it checks if there's a corresponding 2 * x to make a valid pair. If not possible, it returns false. The function returns true if all elements can be paired appropriately.
Sort the array and use a two-pointer approach to try and form valid pairs. One pointer will start from the beginning and the other from the end or some valid position. Carefully manage cases with negative numbers and zero separately, since their pairing rules are distinct.
Time Complexity: O(N log N), due to sorting. Space Complexity: O(N), for storing counts in a map.
1function canReorderDoubled(arr) {
2 let count
This JavaScript solution uses a map for frequency counting and sorts the keys by their absolute values. It tries to match each value with double that value, reducing count accordingly, and returns false if a pair isn’t possible.