Foundations · Lesson 2/8

Arrays, Strings & Hash Maps: The Everyday Toolkit

40 min 1 quiz Graded labs: 3

What you'll learn

How arrays and strings are stored, and what is cheap or expensive about them
How a hash map (dictionary) and a hash set give you lookups in O(1) on average
The patterns that turn O(n²) ideas into O(n): seen-set, frequency counting, canonical keys, prefix sums, sliding window
You will solve: two-sum, grouping anagrams and the longest substring without repeats

Lockers and a coat check 🧥

An array is a hallway of numbered lockers. You can walk straight to locker 57 without opening 1 to 56, so reading a[57] is instant: O(1). But if you want to squeeze a new locker into the middle of the hallway, every locker after it has to slide over one place: O(n).

A hash map is a coat check. You hand over your coat with the name "Sara". The attendant does not search the whole rack: a fixed rule turns "Sara" into a hook number (say 7) and the coat is right there. Anyone can later say "Sara" and get the coat back immediately, and it does not matter whether the cloakroom holds 10 coats or 10 million.

That one trick, computing where to look from the thing you are looking for, is behind most of the speed-ups in this lesson.

Arrays and strings

An array stores items next to each other in memory, all the same size. The address of item i is simply start + i × size, so any index is reached in one step.

Read or write a[i]: O(1)
Append at the end: O(1) amortised (a Python list, JavaScript Array and Java ArrayList are dynamic arrays: when full they allocate a bigger block and copy once in a while)
Insert or delete in the middle or at the front: O(n), because items shift
Search for a value in an unsorted array: O(n)

A string is an array of characters with extra rules. In Python, JavaScript and Java strings are immutable: you cannot change one character in place, every "change" builds a new string. Comparing or hashing a string costs time proportional to its length, so "O(1) lookup" really means O(1) for short keys.

Two habits that save you:

Decide whether your indices are 0-based and whether a range is inclusive (a[l..r]) or half-open (a[l:r], which excludes r). Most off-by-one bugs live here.
Think about the empty and one-element array before you write the loop.

Hash maps and hash sets

A hash map stores key → value pairs. A hash set stores just keys and answers "is this in here?".

How it works, simply: a hash function turns the key into a big integer; the table uses integer mod table size as the slot. Two different keys can land in the same slot (a collision); the table copes (by keeping a small list per slot, or by probing for a free slot) and grows when it gets crowded. With a good hash function:

Insert, lookup, delete: O(1) on average (worst case O(n) if everything collides, which good implementations make very unlikely)
Space: O(n)

Names in different languages: Python dict and set · JavaScript Map and Set · Java HashMap and HashSet · C++ unordered_map and unordered_set · Go map · Rust HashMap and HashSet.

Things to remember:

Keys must be immutable (hashable). In Python a tuple (2, 3) can be a key, a list [2, 3] cannot, because changing it would change its hash.
Do not rely on the order of a set, or of a map in languages that do not promise it. Sort before printing when order matters.
Ask for what you need only once: if k in d: d[k] hashes twice; d.get(k) hashes once.

Pattern 1, frequency counting. To count how often each item occurs, walk once and bump a counter per key. In Python that is collections.Counter; elsewhere, counts[x] = counts.get(x, 0) + 1.

Pattern 2, the seen-set (complement lookup). To find two numbers that add up to target, process the list left to right. For each x the partner you need is target - x. Ask the map "have I already seen that partner?". If yes, you are done. If no, remember x and move on. One pass: O(n) time, O(n) space, instead of trying all pairs in O(n²).

A Counter is a dict specialised for counting. Notice the sorted-letters key at the end: three different words share the same key. That idea powers the second lab.

from collections import Counter

# Pattern 1: frequency counting
text = "the quick brown fox jumps over the lazy dog and the quick cat"
counts = Counter(text.split())
print("the appears", counts["the"], "times")
print("two most common:", counts.most_common(2))
print("a word that never appears:", counts["zebra"])   # a Counter returns 0, no KeyError

# A key must be hashable: a tuple works, a list does not.
visited = {(0, 0), (0, 1)}
print((0, 1) in visited, (5, 5) in visited)
try:
    visited.add([1, 2])
except TypeError as err:
    print("lists cannot be keys:", err)

# Two words are anagrams exactly when their sorted letters are equal.
for word in ["listen", "silent", "enlist", "google"]:
    print(word, "->", "".join(sorted(word)))

Open in Code Lab

Lab exercise 1

JavaScript (Node.js)Graded in Code Lab

Two-sum. Find two different positions whose values add up to a target.

Input: the first line has n target. The second line has n integers (they may be negative or repeat). At least one valid pair exists.

Output: the two 0-based positions i j with i < j and a[i] + a[j] == target. If several pairs exist, print the pair with the smallest j, and for that j the smallest i. (A one-pass hash map gives exactly that.)

Example: input 4 9 and 2 7 11 15 prints 0 1 because 2 + 7 = 9.

Use a Map from value to the first index it appeared at. Check the partner before inserting the current value, so a value never pairs with itself.

Visible tests (6)

The example
The pair is at the end
The same value twice
Negative numbers and a zero target
Several pairs: the one that completes first
3,000 numbers

Example run

Input: 4 9 2 7 11 15
Expected output: 0 1

Starter code

const lines = require("fs").readFileSync(0, "utf8").split("\n");
const [n, target] = lines[0].split(" ").map(Number);
const a = lines[1].split(" ").map(Number);

// TODO: find i < j with a[i] + a[j] === target (smallest j, then smallest i).
// Walk j from left to right; keep a Map from value to the first index where it appeared.
// For each a[j], ask the Map for the partner target - a[j] BEFORE inserting a[j].
let i = 0;
let j = 0;

console.log(i + " " + j);

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Canonical keys and prefix sums

Pattern 3, canonical keys. To group things that are "the same up to rearranging", compute a canonical form that is identical for every member of a group, and use it as the map key. Two words are anagrams when their sorted letters are equal, so "tea", "eat" and "ate" all map to the key "aet". A dict from key to list of words then groups them in one pass. (Another common key: a tuple of letter counts.)

Pattern 4, prefix sums. If you must answer many questions of the form "what is the sum of a[l..r]?", don't loop each time. Precompute once:

prefix[0] = 0
prefix[i + 1] = prefix[i] + a[i]
sum(a[l..r]) = prefix[r + 1] - prefix[l]

Preparation is O(n), then every query is O(1). The idea extends: with a hash map from "prefix sum seen so far" to "how often", you can count subarrays with a given sum in a single pass. The same trick works with products, XOR and 2D grids.

Build the table once, then any range is one subtraction. Change a to your own numbers and check a few ranges by hand.

const a = [3, 1, 4, 1, 5, 9, 2, 6];

// prefix[i] = sum of the first i numbers
const prefix = [0];
for (const x of a) prefix.push(prefix[prefix.length - 1] + x);
console.log("prefix:", prefix.join(" "));

// sum of a[l..r], both ends included, in O(1)
function rangeSum(l, r) {
  return prefix[r + 1] - prefix[l];
}

console.log("a[2..5] =", rangeSum(2, 5));   // 4 + 1 + 5 + 9
console.log("a[0..7] =", rangeSum(0, 7));   // everything
console.log("a[3..3] =", rangeSum(3, 3));   // a single element

Open in Code Lab

Lab exercise 2

PythonGraded in Code Lab

Group the anagrams. Words are anagrams when they use exactly the same letters.

Input: the first line has n. The second line has n lowercase words separated by spaces. Words can repeat.

Output: one line per group. Inside a line, list the group's words sorted alphabetically (a repeated word appears as many times as in the input), separated by one space. Print the lines sorted by each line's first word.

Example: input 6 and eat tea tan ate nat bat prints

ate eat tea
bat
nat tan

Use a dict whose key is the word's sorted letters.

Visible tests (6)

The example
A single word
No anagrams at all
Repeated words stay repeated
Single letters
126 words in two big groups

Example run

Input: 6 eat tea tan ate nat bat
Expected output: ate eat tea bat nat tan

Starter code

import sys

data = sys.stdin.read().split()
n = int(data[0])
words = data[1:1 + n]

# TODO: group the words that are anagrams of each other.
# 1. Build a dict: key = "".join(sorted(word)), value = list of words with that key.
# 2. Sort the words inside each group, then sort the groups by their first word.
# 3. Print one group per line, words separated by a single space.
for word in words:
    print(word)

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Sliding window and two pointers

Pattern 5, sliding window. When the question is about a contiguous piece of an array or string ("longest substring such that...", "shortest run with sum at least..."), keep two indices, start and i, that mark a window. Grow the window by moving i; whenever the window breaks the rule, move start forward until it is valid again.

It looks like a loop inside a loop, but each index only moves forward: start and i each travel at most n steps, so the total work is O(n), not O(n²).

Longest substring without repeating characters. Keep a map from character to the last index where it was seen. When the next character c was last seen at position p inside the current window (p >= start), jump the window's start to p + 1. The window [start, i] never contains a repeat, so its length i - start + 1 is a candidate for the answer.

"abcabcbb"
 abc    -> window "abc" (3)
 abca   -> 'a' was at 0, start moves to 1 -> window "bca" (3)
 ...
answer 3

Two pointers is the cousin for sorted data: one pointer at each end, moving inward depending on a comparison. For example, "do two numbers in this sorted array add up to the target?" runs in O(n) with no hash map: if the sum is too small move the left pointer right, if too big move the right pointer left.

Watch the traps: a repeat that sits before the window must be ignored (the string "abba" catches that bug), and never let start move backwards.

Lab exercise 3

RustGraded in Code Lab

Longest run without a repeat. Read one line of text (it may contain spaces, and may be empty). Print the length of the longest contiguous substring in which no character appears twice.

Example: abcabcbb prints 3 (the substring abc). bbbbb prints 1. pwwkew prints 3 (wke).

Use the sliding window: remember the last index of every character in a HashMap<char, usize>, and when you meet a character already inside the window, move start just past its previous position, but never backwards.

Visible tests (6)

abcabcbb
pwwkew: the window restarts
Empty line
abba: a repeat before the window is ignored
Spaces count as characters
20,800 characters

Example run

Input: abcabcbb
Expected output: 3

Starter code

use std::io::Read;

fn main() {
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    let line = input.lines().next().unwrap_or("");

    // TODO: print the length of the longest substring of `line` with no repeated character.
    // Keep `start` (left edge of the window) and a HashMap<char, usize> with the last index of
    // each character; when a character repeats inside the window, move `start` just past it.
    let mut best = 0;
    for (i, _ch) in line.chars().enumerate() {

More lines in Code Lab: 4

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Quick quiz

Question 1 of 5

Why does Python raise an error for my_dict[[1, 2]] = 'x' but accept my_dict[(1, 2)] = 'x'?

Question 2 of 5

You solve two-sum with a hash map in one pass. What are the time and extra space?

Question 3 of 5

With the prefix array built once, how do you get the sum of a[l..r] (both ends included)?

Question 4 of 5

A sliding-window solution has a while loop inside a for loop. Why can it still be O(n)?

Question 5 of 5

Which key puts every anagram of a word in the same group?

Summary

An array gives O(1) access by index but O(n) inserts in the middle and O(n) searches when unsorted. Strings are arrays of characters, immutable in most languages.
A hash map / set gives O(1) average insert, lookup and delete. Keys must be immutable, and you should not depend on iteration order.
The patterns to recognise: frequency counting, seen-set / complement lookup (two-sum), canonical keys (anagrams), prefix sums (O(1) range sums), sliding window (longest/shortest contiguous piece) and two pointers (sorted data).
Many "try all pairs" solutions become one pass once you ask "what have I already seen that would help right now?".

Practice next: count how many subarrays have sum exactly k (prefix sums plus a hash map), find the first non-repeating character of a string, and check whether two strings are anagrams using a frequency table. Then continue with Linked Lists, Stacks & Queues, and Sorting & Binary Search.