[LeetCode] Array of Doubled Pairs

Problem: Given an array of integers arr of even length, return true if and only if it is possible to reorder it such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2.

Example:

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

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

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

Input: arr = [1,2,4,16,8,4]
Output: false

Constraints:

• 0 <= arr.length <= 3 * 104
• arr.length is even.
• -105 <= arr[i] <= 105

Approach: If you see closely the condition arr[2*i + 1] = 2 * arr[2 * i] is telling us that foreach i = 0, 2, 4, 6,......n-1; 2 * arr[i] should be equal to arr[i + 1]. This means we just need to find 2 * n (twice of n) for every number n of half of the array. 

We can use hashing to find 2*n efficiently.

Implementation in C#:

    public bool CanReorderDoubled(int[] arr) 

    {

        Dictionary<int, int> freqMap = new Dictionary<int, int>();

        foreach (int n in arr)

        {

            if (!freqMap.ContainsKey(n))

            {

                freqMap[n] = 0;

            }

            ++freqMap[n];

        }

        Array.Sort(arr, (n1, n2) => {

            return Math.Abs(n1).CompareTo(Math.Abs(n2));

        });            

        foreach (int n in arr)

        {

            if (!freqMap.ContainsKey(n))

            {

                continue;

            }

            --freqMap[n];

            if (freqMap[n] == 0)

            {

                freqMap.Remove(n);

            }

            if (!freqMap.ContainsKey(2 * n))

            {

                return false;

            }

            --freqMap[2 * n];

            if (freqMap[2 * n] == 0)

            {

                freqMap.Remove(2 * n);

            }

        }

        return freqMap.Count == 0;

    }

Complexity: O(nlogn)