Hash Map Patterns (Two Sum)

    DSA · Beginner

    Definition

    Store seen values in a hash map so the complement of each element is found in O(1).

    The most asked interview question and a reusable pattern.

    Diagram

    2 7 11 15, target 9see 7, need 2 ✓

    Flowchart

    Loop with indexneed = target − xIf need seen, return pairElse store x → index

    Example: Two Sum

    nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
    if target - x in seen:
        print([seen[target - x], i]); break
    seen[x] = i

    Output: [0, 1]

    Complexity

    O(n) time · O(n) space

    Key points

    • Check before inserting to avoid using an element twice
    • Same idea solves subarray-sum-k

    Interview questions

    Sorted input?

    Use two pointers for O(1) extra space.

    More DSA topics

    ArraysLinked ListStackQueue