954

954. Array of Doubled Pairs (Medium)

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 * 104
• arr.length is even.
• -105 <= arr[i] <= 105

Companies:
Google

Related Topics:
Array, Hash Table, Greedy, Sorting

Similar Questions:

• Find Original Array From Doubled Array (Medium)

Solution 1. Greedy

// OJ: https://leetcode.com/problems/array-of-doubled-pairs/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        multiset<int> s(A.begin(), A.end());
        while (s.size()) {
            int val = *s.begin();
            if (val < 0 && val % 2) return false;
            int next = val >= 0 ? val * 2 : val / 2;
            s.erase(s.begin());
            auto it = s.find(next);
            if (it == s.end()) return false;
            s.erase(it);
        }
        return true;
    }
};

Solution 2. Frequency Map

// OJ: https://leetcode.com/problems/array-of-doubled-pairs/
// Author: github.com/lzl124631x
// Time: O(N + KlogK) where `K` is the number of unique elements in `A`.
// Space: O(K)
class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        unordered_map<int, int> m;
        for (int n : A) m[n]++;
        vector<int> nums;
        for (auto [n, cnt] : m) nums.push_back(n);
        sort(begin(nums), end(nums), [&](int a, int b) { return abs(a) < abs(b); });
        for (int n : nums) {
            if (m[2 * n] < m[n]) return false;
            m[2 * n] -= m[n];
        }
        return true;
    }
};