DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

HashMap

What Is a HashMap?

A HashMap is a key-value store that uses hashing to achieve O(1) average-case lookup, insert, and delete by key. Every entry is a pair: a key that uniquely identifies the entry, and a value associated with that key.

Think of it as a generalized array. A regular array maps integers (indices) to values. A HashMap maps any type — strings, integers, objects — to values. The key is not a position; it is any meaningful identifier.

Regular array (key must be integer index):
  scores[0] = 88
  scores[1] = 72
  scores[2] = 95

HashMap (key can be any type):
  scores["alice"]   = 88
  scores["bob"]     = 72
  scores["charlie"] = 95

  Lookup scores["alice"] → 88   (one step, not a scan)
  Lookup scores["dave"]  → null (not found)

The HashMap is the most commonly used data structure in interview problems after arrays. Almost every problem involving counting, grouping, pairing, or fast lookup uses a HashMap.

HashMap in Each Language

Language	Class / Type	Import
Java	`HashMap<K, V>`	`java.util.HashMap`
Python	`dict`	Built-in, no import
C++	`unordered_map<K, V>`	`#include <unordered_map>`
JavaScript	`Map` or plain object `{}`	Built-in

Python's dict and JavaScript's plain object {} are the most commonly reached for. Java's HashMap and C++'s unordered_map require explicit type parameters. In interviews, prefer Map over plain objects in JavaScript — it has cleaner APIs and supports non-string keys.

Declaration and Initialization

Java

import java.util.HashMap;
import java.util.Map;

public class HashMapDeclaration {

    public static void main(String[] args) {
        // Empty HashMap
        HashMap<String, Integer> scores = new HashMap<>();

        // Pre-sized — avoids rehashing when you know the approximate size
        HashMap<String, Integer> presized = new HashMap<>(100);

        // Using Map interface (preferred — more flexible)
        Map<String, Integer> map = new HashMap<>();

        // Initialize with entries (Java 9+)
        Map<String, Integer> preloaded = Map.of(
            "alice", 88,
            "bob",   72
        );
        // Note: Map.of() creates an IMMUTABLE map — no put() after creation

        // Mutable preloaded — copy into HashMap
        Map<String, Integer> mutable = new HashMap<>(Map.of("alice", 88, "bob", 72));

        System.out.println("Empty map:   " + map.size());
        System.out.println("Preloaded:   " + preloaded);
        System.out.println("Mutable:     " + mutable);
    }
}

Output:
Empty map:   0
Preloaded:   {alice=88, bob=72}
Mutable:     {alice=88, bob=72}

Core Operations

Insert and Update — put / set

Java

import java.util.HashMap;
import java.util.Map;

public class HashMapInsert {

    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();

        // Insert new entry — O(1) average
        map.put("alice", 88);
        map.put("bob",   72);
        map.put("charlie", 95);
        System.out.println("After inserts: " + map);

        // Update existing entry — put() overwrites if key exists
        map.put("alice", 99);
        System.out.println("After update alice→99: " + map.get("alice"));

        // putIfAbsent — only inserts if key is not present
        map.putIfAbsent("alice", 0);   // alice already exists → no change
        map.putIfAbsent("dave", 61);   // dave is new → inserted
        System.out.println("alice after putIfAbsent: " + map.get("alice")); // still 99
        System.out.println("dave after putIfAbsent:  " + map.get("dave"));  // 61
    }
}

Output:
After inserts: {alice=88, bob=72, charlie=95}
After update alice→99: 99
alice after putIfAbsent: 99
dave after putIfAbsent:  61

Lookup — get / getOrDefault

Java

import java.util.HashMap;
import java.util.Map;

public class HashMapLookup {

    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("alice", 88);
        map.put("bob",   72);

        // get — returns null if key does not exist
        System.out.println("alice:   " + map.get("alice")); // 88
        System.out.println("charlie: " + map.get("charlie")); // null

        // getOrDefault — returns fallback value instead of null
        // MOST USED method in interview problems
        System.out.println("charlie (default 0): " + map.getOrDefault("charlie", 0)); // 0
        System.out.println("alice   (default 0): " + map.getOrDefault("alice", 0));   // 88

        // containsKey — check existence before accessing
        System.out.println("Has alice: " + map.containsKey("alice"));     // true
        System.out.println("Has dave:  " + map.containsKey("dave"));      // false

        // containsValue — O(n) scan through all values
        System.out.println("Has value 72:  " + map.containsValue(72));    // true
        System.out.println("Has value 100: " + map.containsValue(100));   // false
    }
}

Output:
alice:   88
charlie: null
charlie (default 0): 0
alice   (default 0): 88
Has alice: true
Has dave:  false

Delete — remove / erase / delete

Java

import java.util.HashMap;
import java.util.Map;

public class HashMapDelete {

    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("alice", 88);
        map.put("bob",   72);
        map.put("charlie", 95);

        // remove(key) — removes entry, returns the value that was there
        Integer removed = map.remove("bob");
        System.out.println("Removed bob's score: " + removed);   // 72
        System.out.println("After remove:        " + map);

        // remove(key) on non-existent key — returns null, no error
        Integer notFound = map.remove("dave");
        System.out.println("Remove dave (missing): " + notFound); // null

        // remove(key, value) — removes only if value matches
        boolean conditionalRemove = map.remove("alice", 99); // 88 ≠ 99
        System.out.println("Conditional remove (value mismatch): " + conditionalRemove); // false
        System.out.println("Alice still here: " + map.containsKey("alice")); // true
    }
}

Output:
Removed bob's score: 72
After remove: {alice=88, charlie=95}
Remove dave (missing): null
Conditional remove (value mismatch): false
Alice still here: true

Iteration Patterns

Iterating over a HashMap — visiting every key, every value, or every key-value pair.

Java

import java.util.HashMap;
import java.util.Map;

public class HashMapIteration {

    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<>();
        scores.put("alice",   88);
        scores.put("bob",     72);
        scores.put("charlie", 95);

        // Iterate key-value pairs — most common
        System.out.println("Key-value pairs:");
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println("  " + entry.getKey() + " → " + entry.getValue());
        }

        // Iterate keys only
        System.out.println("Keys:");
        for (String key : scores.keySet()) {
            System.out.println("  " + key);
        }

        // Iterate values only
        System.out.println("Values:");
        for (int value : scores.values()) {
            System.out.println("  " + value);
        }

        // forEach (lambda) — Java 8+
        System.out.println("forEach:");
        scores.forEach((name, score) ->
            System.out.println("  " + name + " scored " + score));

        // Find max value during iteration
        String topScorer = "";
        int maxScore = Integer.MIN_VALUE;
        for (Map.Entry<String, Integer> e : scores.entrySet()) {
            if (e.getValue() > maxScore) {
                maxScore = e.getValue();
                topScorer = e.getKey();
            }
        }
        System.out.println("Top scorer: " + topScorer + " (" + maxScore + ")");
    }
}

Output:
Key-value pairs:
  alice → 88
  bob → 72
  charlie → 95
Keys: alice  bob  charlie
Values: 88  72  95
Top scorer: charlie (95)

Order note: HashMap / dict / unordered_map do not guarantee iteration order. If you need sorted order, use TreeMap (Java), iterate sorted(d.items()) (Python), iterate std::map (C++), or sort entries before iterating.

The `getOrDefault` Pattern — Most Used in Interviews

The single most useful HashMap technique in interviews: safely read a value with a fallback when the key might not exist.

Java

import java.util.HashMap;
import java.util.Map;

public class GetOrDefaultPattern {

    public static void main(String[] args) {
        String s = "programming";

        // Build character frequency — the #1 HashMap use case
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            // getOrDefault(key, 0) safely reads current count
            // +1 increments it, put() stores the new count
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        System.out.println("Frequency: " + freq);

        // merge() — alternative to getOrDefault for counting
        Map<Character, Integer> freq2 = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq2.merge(c, 1, Integer::sum); // merge(key, default, remappingFn)
        }
        System.out.println("Frequency (merge): " + freq2);

        // computeIfAbsent — useful for grouping
        Map<Integer, java.util.List<Character>> byFreq = new HashMap<>();
        for (Map.Entry<Character, Integer> e : freq.entrySet()) {
            byFreq.computeIfAbsent(e.getValue(), k -> new java.util.ArrayList<>())
                  .add(e.getKey());
        }
        System.out.println("By frequency: " + byFreq);
    }
}

Output:
Frequency: {p=1, r=2, o=1, g=2, a=1, m=2, i=1, n=1}
By frequency: {1=[p, o, a, i, n], 2=[r, g, m]}

Two Sum — The Canonical HashMap Interview Problem

Two Sum is the most common HashMap interview problem and the clearest demonstration of why HashMap reduces O(n²) to O(n).

Problem: Given an array and a target, find two indices whose values sum to the target.

Brute force: O(n²)
  For each pair (i, j): check if nums[i] + nums[j] == target
  2 nested loops, n² comparisons

HashMap approach: O(n)
  For each nums[i]: check if (target - nums[i]) was seen before
  If yes → found the pair
  If no  → store nums[i] and its index for future lookups

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TwoSum {

    public static int[] twoSum(int[] nums, int target) {
        // Map: value → index
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            // Has the complement been seen before?
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }

            // Store current value → index for future lookups
            seen.put(nums[i], i);
        }

        return new int[]{}; // No solution found
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));  // [0, 1]
        System.out.println(Arrays.toString(twoSum(new int[]{3, 2, 4}, 6)));       // [1, 2]
        System.out.println(Arrays.toString(twoSum(new int[]{3, 3}, 6)));           // [0, 1]
    }
}

Output:
[0, 1]
[1, 2]
[0, 1]

Dry Run: Two Sum on [2, 7, 11, 15], target = 9

seen = {}

i=0: num=2, complement=9-2=7
  7 in seen? No
  seen = {2: 0}

i=1: num=7, complement=9-7=2
  2 in seen? YES → seen[2]=0
  Return [0, 1] ✓

Why this works:
  When we reach nums[1]=7, we ask "have we seen 2 before?"
  We have (at index 0). So nums[0] + nums[1] = 2 + 7 = 9 = target.
  One pass, O(1) lookup each step → O(n) total.

Lookup Table Pattern

HashMap as a precomputed lookup to avoid repeated computation — converts O(n) repeated scans into O(1) queries.

Java

import java.util.HashMap;
import java.util.Map;

public class LookupTable {

    // Find first character that appears only once — O(n), O(1) space
    public static char firstUnique(String s) {
        Map<Character, Integer> freq = new HashMap<>();

        // Build lookup table in one pass
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        // Query the table in a second pass
        for (char c : s.toCharArray()) {
            if (freq.get(c) == 1) return c;
        }

        return '\0'; // No unique character
    }

    // Check if two strings are isomorphic — each char maps to exactly one other
    public static boolean isIsomorphic(String s, String t) {
        Map<Character, Character> sToT = new HashMap<>();
        Map<Character, Character> tToS = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i), tc = t.charAt(i);

            if (sToT.containsKey(sc) && sToT.get(sc) != tc) return false;
            if (tToS.containsKey(tc) && tToS.get(tc) != sc) return false;

            sToT.put(sc, tc);
            tToS.put(tc, sc);
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println("First unique 'leetcode': " + firstUnique("leetcode")); // 'l'
        System.out.println("Isomorphic 'egg','add':  " + isIsomorphic("egg", "add")); // true
        System.out.println("Isomorphic 'foo','bar':  " + isIsomorphic("foo", "bar")); // false
    }
}

Output:
First unique 'leetcode': l
Isomorphic 'egg','add':  true
Isomorphic 'foo','bar':  false

HashMap Operation Complexity Summary

Operation	Average	Worst	Notes
`put` / `set` / `[]`	O(1)	O(n)	Worst case: all keys collide
`get` / `get()`	O(1)	O(n)	O(n) only with pathological hash
`containsKey` / `has` / `count`	O(1)	O(n)	Same as get
`remove` / `erase` / `delete`	O(1)	O(n)	Amortized O(1)
`size` / `len`	O(1)	O(1)	Stored as a field
Iteration (all entries)	O(n)	O(n)	Must visit every entry
Rehashing	O(n)	O(n)	Triggered by load factor; amortized O(1) per insert

C++ `operator[]` Danger

The most common C++ HashMap bug — using [] for lookup silently inserts a default value:

unordered_map<string, int> map;
map["alice"] = 88;

// DANGER: this INSERTS "dave" → 0 into the map!
cout << map["dave"] << endl;   // prints 0 AND adds "dave" to the map

// SAFE alternatives:
if (map.count("dave"))    cout << map["dave"] << endl;
if (map.find("dave") != map.end()) cout << map.at("dave") << endl;

Always use find() or count() to check existence in C++ before using at() or [] for access. Use [] for writing, not reading.

Common Mistakes Beginners Make

Using map.get(key) == 1 instead of map.getOrDefault(key, 0) == 1 in Java. If key is not in the map, get() returns null, and comparing null == 1 returns false but also risks NullPointerException in certain contexts. Always use getOrDefault when the key might be absent.

Using [] in C++ for read access. map["key"] inserts a default entry if "key" is not present, silently growing the map. Use map.at("key") for safe read-only access (throws on missing) or map.find("key") to check first.

Using plain object {} in JavaScript with non-string keys. obj[42] = "answer" stores it as obj["42"] — JavaScript converts all object keys to strings. Use Map when keys are not strings.

Modifying a map while iterating over it. In Java, adding or removing entries during a for-each over entrySet() throws ConcurrentModificationException. Collect keys to delete first, then delete after the loop.

Expecting sorted order from HashMap. HashMap / dict / unordered_map / Map do not guarantee iteration order. Use TreeMap (Java), sorted() (Python), std::map (C++), or sort entries before iterating if order matters.

Interview Questions

Q: What is the time complexity of all HashMap operations and what causes the worst case?

Insert, lookup, and delete are all O(1) average. The worst case is O(n) and occurs when all n keys hash to the same slot — every operation must scan a chain of length n. A good hash function and a load factor below 0.75 keep the average chain length near 1, ensuring O(1) in practice. Adversarial inputs can force worst-case behavior with simple hash functions, which is why Java 8+ switches from linked lists to red-black trees for chains longer than 8 — capping worst-case at O(log n).

Q: How does getOrDefault differ from get in Java, and when should you use each?

get(key) returns null if the key is not present. getOrDefault(key, defaultValue) returns defaultValue instead of null. In frequency counting and accumulation patterns, getOrDefault(key, 0) eliminates the null check and makes the intent clear. Use get when you intentionally need to distinguish "not present" from "present with a zero or null value." Use getOrDefault for counting, accumulation, and any case where the key might not exist but you have a sensible fallback.

Q: When would you use a TreeMap instead of a HashMap in Java?

Use TreeMap when you need keys in sorted order — when iterating should go in ascending key order, when you need firstKey() / lastKey(), headMap() / tailMap(), or floorKey() / ceilingKey(). TreeMap operations are O(log n) instead of O(1) because it is backed by a red-black tree. For problems that only need key-value storage with fast lookup and do not care about order, HashMap is faster.

FAQs

What is the difference between HashMap and LinkedHashMap in Java?

HashMap does not preserve insertion order — entries may be iterated in any order. LinkedHashMap maintains a doubly linked list through all entries and iterates in insertion order. Use LinkedHashMap when you need both O(1) lookup and predictable iteration order — for example, implementing an LRU cache where you need to know which entry was inserted first.

In Python, is dict ordered?

Yes, since Python 3.7+, dict preserves insertion order as part of the language specification. Iterating over a dict visits keys in the order they were first inserted. In Python 3.6, insertion order was an implementation detail of CPython but not guaranteed. For older Python or when explicit ordering is needed, use collections.OrderedDict.

What is collections.defaultdict in Python and when should I use it?

defaultdict is a subclass of dict that automatically creates a default value for missing keys instead of raising KeyError. defaultdict(int) makes missing keys default to 0 — perfect for counting. defaultdict(list) makes missing keys default to an empty list — perfect for grouping. It eliminates the d.get(key, 0) or if key not in d: d[key] = [] boilerplate. Use it whenever you find yourself initializing missing keys with the same default value.

Quick Quiz

Question 1: map.getOrDefault("alice", 0) when "alice" is not in the map returns:

›A) null
›B) 0
›C) Throws KeyError
›D) Throws NullPointerException

Answer: B) 0. getOrDefault returns the second argument when the key is not present. This is the safe alternative to get() which would return null for a missing key.

Question 2: In C++, map["newKey"] on an unordered_map where "newKey" does not exist:

›A) Returns 0 without modifying the map
›B) Throws std::out_of_range
›C) Inserts "newKey" with default value 0 and returns 0
›D) Returns nullptr

Answer: C) Inserts "newKey" with default value 0 and returns 0. This is the silent insertion trap. The [] operator always inserts if the key is absent. Use map.count("newKey") or map.find("newKey") to check first, then map.at("newKey") for safe read access.

Question 3: You have a HashMap with 10 entries and capacity 16. After inserting the 12th entry (load factor = 0.75), what happens?

›A) The 12th insert fails with an exception
›B) The map resizes to capacity 32 and rehashes all entries
›C) The load factor check is skipped — HashMap only resizes at capacity
›D) The oldest entry is evicted to make room

Answer: B) Resizes to capacity 32 and rehashes. When entries / capacity > threshold (12/16 = 0.75), Java's HashMap triggers a resize — allocates a new array of double the capacity, recomputes every entry's index in the new table, and discards the old array. The 12th insertion completes successfully in the resized table.

Question 4: What is the Two Sum brute force complexity and how does HashMap reduce it?

›A) O(n²) → O(n log n) using sorting
›B) O(n²) → O(n) by storing each number and checking its complement in O(1)
›C) O(n log n) → O(n) using frequency arrays
›D) O(n²) → O(n²) — HashMap does not help with Two Sum

Answer: B) O(n²) → O(n). Brute force checks every pair — O(n²) comparisons. HashMap approach: for each nums[i], check if target - nums[i] was stored in the map — O(1) per lookup. One pass through the array gives O(n) total. The HashMap converts the inner O(n) scan into an O(1) lookup.

Summary

HashMap is the most versatile and most commonly used data structure after arrays. It maps any key type to any value type with O(1) average-case operations.

The key patterns and operations to carry forward:

›put / assignment — O(1) average, overwrites existing value
›get / getOrDefault — O(1) average; always use getOrDefault in counting patterns
›containsKey / has / count — O(1) existence check before access
›remove / erase / delete — O(1) average removal
›Iteration — O(n); order not guaranteed without LinkedHashMap / sorted()
›Frequency counting — freq.put(c, freq.getOrDefault(c, 0) + 1) — the most used single line in HashMap problems
›Two Sum pattern — store seen values, check complement in O(1)
›Lookup table pattern — precompute once, query many times

In the next topic, you will explore HashSet — the key-only variant of a hash table, optimized for existence checking, deduplication, and set operations.

←

PreviousHashing Basics

NextHashSet

→