2206. Divide Array Into Equal Pairs

EasyBit ManipulationArrayHash TableCounting

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 from collections to create the frequency count. cnt = Counter(nums) will iterate over nums, and for each element in the array, it will increment its corresponding count in the cnt 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 the cnt 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 count v, if v % 2 == 0 is true, then v is even.
If all counts are even, then all() returns true, meaning every element can be paired. If any count is odd, then all() returns false, 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 Evaluator

Example 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 from nums, 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. Since Counter({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 for 1, 2, and 3 respectively.

Apply all() Function: Utilizing the all() function, we confirm if every value in the generator expression is True.

can_pair = all(v % 2 == 0 for v in cnt.values())  # True

Result: The all() functioned returned True 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 from nums involves iterating over all n elements of the list to count the occurrences of each unique number. This step has a time complexity of O(n).
The all function then iterates over the values in the counter, which could be at most n/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 take O(n/2) which simplifies to O(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 be O(n). However, this is the worst-case scenario; in the best case, if all numbers are the same, the space complexity would be O(1).
The Counter values are iterated in place using the all 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointers

Two pointers moving in opposite direction

Sliding window

Prefix sum

I don’t know