Arrays & Hashing

Arrays and Hash Maps form the foundation of almost all data structures and algorithms.

Mental model

• Array answers: “Give me element i now.” Indexes are arithmetic; locality is predictable.
• Hash map / set answers: “Given an arbitrary key, have I seen it (or how many times)?” You trade predictable memory layout for lookup speed.

Interview tip: explicitly say why you chose frequency map vs set (“I need counts / complements” vs “I only test membership”).

Key Concepts

• Arrays / Lists: Contiguous indices. $O(1)$ random access, but inserting or deleting in the middle is often $O(n)$ because successors move.
• Hash Maps: Map keys through a hash function into buckets for expected $O(1)$ get/set. Collisions explain worst-case degeneration and why ordering is not intrinsic unless you switch to sorted structures (TreeMap).
• Hash Sets: Set membership checks and deduplication—the same hashing idea without a stored payload per key.

Hashes are typically average-case structures; cite worst-case vigilance only when adversarial hashing or huge memory pressure matters.

When to stay with the array only

Prefer scanning or sorting plus two pointers when the problem asks for contiguous structure, ranking, or monotone properties that a hash hides. Prefer hashes when brute force would revisit the same key many times (“seen before?”, “count pairs by complement”, “canonical form of multiset”).

Diagram

Pattern Recognition

Look for Array & Hashing patterns when the problem asks for:

• "Two elements that sum to a target" (Hash Map complements).
• "Frequencies or counts of elements" (Frequency maps).
• "Finding duplicates" or "checking for existence" (Hash Sets).
• "Subarray sums" (Prefix Sum arrays).
• "In-place array manipulation" (Swapping, sorting, or two pointers).

Problem List

Explore the curated list of Arrays & Hashing problems in this section. See individual problem pages for in-depth diagrams, concepts, and optimal implementations.