Handbooks / Data Structures & Algorithms / Chapter 1

Arrays and Hashing

7 pages · ~5 min✓ Reviewed

Start here. Next up: Linked Lists, Stacks and Queues.

Data Structures & AlgorithmsPage 1

Arrays and Strings: The Mental Model

1. Array Layout and Costs

Array = contiguous memory
arr[i] is found at base address + i * size
Middle insert or delete shifts elements

Operation	Cost	Why
Access `arr[i]`	O(1)	base + i*size
Insert or delete at end	O(1)	nothing shifts
Insert or delete in middle	O(n)	elements shift
Search, unsorted	O(n)	scan every item
Search, sorted	O(log n)	binary search

2. Dynamic Arrays

List, ArrayList, vector grow capacity by a constant factor when full
Vector often 2x, ArrayList 1.5x, CPython list ~1.125x
One resize copies everything: O(n)
Append is amortized O(1): resizes are rare

3. Strings

Strings are immutable in Python, Java and JS
Each s += c builds a new string

python

parts = []
for c in s:
    parts.append(c)
result = "".join(parts)

join once at the end: O(n)

Concatenation in a loop

s += c in a loop is O(n^2). Build a list, then join once.

Data Structures & AlgorithmsPage 2

Hash Maps and Hash Sets: Internals and Costs

1. Map, Set and the Mechanism

Hash map: key → value
Hash set: keys only
Insert, lookup, delete: average O(1)
Worst case O(n): many keys collide

hash(key)an integer
mod bucketspicks index
Bucketentry stored
Collision?chaining or open addressing

Chaining: a bucket holds a list of entries
Open addressing: probe for the next free slot
Resize at load factor ~0.7 to 0.75 keeps average O(1)

2. Keys and Map vs Array

Keys must be hashable and immutable
A tuple can be a key; a list cannot

python

seen = {}
seen[(1, 2)] = "ok"
try:
    seen[[1, 2]] = "no"
except TypeError as e:
    print(e)

output

unhashable type: 'list'

	Hash map	Array
Lookup	O(1) by any key	O(1) by index only
Memory	more	less
Order	none	by index

Remember

Average O(1) is not a guarantee: many collisions push it to O(n).

Data Structures & AlgorithmsPage 3

Frequency Counting and Lookup Patterns

1. Counting in One Pass

One pass over the input: O(n) time, O(k) space for k distinct keys
Use Counter(s) or the manual counts.get(c, 0) + 1

python

from collections import Counter
s = 'aab'
c = Counter(s)  # Counter form
counts = {}  # manual form
for ch in s:
    counts[ch] = counts.get(ch, 0) + 1

2. Seen-Set Lookups

Two Sum: check target - x in seen before inserting x
seen[value] = index: O(n) instead of O(n^2)
Duplicates: if x is already in the set return true, else add(x)

python

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i

3. Anagrams and Grouping

Task	Key or test
Anagram check	Two frequency maps are equal
Lowercase only	26-slot count array
Group key (pick one)	`tuple(sorted(word))`, `''.join(sorted(word))` or a 26-count tuple

Group Anagrams

Same key means anagrams: groups[key].append(word) with groups = defaultdict(list).

Data Structures & AlgorithmsPage 4

Two Pointers and Prefix Sums

1. Two Pointers

Opposite ends: l=0, r=n-1 on a sorted array
Sum too small → l += 1; too large → r -= 1
O(n) time, O(1) space
Slow/fast: slow writes, fast reads (in-place dedupe, remove-element)

2. Prefix Sums

pre[i+1] = pre[i] + a[i], so pre has length n+1
sum(l..r) = pre[r+1] - pre[l]: O(1) after O(n) build
Subarray sum = k: map of prefix sum → count
Each step add cnt[run - k], then count run; O(n)

python

def count_k(a, k):
    cnt, run, res = {0: 1}, 0, 0
    for x in a:
        run += x
        res += cnt.get(run - k, 0)
        cnt[run] = cnt.get(run, 0) + 1
    return res

seed {0: 1} so prefixes starting at index 0 count

3. Choose by Problem

Problem	Tool
Sorted pair	Two pointers
Repeated range queries	Prefix sums
Unsorted pair lookup	Hash map

Pre length

Off-by-one trap: pre needs n+1 slots, with pre[0] = 0.

Data Structures & AlgorithmsPage 5

Sliding Window and Common Mistakes

1. Two Window Shapes

	Fixed (size k)	Variable
Move	add a[i], drop a[i-k]	expand r, shrink l while invalid
Record	best value	best length
Cost	O(n)	O(n), each index in and out once

Expand r
Shrink lwhile invalid
Recordr-l+1

2. No-Repeat Substring

Keep last-seen index per char (or a set)
Duplicate: move l past it

python

last, l, best = {}, 0, 0
for r, c in enumerate(s):
    if c in last and last[c] >= l:
        l = last[c] + 1
    last[c] = r
    best = max(best, r - l + 1)

3. Limits and Mistakes

Needs a monotonic validity rule
Negatives break sum windows
Fix: prefix sums + hash map

Off-by-one: r-l+1, prefix length n+1
Mutating a list while iterating it
List membership O(n): use a set, O(1)

Window test

Only slide if growing r can never repair an invalid window.

Data Structures & AlgorithmsPage 6

Cheat Sheet: Arrays, Strings and Hash Maps

1. Operation Costs

	Costs
Array	access O(1); search O(n); middle insert/delete O(n); append amortized O(1)
Hash map / set	insert, lookup, delete avg O(1); worst O(n); no ordering
String	immutable; sort O(n log n)

s += c in a loop is O(n^2); collect parts, then ''.join(parts)

2. Pattern Picker

Problem	Use
Pairs in a sorted array	two pointers
Contiguous subarray / substring	sliding window
Range sums	prefix sums
Counts, seen, complements	hash map

3. Templates

python

from collections import Counter
cnt = Counter(s)
seen = {}
pre = [0]  # length n+1
l = 0
for r in range(n):
    ...  # grow r, shrink l

4. Interview Point

Why is append amortized O(1)? Capacity grows by a constant factor, so resizes are rare
When does sliding window fail? Validity not monotonic, e.g. negatives in a sum; use prefix sums + map
Why can a hash map degrade to O(n)? Many keys collide in one bucket, so lookup scans it

Data Structures & AlgorithmsPage 7

Check yourself

Two Sum on a=[3,4], target 6. This code inserts before it checks. What does it return?

[0, 0]: 3 pairs with itself
Check target - x first, then insert x

for i, x in enumerate(a):
    seen[x] = i
    if target - x in seen:
        return [seen[target-x], i]

A window shrinks while its sum is above 3. Does it find sum 3 in [4,-3,2]?

No: l skips past 4 and the window empties
Negatives break the rule that shrinking lowers the sum
Use prefix sums plus a hash map

For a=[2,5,1], pre=[0,2,7,8]. What is pre[3]-pre[1]?

6, which is a[1]+a[2] = 5+1
Range sum is pre[r+1] - pre[l]