2206. Divide Array Into Equal Pairs
Problem Description
You have an array named nums
with an even number of integers, precisely 2 * n
integers. Your objective is to determine if this array can be separated into n
pairs where each pair consists of two identical elements. Every element should be used exactly once and only in one pair. The challenge is to figure out if it's possible to create such pairs evenly across the entire array. If it can be done, you should return true
. If it's not possible and there's at least one element that can't form a pair with an identical counterpart, then the result should be false
.
Intuition
One way to approach this problem is to think about the conditions under which the array can be divided into n
pairs. Since we need to pair equal elements, a straightforward requirement is that each unique number must occur an even number of times—specifically 2 times since we're creating pairs. Should there be any number with an odd count, it would be impossible to form the required pairs.
Hence, arriving at the solution involves counting how many times each unique value appears in the array. This is known as creating a frequency count. We use the Counter
class from Python's collections
module to make this very easy. Once we have the counts, we check each of them to ensure they are all even (a number having a count that is a multiple of 2). If even one count is odd, it means there's at least one element that cannot form a pair and thus, we cannot divide the array as needed.
The solution is cleverly utilizing Python's all()
function combined with a generator expression. It iterates over each count value and checks if it's even (v % 2 == 0
). If all counts are even, all()
returns true
. If even one is not, it returns false
, succinctly giving us the answer we need.
Solution Approach
The solution makes use of a hash map to count the occurrences of each number in the input array nums
. In Python, this is conveniently accomplished using the Counter
class from the collections
module, which automatically creates a hash map (dictionary) where each key is a unique number from the array, and its value is the count of how many times it appears.
Here's a breakdown of the algorithm implemented in the provided solution:
-
Import the
Counter
fromcollections
to create the frequency count.cnt = Counter(nums)
will iterate overnums
, and for each element in the array, it will increment its corresponding count in thecnt
hash map. -
Next, we need to verify whether each number appears an even number of times. We use a generator expression
v % 2 == 0 for v in cnt.values()
for this. This expression goes through each value (which represents the count of occurrences for a number) in thecnt
hash map and checks if it is even. -
The
all()
function wraps the generator expression to check if all elements in the expression evaluate to true. For a countv
, ifv % 2 == 0
is true, thenv
is even. -
If all counts are even, then
all()
returnstrue
, meaning every element can be paired. If any count is odd, thenall()
returnsfalse
, meaning it's not possible to evenly divide the array into pairs.
The crux of the solution is to ensure two paired elements (which must be equal) are available for all the elements. If there's an odd number of any element, a pair cannot be formed, violating the problem's constraint.
The reference solution approach utilizes the Constant Time Operation property of the hash map which allows very efficient counting and retrieval operations, and the logical interpretation of the pair-formation rule (even number of elements) to arrive at a succinct and effective solution.
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 take the array nums = [1, 2, 1, 2, 1, 3, 3, 1]
for our example:
-
Initialization: We import the
Counter
class and initialize it with our array,nums
.Counter
tallies the counts of each distinct element, resulting in a hash map.from collections import Counter cnt = Counter(nums) # Counter({1: 4, 2: 2, 3: 2})
The resulting
cnt
dictionary contains keys that are the unique values fromnums
, with the counts as their respective values. -
Check Evenness: We create a generator expression to evaluate whether each count is even. The expression is
v % 2 == 0 for v in cnt.values()
, which in our case will generate the following sequence of booleans:[True, True, True] # every count is even: 4 % 2 == 0, 2 % 2 == 0, 3 % 2 == 0
Here,
v
refers to the count of each unique number in the array. SinceCounter({1: 4, 2: 2, 3: 2})
is our frequency map, the expression checks(4 % 2 == 0, 2 % 2 == 0, 2 % 2 == 0)
corresponding to counts for1
,2
, and3
respectively. -
Apply
all()
Function: Utilizing theall()
function, we confirm if every value in the generator expression isTrue
.can_pair = all(v % 2 == 0 for v in cnt.values()) # True
-
Result: The
all()
functioned returnedTrue
indicating that every count is even, which means that every unique number in the array appears an even number of times. Hence, it is possible to divide the array into pairs of identical elements.
Thus, in this case, the given array nums
can indeed be paired up in the manner described in the problem statement, and the function would return true
.
Solution Implementation
1from collections import Counter
2from typing import List
3
4class Solution:
5 def divideArray(self, nums: List[int]) -> bool:
6 # Create a counter dictionary to store the frequency of each number in the list
7 num_counter = Counter(nums)
8
9 # Use all() to check for each count in the counter values
10 # Return True if all counts are even, which means pairs can be formed for each unique number
11 # If there is any count that is not even, False is returned indicating pairs cannot be formed
12 return all(count % 2 == 0 for count in num_counter.values())
13
1class Solution {
2 // Function to check if it's possible to divide the array into pairs such that each pair contains equal numbers.
3 public boolean divideArray(int[] nums) {
4 // Create an array to count the frequency of elements.
5 // The maximum value for any element is considered to be 500, hence an array of size 510 is created for safe margin.
6 int[] count = new int[510];
7
8 // Iterate over the input array to count the frequency of each element.
9 for (int num : nums) {
10 // Increment the count of the current element.
11 count[num]++;
12 }
13
14 // Iterate over the frequency array to check if all elements have an even count.
15 for (int frequency : count) {
16 // If an element has an odd count, we cannot divide the array into pairs with equal numbers.
17 if (frequency % 2 != 0) {
18 return false; // Return false as soon as an odd frequency is found.
19 }
20 }
21
22 // If all elements have even counts, return true indicating that division into pairs is possible.
23 return true;
24 }
25}
26
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 bool divideArray(vector<int>& nums) {
7 // Create a frequency array with a fixed size,
8 // assuming that 500 is the maximum number expected to be in the `nums` array.
9 vector<int> frequency(501, 0); // Initialize all elements to 0
10
11 // Increment the frequency count for each number in the `nums` array.
12 for (int num : nums) {
13 frequency[num]++;
14 }
15
16 // Check if all numbers occur an even number of times.
17 for (int freq : frequency) {
18 // If a number occurs an odd number of times, it's not possible
19 // to divide the array into pairs such that each pair consists of equal numbers.
20 if (freq % 2 != 0) {
21 return false;
22 }
23 }
24
25 // If the code reaches this point, all numbers occur an even number of times,
26 // and the array can be divided into pairs of equal numbers.
27 return true;
28 }
29};
30
1// Define the function to check if an array can be divided into pairs with equal numbers.
2function divideArray(nums: number[]): boolean {
3 // Create a frequency array with a fixed size,
4 // assuming 500 is the maximum number expected to be in the `nums` array.
5 // Initialize all elements to 0.
6 const frequency: number[] = new Array(501).fill(0);
7
8 // Increment the frequency count for each number in the `nums` array.
9 for (const num of nums) {
10 frequency[num]++;
11 }
12
13 // Check if all numbers occur an even number of times.
14 for (const freq of frequency) {
15 // If a number occurs an odd number of times, it's not possible
16 // to divide the array into pairs such that each pair consists of equal numbers.
17 if (freq % 2 !== 0) {
18 return false;
19 }
20 }
21
22 // If the code reaches this point, all numbers occur an even number of times,
23 // and the array can be divided into pairs of equal numbers.
24 return true;
25}
26
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed as follows:
-
Creating the
Counter
object fromnums
involves iterating over alln
elements of the list to count the occurrences of each unique number. This step has a time complexity ofO(n)
. -
The
all
function then iterates over the values in the counter, which could be at mostn/2
if all numbers are unique and each appears exactly twice (which represents the case with the maximum possible number of keys). In the worst case, this will takeO(n/2)
which simplifies toO(n)
.
Combining these two steps, the overall time complexity remains O(n)
since constants are dropped in Big O notation.
Space Complexity
Analyzing the space complexity involves considering the extra space taken by the algorithm aside from the input:
-
The
Counter
object will store each unique number as a key and its frequency as a value. In the worst case, if all numbers are unique, the space required will beO(n)
. However, this is the worst-case scenario; in the best case, if all numbers are the same, the space complexity would beO(1)
. -
The
Counter
values are iterated in place using theall
function, which doesn't take additional significant space.
Hence, the worst-case space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
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
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!