DSA Notes

Data Structures

Map & Hashing

Look things up by key instead of by position.

The idea

A map stores key → value pairs. map keeps keys sorted with O(log n) operations; unordered_map hashes them for O(1) on average.

Typical uses: counting occurrences, remembering where a value was last seen, and turning large or non-numeric keys (strings, pairs, whole vectors) into something you can index.

Many “find a pair” problems become one pass: for each item, compute what its partner must be and look that up among the items already seen.

Sample problem

1. Two Sum ↗ Easy

Given an array and a target, return the indices of the two numbers that add up to the target.

nums = [8,2,11,5,4], target = 9
output = [3,4]   (5 + 4)

Why the solution works

Trying every pair is O(n²). But for a number x the partner is not a search: it must be exactly target − x.

So the only question is “has that value appeared before, and where?”. A hash map from value to index answers it in O(1), turning the double loop into a single pass.

Looking the partner up before storing the current number guarantees the two indices are different.

Complexity: O(n) time on average, O(n) memory.

Watch out

  • m[key] creates the key if it is missing. Use m.count(key) or m.find(key) to test.
  • unordered_map has no default hash for pairs or vectors and can be slow on adversarial input; map is the safe choice.
  • Iterating a map visits keys in sorted order; an unordered_map has no meaningful order.
Watch it run

Try your own input

Practise on LeetCode