Even Frequency of Array using Sort or Hash Map

Given a list of integers nums, return whether all numbers appear an even number of times.

Constraints
n ≤ 100,000 where n is the length of nums

Example 1
Input
nums = [2, 4, 4, 2, 3, 3]
Output
true
Explanation
Every number occurs twice.

Example 2
Input
nums = [1]
Output
false
Explanation
1 occurs an odd number of times.

Sort and Compare

We can sort the array in O(NLogN) and then we compare two elements (neighbour) at a time which must be equal. Also, the array size needs to be even.

1
2
3
4
5
6
7

bool sortAndCompareEven(vector<int>& nums) {
    sort(begin(nums), end(nums));
    for (int i = 0; i + 1 < nums.size(); i += 2) {
        if (nums[i] != nums[i + 1]) return false;
    }
    return (nums.size() & 1) == 0;
}

bool sortAndCompareEven(vector<int>& nums) {
    sort(begin(nums), end(nums));
    for (int i = 0; i + 1 < nums.size(); i += 2) {
        if (nums[i] != nums[i + 1]) return false;
    }
    return (nums.size() & 1) == 0;
}

The complexity is O(NLogN).

Using Hash Map to Store Frequency of Characters

To improve the runtime, we can use a hash map to store the character frqeuencies and then we just need to iterate over the map to check the frequencies.

1
2
3
4
5
6
7
8

bool evenFrequency(vector<int>& nums) {
    unordered_map<int, int> data;
    for (auto &n: nums) data[n] ++;
    for (auto &[num, freq]: data) {
        if (freq & 1) return false;
    }
    return true;
}

bool evenFrequency(vector<int>& nums) {
    unordered_map<int, int> data;
    for (auto &n: nums) data[n] ++;
    for (auto &[num, freq]: data) {
        if (freq & 1) return false;
    }
    return true;
}

The space requirement is O(N).

–EOF (The Ultimate Computing & Technology Blog) —