Hash map [mp]

Micro pattern¶

Description¶

Associate keys with values for efficient average-case lookup and updates.

Problems¶

Frequency maps¶

Map values or derived keys to occurrence counts.

• 242. Valid Anagram (Top Easy)
• 350. Intersection of Two Arrays II (Top Easy)
• 387. First Unique Character in a String (Top Easy)
• 347. Top K Frequent Elements (Top Medium)
• 454. 4Sum II (Top Hard)
• 149. Max Points on a Line (Top Hard)
• 76. Minimum Window Substring (Top Hard)
• 904. Fruit Into Baskets (Google Prep)

Grouping maps¶

Map canonical keys to collections of corresponding original values.

• 49. Group Anagrams (Top Medium)

Value or state to index¶

Remember a value's position for later complement, split, repetition, or deletion operations.

• 1. Two Sum (Top Easy)
• 3. Longest Substring Without Repeating Characters (Top Medium)
• 105. Construct Binary Tree from Preorder and Inorder Traversal (Top Medium)
• 166. Fraction to Recurring Decimal (Top Medium)
• 380. Insert Delete GetRandom O(1) (Top Medium)
• 315. Count of Smaller Numbers After Self (Top Hard)

Parent mapping¶

Record parent links to permit upward movement without changing the original structure.

• 236. Lowest Common Ancestor of a Binary Tree (Top Hard)
• 863. All Nodes Distance K in Binary Tree (Graph Theory)

Bidirectional mapping¶

Maintain both directions when two sets of values must correspond one-to-one.

• 290. Word Pattern (Google Prep)

Hash map combined with linked ordering¶

Use a map for lookup and linked ordering for fast recency changes.

• 146. LRU Cache (Top Hard)

Implementation¶

Resolve keys through hashed buckets and resize as occupancy grows.

• Hash table (DSA)

Value-indexed dynamic states¶

Map a state key to its best result after processing the input prefix.

• 1218. Longest Arithmetic Subsequence of Given Difference (Dynamic Programming)
• 1027. Longest Arithmetic Subsequence (Dynamic Programming)