Arrays & Hashing

The Foundation of Everything

Arrays and hash maps are the bedrock of coding interviews. Nearly every problem uses one or both. Before diving into advanced data structures, you must be fluent in these fundamentals.

Arrays — Core Operations

An array stores elements in contiguous memory, giving $O(1)$ random access by index. The key complexity tradeoffs:

| Operation | Array | Dynamic Array | |-----------|-------|--------------| | Access by index | $O(1)$ | $O(1)$ | | Append | — | Amortized $O(1)$ | | Insert at position $i$ | $O(n)$ | $O(n)$ | | Search (unsorted) | $O(n)$ | $O(n)$ | | Search (sorted) | $O(\log n)$ | $O(\log n)$ |

In Python, list is a dynamic array. In C++ and Java, use vector and ArrayList.

Hash Maps — $O(1)$ Lookup

A hash map (dictionary) maps keys to values with average $O(1)$ insert, delete, and lookup. This is the single most useful data structure in interviews.

When to use a hash map:

• Counting frequencies ("How many times does each element appear?")
• Checking membership ("Have I seen this element before?")
• Mapping relationships ("What value corresponds to this key?")

Example — Two Sum. Given an array and a target, find two elements that sum to the target.

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

One pass, $O(n)$ time, $O(n)$ space. Without the hash map, you would need $O(n^2)$ nested loops.

Prefix Sums

A prefix sum array lets you compute the sum of any subarray in $O(1)$ after $O(n)$ preprocessing:

prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
    prefix[i + 1] = prefix[i] + nums[i]

# Sum of nums[l..r] inclusive:
subarray_sum = prefix[r + 1] - prefix[l]

Finance application. Prefix sums compute cumulative P&L instantly. "What was the total return between day $l$ and day $r$?" becomes a constant-time lookup.

Frequency Counting

Many problems reduce to counting. Python's collections.Counter is your best friend:

from collections import Counter
counts = Counter(nums)
# Most common k elements:
top_k = counts.most_common(k)

Pattern — Anagram detection. Two strings are anagrams if and only if they have the same character frequency counts. Compare counters in $O(n)$.

Worked Interview Problem

Given an array of stock tickers, group all anagram tickers together.

from collections import defaultdict
def group_anagrams(tickers):
    groups = defaultdict(list)
    for t in tickers:
        key = tuple(sorted(t))
        groups[key].append(t)
    return list(groups.values())

Sorting each ticker takes $O(k \log k)$ where $k$ is the ticker length, and we do this for $n$ tickers: $O(n \cdot k \log k)$ total.

Interview Tip: When you see "find duplicates," "count occurrences," or "group by property," immediately think hash map. State your data structure choice and its complexity before coding — interviewers want to hear your reasoning.