var Component=(()=>{var k=Object.create;var u=Object.defineProperty;var x=Object.getOwnPropertyDescriptor;var C=Object.getOwnPropertyNames;var I=Object.getPrototypeOf,M=Object.prototype.hasOwnProperty;var v=t=>u(t,"__esModule",{value:!0});var T=(t,r)=>()=>(r||t((r={exports:{}}).exports,r),r.exports),q=(t,r)=>{v(t);for(var h in r)u(t,h,{get:r[h],enumerable:!0})},j=(t,r,h)=>{if(r&&typeof r=="object"||typeof r=="function")for(let n of C(r))!M.call(t,n)&&n!=="default"&&u(t,n,{get:()=>r[n],enumerable:!(h=x(r,n))||h.enumerable});return t},O=t=>j(v(u(t!=null?k(I(t)):{},"default",t&&t.__esModule&&"default"in t?{get:()=>t.default,enumerable:!0}:{value:t,enumerable:!0})),t);var S=T((A,w)=>{w.exports=_jsx_runtime});var E={};q(E,{Highlight:()=>l,default:()=>_,frontmatter:()=>H});var e=O(S()),H={title:"HashMaps",date:"2024-12-07",tags:["Algorithms","hash table","array"],draft:!1,summary:"3 Popular Problems",images:[],layout:"QuestionsPostLayout",readTime:"3 Popular Problems",canonicalUrl:"https://lucianoprea.com/blog/Hashing",thumbnail:"/static/images/codingInterview/hashmap2.svg"},l=({children:t,color:r})=>(0,e.jsx)("span",{style:{backgroundColor:r,borderRadius:"2px",color:"#fff",padding:"0.2rem"},children:t});function N(t={}){let{wrapper:r}=t.components||{};return r?(0,e.jsx)(r,Object.assign({},t,{children:(0,e.jsx)(h,{})})):h();function h(){let n=Object.assign({section:"section",h2:"h2",a:"a",span:"span",strong:"strong",h4:"h4",p:"p",hr:"hr",ol:"ol",li:"li",ul:"ul",code:"code",h3:"h3",blockquote:"blockquote",em:"em"},t.components),{ProgressProvider:g,ProgressWrapper:f,SimpleCollapsibleSection:p,SimpleSectionTitle:m,TextContainer:o,Image:y,CollapsibleQuestionsWrapper:b,CollapsibleSection:c,SectionTitle:s,TabItem:i,Tabs:d}=n;return b||a("CollapsibleQuestionsWrapper",!0),c||a("CollapsibleSection",!0),y||a("Image",!0),g||a("ProgressProvider",!0),f||a("ProgressWrapper",!0),s||a("SectionTitle",!0),p||a("SimpleCollapsibleSection",!0),m||a("SimpleSectionTitle",!0),i||a("TabItem",!0),d||a("Tabs",!0),o||a("TextContainer",!0),(0,e.jsxs)(n.section,{className:"h0Wrapper headingWrapper",children:[" "," ",(0,e.jsxs)(g,{slug:"hashmap",children:[(0,e.jsx)(f,{}),(0,e.jsxs)(n.h2,{id:"theory",children:[(0,e.jsx)(n.a,{href:"#theory","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Theory"]}),(0,e.jsxs)(p,{children:[(0,e.jsxs)(m,{children:["What is a ",(0,e.jsx)(n.strong,{children:"hashmap"}),"?"]}),(0,e.jsxs)(o,{children:[(0,e.jsxs)(n.h4,{id:"definition",children:[(0,e.jsx)(n.a,{href:"#definition","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Definition"]}),(0,e.jsxs)(n.p,{children:["A ",(0,e.jsx)(n.strong,{children:"hash map"})," (or hash table) is a data structure that maps keys to values, enabling highly efficient lookups. While there are various ways to implement a hash table, we\u2019ll focus on a simple yet common implementation."]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(p,{children:[(0,e.jsx)(m,{children:"How does it work?"}),(0,e.jsxs)(o,{children:[(0,e.jsx)(y,{alt:"hashing",src:"/static/images/codingInterview/HashMap.svg",className:"m-2 p-2",width:800,height:250}),(0,e.jsx)(n.ol,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Insert Operation"}),":"]})}),(0,e.jsxs)(n.ul,{children:[(0,e.jsxs)(n.li,{children:[(0,e.jsx)(l,{color:"#1877F2",children:"Compute the Hash Code"}),": For a given key (which could be a string or any data type), calculate its hash code. The hash code is typically an integer or long value. Note that two different keys might produce the same hash code due to the finite range of integers and the potentially infinite number of keys."]}),(0,e.jsxs)(n.li,{children:[(0,e.jsx)(l,{color:"#25c2a0",children:"Map the Hash Code to an Index"}),": Convert the hash code to an array index using a modulus operation, such as ",(0,e.jsx)(n.code,{children:"hash(key) % array_length"}),". Multiple hash codes could map to the same index due to collisions."]}),(0,e.jsxs)(n.li,{children:[(0,e.jsx)(l,{color:"#1877F2",children:"Store the Key-Value Pair"}),": At the calculated index, maintain a linked list to handle collisions. Append the key-value pair to this list. The linked list allows storage of multiple key-value pairs that hash to the same index."]})]}),(0,e.jsx)(n.ol,{start:"2",children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Retrieve Operation"}),":"]})}),(0,e.jsxs)(n.ul,{children:[(0,e.jsx)(n.li,{children:"To retrieve a value by its key, repeat the insertion steps:"}),(0,e.jsx)(n.li,{children:"Compute the hash code from the key."}),(0,e.jsx)(n.li,{children:"Map the hash code to the array index."}),(0,e.jsx)(n.li,{children:"Traverse the linked list at that index to find the key and return the associated value."})]}),(0,e.jsxs)(n.h3,{id:"performance-and-collisions",children:[(0,e.jsx)(n.a,{href:"#performance-and-collisions","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Performance and Collisions:"]}),(0,e.jsx)(n.p,{children:"If the number of collisions is high, the worst-case runtime for a lookup is (O(N)), where (N) is the total number of keys. However, with a well-designed hash function that minimizes collisions and an appropriately sized array, the average lookup time is (O(1)), making hash tables an efficient choice for many applications."}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(b,{children:[(0,e.jsxs)(n.h2,{id:"coding",children:[(0,e.jsx)(n.a,{href:"#coding","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Coding"]}),(0,e.jsxs)(c,{children:[(0,e.jsx)(s,{children:"Q1 - Two Sum"}),(0,e.jsxs)(o,{children:[(0,e.jsx)(l,{color:"rgb(34 197 94)",children:"Easy Difficulty"}),(0,e.jsxs)(n.blockquote,{children:[(0,e.jsxs)(n.p,{children:["Given an array of integers ",(0,e.jsx)(n.code,{children:"nums"})," and an integer ",(0,e.jsx)(n.code,{children:"target"}),", return indices of the two numbers such that they add up to target."]}),(0,e.jsx)(n.p,{children:"You may assume that each input would have exactly one solution, and you may not use the same element twice."}),(0,e.jsx)(n.p,{children:"You can return the answer in any order."})]}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 1:"})}),(0,e.jsx)(i,{label:"java",language:"javascript",code:`Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].`}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 2:"})}),(0,e.jsx)(i,{label:"java",language:"javascript",code:`Input: nums = [3,2,4], target = 6 Output: [1,2]`}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 3:"})}),(0,e.jsx)(i,{label:"java",language:"javascript",code:`Input: nums = [3,3], target = 6 Output: [0,1]`}),(0,e.jsx)(n.hr,{}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 1"})}),(0,e.jsx)(n.ul,{children:(0,e.jsx)(n.li,{children:"Create a hash table (dictionary in Python) to store the numbers encountered so far."})})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 2"})}),(0,e.jsx)(n.ul,{children:(0,e.jsx)(n.li,{children:"While iterating through the array, you check if the complement of the current number (i.e., target minus the current number) is already in the hash table."})})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(c,{children:[(0,e.jsx)(s,{children:"Q2 - Valid Anagram"}),(0,e.jsxs)(o,{children:[(0,e.jsx)(l,{color:"rgb(34 197 94)",children:"Easy Difficulty"}),(0,e.jsx)(n.blockquote,{children:(0,e.jsxs)(n.p,{children:["Given two strings ",(0,e.jsx)(n.strong,{children:"s"})," and ",(0,e.jsx)(n.strong,{children:"t"}),", return ",(0,e.jsx)(n.code,{children:"true"})," if ",(0,e.jsx)(n.strong,{children:"t"})," is an anagram of ",(0,e.jsx)(n.strong,{children:"s"}),", and ",(0,e.jsx)(n.code,{children:"false"})," otherwise."]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 1:"})}),(0,e.jsx)(i,{label:"java",language:"javascript",code:`Input: s = "anagram", t = "nagaram" Output: true`}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 2:"})}),(0,e.jsx)(i,{label:"java",language:"javascript",code:`Input: s = "rat", t = "car" Output: false`}),(0,e.jsx)(n.hr,{}),(0,e.jsxs)(n.h3,{id:"hints",children:[(0,e.jsx)(n.a,{href:"#hints","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),(0,e.jsx)(n.strong,{children:"Hints"})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 1"})}),(0,e.jsxs)(n.p,{children:["A brute-force approach is to sort the given strings and compare their equality. However, this method has a time complexity of ",(0,e.jsx)(n.em,{children:"O(nlogn + mlogm)"}),"."]}),(0,e.jsx)(n.p,{children:"While this solution is acceptable, can you think of a more efficient way to solve the problem without relying on sorting?"})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 2"})}),(0,e.jsx)(n.p,{children:"We can just consider maintaining the frequency of each character. We can do this by having two separate hashmaps for the two strings."}),(0,e.jsx)(n.p,{children:"Then, we can check whether the frequency of each character in s is equal to that in t."})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(c,{children:[(0,e.jsx)(s,{children:"Q3 - Top K Frequent Elements"}),(0,e.jsxs)(o,{children:[(0,e.jsx)(l,{color:"rgb(202 138 4)",children:"Medium Difficulty"}),(0,e.jsx)(n.blockquote,{children:(0,e.jsxs)(n.p,{children:["Given an integer array ",(0,e.jsx)(n.code,{children:"nums"})," and an integer ",(0,e.jsx)(n.code,{children:"k"}),", return the k most frequent elements. You may return the answer in any order."]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 1:"})}),(0,e.jsx)(i,{label:"java",language:"javascript",code:`Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]`}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 2:"})}),(0,e.jsx)(i,{label:"java",language:"javascript",code:`Input: nums = [7,7], k = 1 Output: [7]`}),(0,e.jsx)(n.hr,{}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 1"})}),(0,e.jsxs)(n.p,{children:[(0,e.jsx)(l,{color:"#25c2a0",children:"Create a hashmap"})," to store the frequency of each element in the input array."]})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 2"})}),(0,e.jsx)(n.p,{children:"Convert the hashmap items into pairs and store them in a list (pairs)."})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 3"})}),(0,e.jsxs)(n.p,{children:[(0,e.jsx)(l,{color:"#1877F2",children:"Sort the list of pairs"})," based on the frequency in descending order."]})]}),(0,e.jsxs)(n.p,{children:[(0,e.jsx)(n.strong,{children:"Move to solution:"})," ",(0,e.jsx)(n.a,{href:"#solution-Q3",children:"Solution Q3 - Top K Frequent Elements"}),"."]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(n.h2,{id:"solutions",children:[(0,e.jsx)(n.a,{href:"#solutions","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Solutions"]}),(0,e.jsxs)(c,{children:[(0,e.jsx)(s,{children:"Solution Q1"}),(0,e.jsxs)(o,{children:[(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Solution Overview:"})}),(0,e.jsxs)(n.ol,{children:[(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Create a hashmap"})," (dictionary in Python) to store the numbers encountered so far."]}),(0,e.jsx)(n.li,{children:"While iterating through the array, you check if the complement of the current number (i.e., target minus the current number) is already in the hash table."}),(0,e.jsx)(n.li,{children:"If it is, you've found the pair that sums to the target."})]}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Time Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N)"}),", where N is the length of the input array. We traverse the array once."]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Space Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N)"})," in the worst case, as we might need to store all 'n' numbers in the hashmap."]})}),(0,e.jsxs)(n.h4,{id:"code-solution",children:[(0,e.jsx)(n.a,{href:"#code-solution","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Code Solution"]}),(0,e.jsxs)(d,{children:[(0,e.jsx)(i,{label:"Python",language:"python",code:`def twoSum(self, nums: List[int], target: int) -> List[int]: num_dict = {} for i, num in enumerate(nums): complement = target - num if complement in num_dict: return [num_dict[complement], i] num_dict[num] = i return []`}),(0,e.jsx)(i,{label:"Javascript",language:"javascript",code:`var twoSum = function(nums, target) { const numMap = new Map(); for (let i = 0; i < nums.length; i++) { const complement = target - nums[i]; if (numMap.has(complement)) { return [numMap.get(complement), i]; } numMap.set(nums[i], i); } return []; };`}),(0,e.jsx)(i,{label:"Java",language:"javascript",code:`public int[] twoSum(int[] nums, int target) { HashMap numMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (numMap.containsKey(complement)) { return new int[]{numMap.get(complement), i}; } numMap.put(nums[i], i); } return new int[0]; }`})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(c,{children:[(0,e.jsx)(s,{children:"Solution Q2"}),(0,e.jsxs)(o,{children:[(0,e.jsxs)(n.p,{children:[(0,e.jsx)(n.strong,{children:"Solution Overview:"})," The solution involves comparing the character frequency of each letter in both strings. If the character frequency for each character is the same, the two strings are anagrams."]}),(0,e.jsxs)(n.ol,{children:[(0,e.jsx)(n.li,{children:"Create two hashmaps (dictionaries) to store the frequency of each character in both strings."}),(0,e.jsx)(n.li,{children:"Iterate through both strings, populating the hashmaps."}),(0,e.jsx)(n.li,{children:"Compare the two hashmaps to check if they contain the same character frequencies."})]}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Time Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N)"}),", where N is the length of the input strings. We iterate through both strings once."]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Space Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(1)"})," in the sense that the size of the hashmaps used for character counts is constant since the number of possible characters is limited (e.g., 26 for lowercase letters)."]})}),(0,e.jsxs)(n.h4,{id:"code-solution-1",children:[(0,e.jsx)(n.a,{href:"#code-solution-1","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Code Solution"]}),(0,e.jsxs)(d,{children:[(0,e.jsx)(i,{label:"Python",language:"python",code:`class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False countS, countT = {}, {} for i in range(len(s)): countS[s[i]] = 1 + countS.get(s[i], 0) countT[t[i]] = 1 + countT.get(t[i], 0) return countS == countT`}),(0,e.jsx)(i,{label:"Javascript",language:"javascript",code:`var isAnagram = function(s, t) { if (s.length !== t.length) { return false; } const charCountS = new Map(); const charCountT = new Map(); for (const char of s) { charCountS.set(char, (charCountS.get(char) || 0) + 1); } for (const char of t) { charCountT.set(char, (charCountT.get(char) || 0) + 1); } for (const [char, count] of charCountS) { if (charCountT.get(char) !== count) { return false; } } return true; };`}),(0,e.jsx)(i,{label:"Java",language:"javascript",code:`public class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } HashMap countS = new HashMap<>(); HashMap countT = new HashMap<>(); for (int i = 0; i < s.length(); i++) { countS.put(s.charAt(i), countS.getOrDefault(s.charAt(i), 0) + 1); countT.put(t.charAt(i), countT.getOrDefault(t.charAt(i), 0) + 1); } return countS.equals(countT); } }`})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(c,{children:[(0,e.jsx)(s,{children:"Solution Q3"}),(0,e.jsxs)(o,{children:[(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Solution Overview:"})}),(0,e.jsxs)(n.ol,{children:[(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Create a hashmap (hm)"})," to store the frequency of each element in the input array."]}),(0,e.jsx)(n.li,{children:"Convert the hashmap items into pairs and store them in a list (pairs)."}),(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Sort the list of pairs"})," based on the frequency in descending order."]}),(0,e.jsx)(n.li,{children:"Extract the first k elements from the sorted list."})]}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Time Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N log N)"}),", where N is the length of the input array. This is due to the sorting step."]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Space Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N)"})," for the hashmap and O(N) for the list of pairs."]})}),(0,e.jsxs)(n.h4,{id:"code-solution-2",children:[(0,e.jsx)(n.a,{href:"#code-solution-2","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Code Solution"]}),(0,e.jsxs)(d,{children:[(0,e.jsx)(i,{label:"Python",language:"python",code:`def topKFrequent(self, nums: List[int], k: int) -> List[int]: hm = {} for n in nums: hm[n] = 1 + hm.get(n, 0) pairs = [] for key, value in hm.items(): pairs.append([key, value]) pairs.sort(key=lambda pair: pair[1], reverse=True) return [x[0] for x in pairs][:k]`}),(0,e.jsx)(i,{label:"JavaScript",language:"javascript",code:`var topKFrequent = function(nums, k) { let frequencyMap = new Map(); // Step 1: Create a hashmap to store the frequency of each element for (let num of nums) { frequencyMap.set(num, 1 + (frequencyMap.get(num) || 0)); } let pairs = Array.from(frequencyMap.entries()); // Step 2: Sort the pairs based on frequency in descending order pairs.sort((a, b) => b[1] - a[1]); // Step 3: Extract the k most frequent elements return pairs.slice(0, k).map(pair => pair[0]); }; `}),(0,e.jsx)(i,{label:"Java",language:"javascript",code:`public int[] topKFrequent(int[] nums, int k) { Map frequencyMap = new HashMap<>(); // Step 1: Create a hashmap to store the frequency of each element for (int num : nums) { frequencyMap.put(num, 1 + frequencyMap.getOrDefault(num, 0)); } List> pairs = new ArrayList<>(frequencyMap.entrySet()); // Step 2: Sort the pairs based on frequency in descending order pairs.sort((a, b) -> b.getValue() - a.getValue()); // Step 3: Extract the k most frequent elements List result = new ArrayList<>(); for (int i = 0; i < k && i < pairs.size(); i++) { result.add(pairs.get(i).getKey()); } // Convert List to int[] return result.stream().mapToInt(Integer::intValue).toArray(); }`})]}),(0,e.jsx)(n.hr,{})]})]})]})]})]})}}var _=N;function a(t,r){throw new Error("Expected "+(r?"component":"object")+" `"+t+"` to be defined: you likely forgot to import, pass, or provide it.")}return E;})(); ;return Component;