Solution Explanation: Divide Array Into Equal Pairs

The problem asks whether an array of even length can be divided into pairs where each pair consists of two identical numbers. The solution hinges on the observation that this is possible if and only if every unique number in the array appears an even number of times.

Approach: Counting Occurrences

We can solve this efficiently by counting the occurrences of each number. If every number has an even count, then the array can be divided into equal pairs; otherwise, it cannot.

Algorithm

1. Count Occurrences: Use a hash map (or a simple array if the input numbers are within a known range) to count the occurrences of each number in the input array nums. For this problem, because the input numbers are constrained to be between 1 and 500, a simple array cnt of size 510 is sufficient and more efficient than a HashMap.

2. Check Even Counts: Iterate through the counts. If any count is odd, it means that number cannot be paired, so we return false.

3. Return True: If the loop completes without finding any odd counts, it means all numbers have even counts, and we return true.

Time and Space Complexity

• Time Complexity: O(N), where N is the length of the input array nums. This is because we iterate through the array once to count occurrences and then iterate through the counts (which is at most 500 in this case, a constant).

• Space Complexity: O(1). While we use a cnt array, its size is constant (510) and does not depend on the input size N. Using a HashMap would lead to O(M) space complexity, where M is the number of unique numbers in the input array. Since M <= N, it remains linear with respect to the input but is less efficient than a simple array for this problem.

Code Implementations

The code implementations below reflect the algorithm described above. They use different programming languages but share the same core logic.

Python

from collections import Counter
 
class Solution:
    def divideArray(self, nums: list[int]) -> bool:
        counts = Counter(nums)
        return all(count % 2 == 0 for count in counts.values())
 

Java

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public boolean divideArray(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        for (int count : counts.values()) {
            if (count % 2 != 0) {
                return false;
            }
        }
        return true;
    }
}

C++

#include <vector>
#include <map>
 
using namespace std;
 
class Solution {
public:
    bool divideArray(vector<int>& nums) {
        map<int, int> counts;
        for (int num : nums) {
            counts[num]++;
        }
        for (auto const& [key, val] : counts) {
            if (val % 2 != 0) {
                return false;
            }
        }
        return true;
    }
};

Javascript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var divideArray = function(nums) {
    const counts = {};
    for (const num of nums) {
        counts[num] = (counts[num] || 0) + 1;
    }
    for (const count of Object.values(counts)) {
        if (count % 2 !== 0) {
            return false;
        }
    }
    return true;
};

These examples demonstrate the efficient counting approach. The use of a Counter in Python and similar data structures in other languages simplifies the process of counting occurrences. Remember that for this specific problem, given the constraints on the input values, using a fixed-size array is even more efficient than a HashMap or similar dynamic data structure.