991. Array Of Doubled Pairs¶

Difficulty: Medium

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

Constraints:

2 <= arr.length <= 3 * 10⁴
arr.length is even.
-10⁵ <= arr[i] <= 10⁵

Solution¶

class Solution {
    public boolean canReorderDoubled(int[] arr) {
        int n = arr.length;
        Arrays.sort(arr);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int ele : arr) map.put(ele, map.getOrDefault(ele, 0) + 1);
        for (int ele : arr) {
            if (map.getOrDefault(ele, 0) == 0) continue;
            if (ele < 0 && ele % 2 != 0) return false;
            int y = 0;
            if (ele > 0) y = 2 * ele;
            else y = ele / 2;
            if (map.getOrDefault(y, 0) == 0) return false;
            map.put(ele, map.getOrDefault(ele, 0) -1);
            map.put(y, map.getOrDefault(y, 0) -1);
        }
        return true;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here