Definition

Data structure that stores key-value pairs, internally it uses a hash function to compute the index to underlying array.

Time complexity: O(1) (Search, Insert, Remove) Space complexity: O(n)

Patterns

This technique is usually used as subordinate step to solve the problem, rarely being the main technique:

• Frequency map
• Check if element already existed (duplication)
• Store calculation of previous elements (sum, difference of an element)

Problems

1/ Two Sum

Problem: Given array of nums, find a pair that make the sum equal to target, return the index. We can store the each visited element[i] and index i to the map if element has not visited. We then calculate the difference of the target and element[i], if the map contains the difference meaning the current element is the remaining value that sum up to the target.

2/ Valid Anagram

Problem: Given 2 strings s and t. Return true if t string is an anagram of s. Anagram is strings that have the same characters but the characters can be position differently. We can store the frequency of characters of string s to the Map. Then we loop through string t and decrease the frequency map of each character. If character doesn't exist or character count is 0 then we can determine string isn't anagram.

3/ Group Anagram

Problem: Given an array of strings strs, group the anagrams together. You can return the answer in any order. We can sort the string as key for the Map, since anagram strings will be sorted the same so we can group the elements by that key and add to the results.