Problem statement

https://leetcode.com/problems/array-of-doubled-pairs/

Solution

How to understand that you need to apply greedy strategy in some problem? It is a good question, and usually I try it after I see nothing else can work. In this specific problem it is quite easy to find greedy strategy. Let us think, we are given number x, what pair should we give to this number? It can be 2*x or x//2 (if x is even). So, we can not immedietly say, which pair we should choose? Is there any number such that it has only one pair? Yes, it is the number with smallest (or biggest) absolute value. For number with smallest absolute value x we can take as pair only x*2, no other choice. What is rest is to continue this process.

  1. We sort our number with key abs(x).
  2. Also we create cnt is Counter of all numbers: it can happen that we have some numbers several times.
  3. Iterate through sorted arr and if we see that frequency of some number is already 0: it can happen, because this number can be taken, we do nothing. If it is not zero, but we do not have pair 2*num, return False. Finally, we decreasy frequencies of two numbers: num and 2*num.

Complexity

It is O(n log n) to sort number and then O(n) to put them all into pairs, so overall time complexity is O(n log n). Space complexity is O(n).

Code

class Solution:
    def canReorderDoubled(self, arr):
        cnt = Counter(arr)
        for num in sorted(arr, key = lambda x: abs(x)):
            if cnt[num] == 0: continue
            if cnt[2*num] == 0: return False
            cnt[num] -= 1
            cnt[2*num] -= 1
        
        return True