04 — Arrays & Hashing

The core idea

Almost every hashing solution in the 150 comes from one trade:

Spend O(n) memory to eliminate a nested loop.

Here's the shape. Suppose you want to find two numbers that add to 9 in [2, 7, 11, 15]. The obvious approach compares every pair:

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (nums[i] + nums[j] == 9) return new int[]{i, j};

That's O(n²) — for n = 10,000 it's 100 million comparisons.

Now notice what the inner loop is actually doing: searching for a specific value. At i = 0 (value 2), it's scanning for a 7. Searching is exactly what a hash map makes instant. So instead of scanning forward for the partner, remember everything you've already passed:

Map<Integer, Integer> seen = new HashMap<>();       // value -> index
for (int i = 0; i < nums.length; i++) {
    int need = 9 - nums[i];
    if (seen.containsKey(need)) return new int[]{seen.get(need), i};
    seen.put(nums[i], i);
}

One loop. O(n).

The general move: whenever an inner loop is searching, replace it with a lookup in something you built as you went.

Designing the key

A hash map answers "has something with property P appeared?" in O(1). All the design work is choosing what the key is. That choice is the whole problem.

When you're stuck, ask:

"What would I need to have already recorded, at this element, to answer in one step?"

That thing is your key.

Frequency counting

Counting occurrences is the most common single operation in this section.

Fixed small alphabet → use an array

When the problem says "lowercase English letters", there are only 26 possibilities. An array indexed by c - 'a' beats a HashMap: no hashing, no objects, just an array index.

// Valid Anagram: is t a rearrangement of s?
if (s.length() != t.length()) return false;      // different lengths, done

int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;      // add for s
for (char c : t.toCharArray()) count[c - 'a']--;      // subtract for t
for (int n : count) if (n != 0) return false;         // anything left over = mismatch
return true;

Why one array instead of two: if s and t have identical character counts, adding for one and subtracting for the other cancels everything to zero. Any non-zero slot means the counts differed.

Trace with s = "anagram", t = "nagaram":

All zeros → anagram. ✓

The length check first is not just an optimization — without it, "a" vs "aa" would leave a non-zero count anyway, but checking makes the intent explicit and exits early.

Arbitrary keys → use a map

Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.put(n, freq.getOrDefault(n, 0) + 1);

Set for membership

// Contains Duplicate
Set<Integer> seen = new HashSet<>();
for (int n : nums) {
    if (!seen.add(n)) return true;        // add returned false => already present
}
return false;

add returns false when the element was already there, so test-and-insert happens in one operation instead of a contains followed by an add. Small thing, but it reads better and halves the lookups.

Alternatives worth naming in the interview:

• Sort first, then check neighbours — O(n log n) time but O(1) extra space. The right answer if memory is constrained.
• Brute force pairs — O(n²). State it, reject it.

Offering the space/time trade unprompted is a strong signal.

Complement lookup (Two Sum)

Map<Integer, Integer> seen = new HashMap<>();   // value -> index
for (int i = 0; i < nums.length; i++) {
    int need = target - nums[i];
    if (seen.containsKey(need)) return new int[]{seen.get(need), i};
    seen.put(nums[i], i);                       // insert AFTER checking
}
return new int[]{};

Trace with nums = [2, 7, 11, 15], target = 9:

Why checking must come before inserting: if you insert first, then with target = 4 and nums[i] = 2, you'd find the 2 you just added and return [0, 0] — pairing an element with itself. Checking first guarantees any match came from a genuinely earlier index.

O(n) time, O(n) space. If the array were sorted, two pointers would solve it in O(1) space (07) — that choice between hashing and two pointers is decided entirely by whether the input has order you can exploit.

Canonical keys — grouping "the same" things

Group Anagrams: put ["eat","tea","tan","ate","nat","bat"] into groups of anagrams.

Two words belong together if they're anagrams. But you can't use the word as a key — "eat" and "tea" are different strings. You need a canonical form: a value that is identical for everything in the group.

Option A — sort the characters

char[] chars = word.toCharArray();
Arrays.sort(chars);
String key = new String(chars);          // "eat" -> "aet", "tea" -> "aet"

Both become "aet", so they land in the same bucket. Cost: O(k log k) per word, where k is word length.

Option B — a count signature

int[] count = new int[26];
for (char c : word.toCharArray()) count[c - 'a']++;
String key = Arrays.toString(count);     // "[1, 0, 0, 0, 1, ..., 1, ...]"

Anagrams have identical letter counts, so identical signatures. Cost: O(k) per word — no log k factor.

Full solution

Map<String, List<String>> groups = new HashMap<>();
for (String word : strs) {
    int[] count = new int[26];
    for (char c : word.toCharArray()) count[c - 'a']++;
    String key = Arrays.toString(count);
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
return new ArrayList<>(groups.values());

Option B is the stronger answer — mention that you chose it to drop the log k. Option A is more readable and perfectly acceptable; say which you're picking and why.

Prefix and suffix accumulation

The idea

When the answer at index i depends on "everything to the left" and "everything to the right", precompute both directions in advance. Each is one pass, so you replace an O(n²) recompute-per-element with O(n).

Product of Array Except Self

res[i] = the product of every element except nums[i], without using division.

Key insight: that product is (everything left of i) × (everything right of i).

int n = nums.length;
int[] res = new int[n];

// Pass 1: res[i] = product of everything strictly LEFT of i
res[0] = 1;                                   // nothing to the left of index 0
for (int i = 1; i < n; i++) {
    res[i] = res[i - 1] * nums[i - 1];
}

// Pass 2: multiply in the product of everything strictly RIGHT of i
int suffix = 1;                               // nothing to the right of the last index
for (int i = n - 1; i >= 0; i--) {
    res[i] *= suffix;
    suffix *= nums[i];
}
return res;

Trace with nums = [1, 2, 3, 4]:

After pass 1 (left products):

Pass 2, walking right to left:

Result: [24, 12, 8, 6]. ✓

Why this is O(1) extra space: the output array doesn't count as auxiliary space (the problem requires returning it), and suffix is a single variable. We avoided a second array by folding the suffix pass directly into the result.

The general prefix-sum form

Used by any "sum of a range" question:

int[] prefix = new int[n + 1];               // prefix[i] = sum of the first i elements
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

int sumOfRange = prefix[j + 1] - prefix[i];  // inclusive [i..j], in O(1)

Size it n + 1 with a leading zero. prefix[0] = 0 means "sum of nothing", which makes the subtraction work at i = 0 with no special case. This sizing convention removes essentially every off-by-one in prefix-sum code — adopt it by default.

Bucket sort by frequency

Top K Frequent Elements: return the k most common values.

The obvious approach sorts by frequency: O(n log n). A heap does O(n log k) (14). But there's an O(n) answer, and it comes from one observation:

A frequency can never exceed n. So instead of sorting by frequency, use the frequency itself as an array index.

// Step 1: count occurrences
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);

// Step 2: bucket[f] = all values that appear exactly f times
List<Integer>[] buckets = new List[nums.length + 1];
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
    int f = e.getValue();
    if (buckets[f] == null) buckets[f] = new ArrayList<>();
    buckets[f].add(e.getKey());
}

// Step 3: walk buckets from the highest frequency down
int[] res = new int[k];
int idx = 0;
for (int f = buckets.length - 1; f >= 0 && idx < k; f--) {
    if (buckets[f] == null) continue;
    for (int val : buckets[f]) {
        res[idx++] = val;
        if (idx == k) break;
    }
}
return res;

Trace with nums = [1,1,1,2,2,3], k = 2:

Frequencies: {1→3, 2→2, 3→1}

Buckets (index = frequency):

Walking down from index 6: nothing at 6, 5, 4. At 3 → take 1. At 2 → take 2. We have k = 2, stop.

Result: [1, 2]. ✓

Why it's O(n): counting is O(n), filling buckets is O(distinct values) ≤ O(n), and scanning buckets visits each of n + 1 slots at most once. No sorting anywhere.

The general trick: when the thing you'd sort by is a bounded integer, you can index by it instead of comparing. That's counting sort, and it's the reason this drops below O(n log n).

Set-based structural scanning

Longest Consecutive Sequence: given [100, 4, 200, 1, 3, 2], the longest run of consecutive integers is [1,2,3,4] — length 4. Required: O(n).

Sorting would work but costs O(n log n), which the problem forbids.

Naive hashing attempt: put everything in a set, then from each number walk upward counting. That's correct but O(n²) in the worst case — for [1,2,3,...,n] you'd walk the whole run starting from every element.

The fix — only start counting from a number that begins a run:

Set<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);

int best = 0;
for (int n : set) {
    if (set.contains(n - 1)) continue;      // n-1 exists, so n is NOT a run start — skip
    int len = 1;
    while (set.contains(n + len)) len++;    // walk the run upward
    best = Math.max(best, len);
}
return best;

Trace with {100, 4, 200, 1, 3, 2}:

Answer: 4. ✓

Why the continue guard makes it O(n): the inner while only ever runs from the start of a run. Each element is therefore visited by an inner walk at most once across the entire algorithm — the run containing it is walked exactly one time. Total inner-loop work is O(n), even though the code looks nested.

This is the same aggregate accounting argument as the monotonic stack (01).

Multi-dimensional keys (Valid Sudoku)

A Sudoku board has three constraint families: no repeat in a row, a column, or a 3×3 box. You need three separate key spaces.

Approach A — one set with tagged keys

Set<String> seen = new HashSet<>();
for (int r = 0; r < 9; r++) {
    for (int c = 0; c < 9; c++) {
        char v = board[r][c];
        if (v == '.') continue;
        if (!seen.add(v + "@row" + r) ||
            !seen.add(v + "@col" + c) ||
            !seen.add(v + "@box" + (r / 3) + (c / 3))) return false;
    }
}
return true;

Tagging keeps the three families from colliding: "5@row0" and "5@col0" are different strings, so a 5 in row 0 doesn't falsely conflict with a 5 in column 0.

The box index

box = (r / 3, c / 3)

Integer division maps a coordinate to its 3×3 block. Rows 0, 1, 2 all give 0 / 3 = 0, 1 / 3 = 0, 2 / 3 = 0. Rows 3, 4, 5 give 1. And so on.

To get a single number 0–8 instead of a pair: (r / 3) * 3 + c / 3.

This coordinate-to-block mapping recurs across matrix problems — worth internalizing separately from Sudoku.

Approach B — bitmasks (faster)

int[] rows = new int[9], cols = new int[9], boxes = new int[9];

int bit = 1 << (board[r][c] - '1');          // digit 1..9 -> bit 0..8
int box = (r / 3) * 3 + c / 3;

if ((rows[r] & bit) != 0 || (cols[c] & bit) != 0 || (boxes[box] & bit) != 0) return false;
rows[r] |= bit;  cols[c] |= bit;  boxes[box] |= bit;

Each int stores nine yes/no flags in its bits. No string building, no hashing — just arithmetic. See 22 — Bit Manipulation.

Encoding with length prefixes

Encode and Decode Strings: turn a list of strings into one string, and back.

The naive idea is to join with a delimiter like #. It fails, because a payload string might itself contain # — the decoder can't tell a real delimiter from data. Any single delimiter has this problem; so does any fixed escape scheme you'd have to invent on the spot.

The fix: prefix each string with its length. The decoder reads the length, then takes exactly that many characters — it never has to search for a boundary, so no character is special.

// encode: ["abcd", "xyz"] -> "4#abcd3#xyz"
public String encode(List<String> strs) {
    StringBuilder sb = new StringBuilder();
    for (String s : strs) sb.append(s.length()).append('#').append(s);
    return sb.toString();
}

public List<String> decode(String s) {
    List<String> res = new ArrayList<>();
    int i = 0;
    while (i < s.length()) {
        int j = i;
        while (s.charAt(j) != '#') j++;            // find the end of the length digits
        int len = Integer.parseInt(s.substring(i, j));
        res.add(s.substring(j + 1, j + 1 + len));  // take exactly len characters
        i = j + 1 + len;                           // jump past this entry entirely
    }
    return res;
}

Trace decoding "4#abcd3#xyz":

Done — ["abcd", "xyz"]. ✓

Why # inside the payload is harmless: the first inner while only scans for # starting at a position where a length is expected. Once the length is read, the next len characters are consumed blindly. A # inside them is just data.

Raise that case proactively — it's the entire point of the question.

Complexity summary

Recognition checklist