Arrays & Hashing

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

Key Concepts

• Arrays / Lists: Contiguous blocks of memory. Excellent for $O(1)$ random access, but $O(n)$ for arbitrary insertions or deletions.
• Hash Maps / Dictionaries: Key-value stores utilizing hash functions. Excellent for amortized $O(1)$ lookups, insertions, and deletions. The ultimate tool for trading space for time.
• Hash Sets: Like Hash Maps, but only storing keys. Used primarily for $O(1)$ existence checks and deduplication.

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.