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 * 104arr.length is even.-105 <= arr[i] <= 105Sort the array and use a map (or dictionary) to count the occurrences of each number. For each number in the sorted array, try to pair it with its double. If a number cannot be paired, return false. Handle zeroes separately as they need pairs to be zero as well.
The function first counts the frequency of each integer in the array using Counter. It then sorts the array by the absolute values of its elements. For each element x in the sorted array, it checks if there's a corresponding 2 * x to make a valid pair. If not possible, it returns false. The function returns true if all elements can be paired appropriately.
Java
Time Complexity: O(N log N), due to the sorting step. Space Complexity: O(N), needed for the Counter map.
Sort the array and use a two-pointer approach to try and form valid pairs. One pointer will start from the beginning and the other from the end or some valid position. Carefully manage cases with negative numbers and zero separately, since their pairing rules are distinct.
This JavaScript solution uses a map for frequency counting and sorts the keys by their absolute values. It tries to match each value with double that value, reducing count accordingly, and returns false if a pair isn’t possible.
C#
Time Complexity: O(N log N), due to sorting. Space Complexity: O(N), for storing counts in a map.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Counting | Time Complexity: O(N log N), due to the sorting step. Space Complexity: O(N), needed for the Counter map. |
| Approach 2: Two-pointer Technique | Time Complexity: O(N log N), due to sorting. Space Complexity: O(N), for storing counts in a map. |
LeetCode 954. Array of Doubled Pairs - Interview Prep Ep 77 • Fisher Coder • 3,122 views views
Watch 9 more video solutions →Practice Array of Doubled Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor