954. Array of Doubled Pairs
Problem Description
Given an array arr
of integers of even length, the task is to find out whether it is possible to rearrange the array such that, for every number arr[2*i]
, there exists a corresponding number arr[2*i + 1]
which is double the value of arr[2*i]
. This condition must hold true for all values of i
that range from 0
to len(arr) / 2 - 1
. If such a reordering is possible, return true
; otherwise, return false
.
Intuition
The intuition behind the solution involves understanding that each element must have a counterpart that is exactly double its value. One effective way to approach this problem is to count the frequency of each element in the array using a hashmap or counter, which provides O(1) lookup time to check for the existence of the double value.
Sorting the keys of this hashmap by their absolute value helps deal with both positive and negative numbers equally because the counterpart should be 2 times that number regardless of its sign. Starting with the smallest absolute value ensures that if we find a match (i.e., a number that is double the current number), we can be sure that we haven't erroneously attempted to match it with a number too large or too small.
The core idea of this solution is that for every key x
, there should be at least as many numbers 2*x
as there are x
since we want to pair each x
with a 2*x
. If at any point, the frequency of 2*x
is lower than the frequency of x
, then it is impossible to pair all x
ās with their corresponding double values, and therefore, the function should return false. If we successfully pair all elements, then we return true.
However, keep in mind that the case for 0
is special since it must be paired with itself. Hence if there is an odd number of zeros, it is not possible to pair them all up and we should return false right away.
Solution Approach
-
First, count the occurrence (frequency) of each element in the array using the
Counter
class from Python'scollections
module. -
Check the special case for
0
. If there is an odd number of0
s, return false because you cannot pair all0
s with double their value. -
Sort the keys of the frequency counter by the absolute value to ensure proper pairing regardless of the signs of the numbers.
-
Iterate through each number
x
in the sorted keys:a. Check if there are fewer numbers at
2*x
thanx
. If so, return falseāwhile attempting to pair numbers, we have encountered more of a number than its pair.b. Decrease the frequency of
2*x
by the frequency ofx
to "pair up" thex
values with2*x
values. -
If we successfully iterate over all numbers without returning false, it means we can pair all numbers with their doubles, so we return true.
Solution Approach
The solution leverages the Counter
class from Python's collections
module to create a frequency table to keep track of the occurrences of each element. This approach is efficient because it provides constant-time (O(1)
) access to each element's count, a crucial feature for the solution's performance.
-
Initialize the frequency counter for the array elements:
1freq = Counter(arr)
-
Special case handling for
0
:1if freq[0] & 1: 2 return False
Here, we're using the bitwise AND operator
&
to check if the number of zeros is odd. If it's odd, it's not possible to pair0
with double its value (also0
), so we returnFalse
. -
Sort the keys of the frequency counter by their absolute value:
1for x in sorted(freq, key=abs):
The keys are sorted in ascending order of their absolute value, which allows us to iterate from the smallest to the largest by considering their magnitude. This is essential to handle negative numbers correctly.
-
Iterate through each sorted key and try to pair it with its double:
1if freq[x << 1] < freq[x]: 2 return False 3freq[x << 1] -= freq[x]
First, we check if the frequency of the double of
x
(achieved by left-shiftingx
orx << 1
, which is equivalent to2 * x
) is less than the frequency ofx
. If it is, we can't pair allx
with2 * x
, hence we returnFalse
.If the condition passes, we reduce the frequency of
2 * x
by the frequency ofx
. This effectively pairs up thex
's and the2 * x
's. -
If all pairs are successfully matched, the function returns
True
:1return True
The key principle in this approach is the management of the frequency counter and ensuring that for every element x
with a non-zero count, there is a sufficient count of elements 2 * x
to match with. Sorting by absolute value ensures that we pair elements starting from the smallest magnitude, making it impossible to create invalid pairings with elements that already should have been paired with smaller numbers.
The algorithm's time complexity primarily depends on the sorting procedure, which operates in O(n log n)
time, where n
is the length of the array. The subsequent iteration has a linear run time concerning the number of unique elements. The space complexity depends on the number of unique elements as well, which determines the size of the frequency counter.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach:
Given the input array arr = [4, 8, 1, 2, 3, 6]
, we need to check if it can be rearranged so that for every number at arr[2*i]
, there is a number at arr[2*i + 1]
that is double its value.
-
First, we count the frequency of each element:
1freq = {4: 1, 8: 1, 1: 1, 2: 1, 3: 1, 6: 1}
-
There are no zeros in this example, so we don't need to worry about the special case for
0
. -
We sort the keys of the frequency counter by absolute value to get the numbers in the correct pairing order:
1sorted keys by absolute value = [1, 2, 3, 4, 6, 8]
-
Now, we iterate through these sorted keys, checking and pairing each number with its double:
-
For
1
, there is a corresponding2
(double of1
), so we pair them up and reduce the frequency of2
by the frequency of1
:1freq = {4: 1, 8: 1, 1: 0, 2: 0, 3: 1, 6: 1}
-
Next, we have
3
, and its double6
is also available. We pair them and adjust the frequencies:1freq = {4: 1, 8: 1, 1: 0, 2: 0, 3: 0, 6: 0}
-
Finally, we pair
4
with8
:1freq = {4: 0, 8: 0, 1: 0, 2: 0, 3: 0, 6: 0}
-
-
All elements have been successfully paired with their doubles, so we return
True
If, at any point during the iteration, the frequency of the current element's double was insufficient to pair with every instance of the current element, we would return False
. However, in this example, the pairing is successful, so the given array meets the conditions defined in the problem.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def canReorderDoubled(self, arr: List[int]) -> bool:
5 # Create a frequency counter for elements in the array
6 element_frequency = Counter(arr)
7
8 # If the frequency of 0 is odd, pairs of twice 0 can't be formed
9 if element_frequency[0] % 2 != 0:
10 return False
11
12 # Sort the unique elements by their absolute values
13 for element in sorted(element_frequency, key=abs):
14 # The number of times the double of this element should be
15 # at least the number of times the element itself occurs
16 if element_frequency[element * 2] < element_frequency[element]:
17 return False
18 # Decrement the frequency of the double element
19 element_frequency[element * 2] -= element_frequency[element]
20
21 # If all elements can be paired with their doubles, return True
22 return True
23
1class Solution {
2
3 public boolean canReorderDoubled(int[] arr) {
4 // Create a frequency map to count occurrences of each number in the array
5 Map<Integer, Integer> frequencyMap = new HashMap<>();
6 for (int number : arr) {
7 frequencyMap.put(number, frequencyMap.getOrDefault(number, 0) + 1);
8 }
9
10 // If there's an odd number of zeroes, it's not possible to reorder as per the rules
11 if ((frequencyMap.getOrDefault(0, 0) & 1) != 0) {
12 return false;
13 }
14
15 // Create a list of unique keys (numbers) from the map and sort them by their absolute values
16 List<Integer> keys = new ArrayList<>(frequencyMap.keySet());
17 keys.sort(Comparator.comparingInt(Math::abs));
18
19 // Iterate through the keys
20 for (int key : keys) {
21 // If the frequency of the double is less than the frequency of the current key, return false
22 if (frequencyMap.getOrDefault(key * 2, 0) < frequencyMap.get(key)) {
23 return false;
24 }
25 // Decrease the frequency of the doubled number by the frequency of the current key
26 frequencyMap.put(key * 2, frequencyMap.getOrDefault(key * 2, 0) - frequencyMap.get(key));
27 }
28
29 // If the loop completes without returning false, reordering is possible
30 return true;
31 }
32}
33
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7 // Function to determine if it is possible to reorder the array such that
8 // for every element x in the array, there exists another element 2 * x as well.
9 bool canReorderDoubled(std::vector<int>& arr) {
10 // Create a frequency map for all elements in the array.
11 std::unordered_map<int, int> frequency_map;
12 for (int value : arr) {
13 ++frequency_map[value];
14 }
15
16 // If there's an odd number of zeros, it's not possible to pair all of them,
17 // hence we can return false immediately.
18 if (frequency_map[0] % 2 != 0) return false;
19
20 // Extract keys from the frequency map to sort them based on their absolute values.
21 std::vector<int> keys;
22 for (const auto& element : frequency_map) {
23 keys.push_back(element.first);
24 }
25
26 // Sorting the keys based on the absolute values of the elements.
27 std::sort(keys.begin(), keys.end(), [](int a, int b) {
28 return std::abs(a) < std::abs(b);
29 });
30
31 // Iterate over the sorted keys.
32 for (int key : keys) {
33 // If there are not enough double elements to pair with the current element,
34 // it's not possible to reorder the array as required.
35 if (frequency_map[key * 2] < frequency_map[key]) return false;
36
37 // Decrement the count of the pair element by the frequency of the current element.
38 frequency_map[key * 2] -= frequency_map[key];
39 }
40
41 // If all elements can be paired successfully, return true.
42 return true;
43 }
44};
45
1// Import necessary functions from the "lodash" library.
2import { sortBy, countBy } from "lodash";
3
4// Function to determine if it is possible to reorder the array such that
5// for every element x in the array, there exists another element 2 * x as well.
6function canReorderDoubled(arr: number[]): boolean {
7 // Create a frequency map for all elements in the array using the countBy function.
8 const frequencyMap: Record<number, number> = countBy(arr);
9
10 // If there's an odd number of zeros, it's not possible to pair all of them,
11 // hence we can return false immediately.
12 if (frequencyMap[0] % 2 !== 0) return false;
13
14 // Extract keys from the frequency map and sort them based on their absolute values.
15 const keys: number[] = Object.keys(frequencyMap).map(Number);
16 const sortedKeys: number[] = sortBy(keys, Math.abs);
17
18 // Iterate over the sorted keys.
19 for (const key of sortedKeys) {
20 // If there are not enough double elements to pair with the current element,
21 // it's not possible to reorder the array as required.
22 if ((frequencyMap[key * 2] || 0) < frequencyMap[key]) return false;
23
24 // Decrement the count of the pair element by the frequency of the current element.
25 frequencyMap[key * 2] = (frequencyMap[key * 2] || 0) - frequencyMap[key];
26 }
27
28 // If all elements can be paired successfully, return true.
29 return true;
30}
31
Time and Space Complexity
Time Complexity
The time complexity of the given code can be broken down into several parts:
-
Counter Creation: The
Counter
creation from thearr
list runs inO(n)
time, wheren
is the length ofarr
, as it needs to iterate through the list once to count the frequency of each element. -
Sorting: The
sorted
function sorts the keys of the frequency counter. Sorting is typicallyO(n log n)
. In this case, itās sorting based on the absolute values, but this doesn't change the time complexity. -
Iterating through Sorted Keys: The for-loop iterates through each unique value in
arr
(after it's been sorted), which in the worst case can beO(n)
when all elements are unique. However, for each element, it's only doing a constant amount of work by adjusting the frequency of the doubled element. Therefore, this step isO(n)
.
Combining these, the sorting step dominates the time complexity, leading to an overall time complexity of O(n log n)
.
Space Complexity
The space complexity of the given code is as follows:
-
Counter: A Counter is created to store the frequency of each element in
arr
. In the worst case, if all elements are unique, it requiresO(n)
space. -
Sorted List: The
sorted
function returns a new list containing the sorted keys, which also requiresO(n)
space in the worst case if all elements are unique.
However, the space used by the new sorted list does not add to the space complexity because it's not allocating additional space that grows with the input size; it's dependent on the number of unique elements which is already accounted for by the Counter. So the overall space complexity remains O(n)
.
Therefore, the final space complexity is also O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we