# Divide Array Into Equal Pairs
**Difficulty:** EASY
[External](https://leetcode.com/problems/divide-array-into-equal-pairs)
Canonical: https://scaleengineer.com/dsa/problems/divide-array-into-equal-pairs
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
You are given an integer array `nums` consisting of `2 * n` integers.

You need to divide `nums` into `n` pairs such that:

* Each element belongs to **exactly one** pair.
* The elements present in a pair are **equal**.

Return `true` _if nums can be divided into_ `n` _pairs, otherwise return_ `false`.

**Example 1:**

**Input:** nums = [3,2,3,2,2,2]
**Output:** true
**Explanation:** 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

**Example 2:**

**Input:** nums = [1,2,3,4]
**Output:** false
**Explanation:** 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

**Constraints:**

* `nums.length == 2 * n`
* `1 <= n <= 500`
* `1 <= nums[i] <= 500`

# Approaches
## Sorting the Array
This approach relies on the idea that if an array can be divided into pairs of equal elements, then after sorting the array, all equal elements will be adjacent. We can then iterate through the sorted array and check if every pair of adjacent elements at even-starting indices `(2*i, 2*i + 1)` are identical.
**Time:** O(N log N), where N is the number of elements in `nums`. The sorting operation is the bottleneck. The subsequent loop to check pairs runs in O(N) time. · **Space:** O(log N) to O(N). The space complexity depends on the sorting algorithm's implementation. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which requires `O(log N)` space on average for the recursion stack.
**Pros:** The logic is straightforward and easy to understand.; It can be implemented with minimal extra space, depending on the sorting algorithm used.
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than other approaches for this problem.
### Explanation
The first step is to sort the input array `nums`. This operation groups all identical elements together. For example, `[3,2,3,2,2,2]` becomes `[2,2,2,2,3,3]`. After sorting, if the array can indeed be partitioned into `n` pairs of equal values, then for every even index `i`, the element `nums[i]` must be equal to the element `nums[i+1]`. We can verify this by iterating through the sorted array with a step of 2. We compare `nums[i]` and `nums[i+1]` in each step. If we find any pair that is not equal, we can conclude that the array cannot be divided as required and return `false`. If the entire loop finishes without finding any such unequal pairs, it confirms that the array can be successfully divided, and we return `true`.

```java
import java.util.Arrays;

class Solution {
    public boolean divideArray(int[] nums) {
        // The array has 2 * n elements. If n=0, nums is empty, which is trivially true.
        if (nums.length == 0) {
            return true;
        }
        
        // Sort the array to group equal elements together.
        Arrays.sort(nums);
        
        // Iterate through the array, checking pairs of elements.
        for (int i = 0; i < nums.length; i += 2) {
            // If a pair of adjacent elements is not equal, it's impossible to form equal pairs.
            if (nums[i] != nums[i+1]) {
                return false;
            }
        }
        
        // If all pairs are equal, the condition is satisfied.
        return true;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Iterate through the sorted array with a step of 2, starting from index 0.
- In each iteration, compare the element at the current index `i` with the element at `i+1`.
- If `nums[i]` is not equal to `nums[i+1]`, it's impossible to form a pair, so return `false`.
- If the loop completes without finding any unequal adjacent pairs, it means all elements can be paired up. Return `true`.

## Tracking Pairs with a Hash Set
This approach uses a hash set to dynamically track elements that need a pair. When we encounter a number, we check if it's already in our set of 'unpaired' elements. If it is, we've found a pair, so we remove it. If it's not, we add it to the set, waiting for its partner. If all elements are paired up by the end, the set will be empty.
**Time:** O(N), where N is the number of elements in `nums`. We iterate through the array once, and each hash set operation (add, remove, contains) takes O(1) average time. · **Space:** O(K), where K is the number of unique elements in the array. In the worst case, where pairs are like `(a,a), (b,b), ...`, the set size can grow up to `N/2` before shrinking. So, the space is proportional to the number of pairs, which is `O(N)`.
**Pros:** Achieves a linear time complexity, which is more efficient than the sorting approach.; Requires only a single pass over the input array.
**Cons:** Requires extra space for the hash set, which can be up to O(N/2) in the worst-case scenario.
### Explanation
The core idea is to use a `HashSet` to keep track of elements for which we have not yet found a matching pair. We iterate through the `nums` array one element at a time. For each element `num`, we check if it is already present in the set. If `set.contains(num)` is true, it signifies we have found the second element of a pair, so we remove `num` from the set. If `num` is not in the set, it's the first element of a potential pair, so we add it to the set. After iterating through the entire `nums` array, if the set is empty, it means every element found its match, and the array can be divided into equal pairs. If the set is not empty, it contains the elements that were left over without a pair. In this case, the condition is not met. A slightly more concise implementation can use the boolean return value of the `add` method.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean divideArray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            // If num is already in the set, remove it.
            if (set.contains(num)) {
                set.remove(num);
            } else {
                // Otherwise, add it to the set.
                set.add(num);
            }
        }
        // If the set is empty, all numbers formed a pair.
        return set.isEmpty();
    }
}
```
### Algorithm
- Initialize an empty `HashSet` to store elements that are waiting for a pair.
- Iterate through each number `num` in the input array `nums`.
- For each `num`, attempt to add it to the set. The `add` method of a `HashSet` returns `false` if the element is already present.
- If `add(num)` returns `false`, it means we've found a match for a previously seen `num`. We then remove `num` from the set to complete the pair.
- After iterating through all numbers, check if the set is empty.
- If the set is empty, all elements were successfully paired. Return `true`.
- Otherwise, there are unpaired elements left in the set. Return `false`.

## Frequency Counting with an Array
The most efficient approach is based on a simple logical condition: an array can be divided into pairs of equal elements if and only if every distinct number in the array appears an even number of times. This method counts the occurrences of each number and then verifies this condition. Given the problem's constraints on the values of the numbers, we can use a simple array for frequency counting, which is highly efficient.
**Time:** O(N + M), where N is the length of `nums` and M is the range of values (500). Since M is a constant, the complexity simplifies to O(N). · **Space:** O(1). Since the range of values in `nums` is fixed (1 to 500), the size of the `counts` array is constant (501) and does not depend on the size of the input array `N`.
**Pros:** Optimal time complexity of O(N).; Optimal constant space complexity, O(1), due to the fixed range of input values.; Very efficient in practice as array access is faster than hashing.
**Cons:** This specific implementation is highly optimized for the given constraints on the element values. If the range of numbers were much larger or unbounded, a `HashMap` would be needed, which would increase the space complexity.
### Explanation
This approach directly tackles the core requirement. For the array to be divisible into pairs of equal numbers, every unique number must have an even frequency. If a number appears an odd number of times, one instance of it will be left over without a pair. We can verify this by counting the frequency of each number. Since the constraints state that `1 <= nums[i] <= 500`, we can use a fixed-size integer array of size 501 as a frequency map. We iterate through the input `nums` array, and for each number, we increment its corresponding index in our frequency array. After this single pass, we have the counts of all numbers. Then, we iterate through our frequency array. If we find any count that is not divisible by 2, we know it's impossible to form the pairs, so we return `false`. If all counts are even, we return `true`.

```java
class Solution {
    public boolean divideArray(int[] nums) {
        // Constraints: 1 <= nums[i] <= 500
        int[] counts = new int[501];
        
        // Count the frequency of each number.
        for (int num : nums) {
            counts[num]++;
        }
        
        // Check if any number has an odd frequency.
        for (int count : counts) {
            if (count % 2 != 0) {
                return false;
            }
        }
        
        // If all frequencies are even, it's possible.
        return true;
    }
}
```
### Algorithm
- Create an integer array `counts` of size 501 (since `1 <= nums[i] <= 500`), initialized to all zeros.
- Iterate through each number `num` in the input array `nums`.
- For each `num`, increment its frequency in the `counts` array: `counts[num]++`.
- After counting, iterate through the `counts` array.
- For each `count` in the array, check if it is odd (`count % 2 != 0`).
- If any count is odd, return `false` immediately.
- If the loop completes without finding any odd counts, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean divideArray(int[] nums) {
    int[] cnt = new int[510];
    for (int v : nums) {
      ++cnt[v];
    }
    for (int v : cnt) {
      if (v % 2 != 0) {
        return false;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {boolean} */ var divideArray = function (
  nums,
) {
  const cnt = {};
  for (const x of nums) {
    cnt[x] = (cnt[x] || 0) + 1;
  }
  return Object.values(cnt).every((x) => x % 2 === 0);
};

```

### Python

```python
class Solution:
    def divideArray(self, nums: List[int]) -> bool: cnt = Counter(nums) return all(v % 2 == 0 for v in cnt . values())

```

### CPP

```cpp
class Solution {
public:
  bool divideArray(vector<int> &nums) {
    vector<int> cnt(510);
    for (int &v : nums)
      ++cnt[v];
    for (int &v : cnt)
      if (v % 2)
        return false;
    return true;
  }
};

```