🗓️Day 05 – Hashmap
Topics: Hashmap
Problem solved:
#242 - Valid Anagram
#349 - Intersection of two arrays
#202 - Happy Number

📚Concept Review – Something about Hashmap

A Hashmap is a mapping structure from key to value, which uses a hash function to convert the key into array index, achieving:

• Average O(1) time for look up
• Average O(1) time for insertion
• Average O(1) time for deletion

---

🧩Problem solution – 242. Valid Anagram

link

💡Problem description

Given two strings s and t, return true if t is an anagram of s, and false otherwise.
(An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.)
For example, Tom Marvolo Riddle ->I am Lord Voldemort

Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true

Example 2:
Input: s = “rat”, t = “car”
Output: false

Constraints:

1 <= s.length, t.length <= 5 * 10 ⁴
s and tconsist of lowercase English letters.

🧭Thought Process

First, if the size of s is not equal to the t, just return false.
Then, use hashmap to record the times of letter appears in each string.
Finally, compare whether these two hashmap is same or not.

💻Code Implementation

class Solution {
public:
    bool isAnagram(string s, string t) {
        map<char,int> m1, m2;
        int len1 = s.size(), len2 = t.size();
        int i = 0;
        if(len1!=len2)
        return false;
        for(i = 0;i<len1;i++){
            auto it1 = m1.find(s[i]);
            auto it2 = m2.find(t[i]);
            if(it1==m1.end()){
                m1[s[i]] = 1;
            }else{
                m1[s[i]]++;
            }
            if(it2==m2.end()){
                m2[t[i]] = 1;
            }else{
                m2[t[i]]++;
            }
        }
        int s1 = m1.size(),s2 = m2.size();
        if(m1!=m2)
            return false;
        map<char,int>::iterator iter;
        for(iter=m1.begin();iter!=m1.end();iter++){
            auto it = m2.find(iter->first);
            if(it==m2.end())
            return false;
            else{
                if(it->second!=iter->second)
                return false;
            }
        }
        return true;
    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(n)

---

🧩Problem solution – 349. Intersection of two Arrays

link

💡Problem description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

🧭Thought Process

We can use hashmap to record every letter has appeared in nums1. Then traverse the array nums2, if any letter can be found in the hashmap, we add it into the final result and delete it in hashmap.

💻Code Implementation

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        map<int,int> m1;
        for(int i = 0;i<nums1.size();i++){
            auto it = m1.find(nums1[i]);
            if(it==m1.end()){
                m1[nums1[i]] = 1;
            }
        }
        vector<int> res;
        for(int i = 0;i<nums2.size();i++){
            if(m1.find(nums2[i])!=m1.end()){
                res.push_back(nums2[i]);
                m1.erase(nums2[i]);
            }
        }
        return res;
    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(n)

---

🧩Problem solution – 202. Happy Number

link

💡Problem description

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.
  Return true if n is a happy number, and false if not.

Example 1:
Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:
Input: n = 2
Output: false

Constraints:

1 <= n <= 2 ³¹ - 1

🧭Thought Process

The first thing we should think about is in what circumtances we will fall into infinite loop. It’s easy for us to find that if there is a number keeps appearing in calculation process, it will lead to infinite loop. Is there any other circumtance? NO. No matter how large the initial number is, after a few rounds of calculation, it will turn into a number less than 1000, casuing the subsequent results to always fall within a finite range.

💻Code Implementation

class Solution {
public:
    bool isHappy(int n) {
        int i = 0,j = 0;
        int re = 0;
        unordered_map<int,int> m;
        m[n] = 1;
        while(true){
            if(n==1){
                return true;
            }
            re = 0;
            while(n!=0){
                re+=pow(n%10,2);
                n = n/10;
            }
            auto it = m.find(re);
            if(it!=m.end()){
                return false;
            }
            m[re] = 1;
            n = re;
        }
    }
};

⏱️Complexity Analysis

• Time complexity: O(log n)
• Space complexity: O(log n)