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].
Example 4:
Input: arr = [1,2,4,16,8,4] Output: false
Constraints:
2 <= arr.length <= 3 * 10^4arr.length is even.-105 <= arr[i] <= 10^5
The description was taken from https://leetcode.com/problems/array-of-doubled-pairs/.
#O(N(Log(N))) Time, O(N) Space
class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
count = {}
for num in arr:
if num not in count:
count[num] = 1
else:
count[num] += 1
for num in sorted(arr, key = abs):
if not count[num]:
continue
if num * 2 not in count or not count[num * 2]:
return False
count[num] -= 1
count[num * 2] -= 1 return TrueIn this problem, a number can either be multiplied by two to equal its pair partner, or it can be divided by two to equal its pair partner.
If we had a number that could be paired with a division partner, but it could also be paired with a multiplication partner, how would we choose which number to pair it with?
That is where we may consider a greedy approach, an approach where we sort our input and take care of the cheapest tasks to conserve the most resources. In this case, our resources are numbers to pair.
If we are implementing an algorithm that requires knowing where other numbers are within input or if they exist, that is usually a given that a HashMap should be utilized.
What we can do is place each number and their frequency into a HashMap and then sort the array by absolute values, since we can have negative numbers.
From there, all we need to do is pick a multiplication partner and won't have to worry about a division partner.
We will traverse the array and for each number, we will see if its partner exists by multiplying it by two and referencing the hashmap. After we pair the numbers we will just decrement their frequencies in the HashMap to simulate the pairing.
Let's start by initializing our HashMap which we will use to count the frequency of each number.
count = {}
For each number in the array, if the number isn't already in the HashMap, we will place it there with an initial value of one.
Otherwise, we will increment its frequency.
for num in arr:
if num not in count:
count[num] = 1
else:
count[num] += 1
Then, we will traverse the input array, sorted by absolute values.
for num in sorted(arr, key = abs):
If the current number has been decremented to zero within the input array, then we have already paired this number so we will continue.
if not count[num]:
continue
If the current number multiplied by two is not in the HashMap, then we can't pair this number so we will return false. We will also return false if the number is there, but has already been paired with a different number and can't be paired with the current one.
if num * 2 not in count or not count[num * 2]:
return False
Otherwise, we will pair these two numbers.
count[num] -= 1
count[num * 2] -= 1
If we have traversed the array and never returned false, that means we were able to pair each number so we will return true.
return True