[LeetCode] 2206. Divide Array Into Equal Pairs

Problem

https://leetcode.com/problems/house-robber-iv/description

Leetcode - Divide Array Into Equal Pairs

Type - Hash

Difficulty - Easy

Approach & Solution

Data Structures and Variables

• mp: map for counting frequency of each number.

Algorithm:

1. As we iterate through the nums, we increment the frequency of num[i] by 1.

2. If any key in the map has an odd frequency, return false.

3. Otherwise, return true.

Complexity

• Time Complexity: O(n)

  • Since we traverse nums only once.

• Space Complexity: O(n)

  • In worst case, the size of map can be n, which is the size of nums.

Code (C++ | Go)

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    bool divideArray(vector<int>& nums) {
        unordered_map<int, int> mp;
        for(const auto &num : nums) {
            mp[num]++;
        }

        for(const auto &[k, v] : mp) {
            if(v%2 == 1) return false;
        }

        return true;
    }
};

func divideArray(nums []int) bool {
    mp := make(map[int]int)
    for _, num := range nums {
        mp[num]++
    }

    for _, v := range mp {
        if v%2 == 1{
            return false 
        }
    }
    return true
}