Arrays & Hashing

Two Sum is the most-asked interview problem on the planet, and the brute-force answer gets you politely rejected. The interviewer isn’t testing whether you can write two loops — they’re testing whether you know the single most important trade in all of computing: spend memory to buy speed. This module is that trade, and the one data structure that makes it: the hash map.

The Goal

By the end of this module you can:

• Explain the memory-for-speed trade in one sentence, and name what you pay and what you get
• Explain why an array gives O(1) access but O(n) insert — from the memory layout, not from memorising
• Implement the three killer moves: seen-before (HashSet), count-things (frequency map), remember-where (value → index map)
• Solve Two Sum in O(n) and say exactly why the brute force is O(n²)
• Use getOrDefault, computeIfAbsent, and containsKey without looking them up
• Recognize an arrays-and-hashing problem from its wording in under 30 seconds

The Lesson

The foundational trade

Almost every “make it faster” move in DSA is the same move: store extra information now so you don’t have to search for it later. The brute-force version re-scans the data over and over. The fast version walks through once, writing down what it has seen in a structure with instant lookup. You burn memory (the map), you buy speed (no re-scanning).

That’s it. That’s the trade. Every section below is a variation of it.

Arrays — why index access is genuinely O(1)

An array is a single contiguous block of memory. int[] arr = new int[1000] reserves 1000 int-sized slots side by side, and the variable holds the address of slot 0.

That layout is why arr[742] is instant. The JVM doesn’t walk 742 slots — it computes:

address of arr[i] = base address + (i × size of one element)

One multiplication, one addition, done. Whether the array has 10 elements or 10 million, fetching by index costs the same. O(1) access isn’t a promise — it’s arithmetic.

But contiguity cuts both ways:

That last row is the problem hashing solves. “Is 7 in this array?” forces a full scan. Unless you’ve stored the answer somewhere with instant lookup.

The hash map — the most-used tool in interviews

Hashing in three sentences: a hash function takes a key (a string, a number, an object) and crunches it into a number called the hash code. The map uses that number to compute a bucket index — which, as you now know from arrays, is an O(1) jump. So instead of searching for your key, the map calculates where it lives and goes straight there.

Collisions in two: two different keys can land in the same bucket, so each bucket holds a small list (or tree) of entries and the map walks it comparing keys with equals. A good hash function spreads keys evenly, so those lists stay tiny and lookup stays O(1) on average.

flowchart LR
    A["key: chai"] -->|hashCode| B["number: 94623429"]
    B -->|mod table size| C["bucket index: 5"]
    C --> D["jump straight to bucket 5"]
    D --> E["compare with equals, return value"]

In JS terms: a HashMap is your plain object / Map, and a HashSet is Set — Java just makes you declare the types.

One contract you must respect, in three lines: if two objects are equals, they must return the same hashCode — otherwise the map files them in different buckets and containsKey lies to you. String and Integer get this right for free. Define it yourself only for custom key classes — full story in Core Java — Collections.

The three killer moves

Ninety percent of arrays-and-hashing problems are one of these three. Learn them as moves, not as problems.

Move 1 — Seen-before (HashSet). “Does this array contain a duplicate?” Walk once; if the set already has the element, you’ve answered.

import java.util.HashSet;

public class SeenBefore {
    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 1, 5};
        HashSet<Integer> seen = new HashSet<>();
        for (int n : nums) {
            if (seen.contains(n)) {
                System.out.println("Duplicate found: " + n);
                return;
            }
            seen.add(n);
        }
        System.out.println("All unique");
    }
}

Move 2 — Count-things (frequency map). “Are these two strings anagrams?” “Which element appears most?” Build a HashMap<K, Integer> of counts.

import java.util.HashMap;

public class CountThings {
    public static void main(String[] args) {
        String s = "engineering";
        HashMap<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        System.out.println(freq);   // {r=1, e=3, g=2, i=2, n=3}
    }
}

freq.getOrDefault(c, 0) + 1 is the line you’ll write a thousand times: “give me the current count, or 0 if you’ve never seen it, then add one.”

Move 3 — Remember-where (value → index map). This is Two Sum. “Find two numbers adding to target” brute-forced is: for every element, scan the rest for its partner — O(n²). The killer move: walk once, and for each element ask “have I already seen my partner?” The map remembers every value and where it was.

import java.util.HashMap;

public class TwoSum {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        HashMap<Integer, Integer> seenAt = new HashMap<>();  // value -> index
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seenAt.containsKey(need)) {
                System.out.println("Indexes: " + seenAt.get(need) + " and " + i);
                return;
            }
            seenAt.put(nums[i], i);
        }
        System.out.println("No pair");
    }
}

Note the order: check first, then store. That’s what stops target = 8, nums[i] = 4 from matching an element with itself.

The bonus move — group-by-key. “Group the anagrams together.” The trick is designing a key such that things that belong together get the same key. For anagrams: sort the letters — "eat", "tea", "ate" all become "aet".

import java.util.*;

public class GroupAnagrams {
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        HashMap<String, List<String>> groups = new HashMap<>();
        for (String w : words) {
            char[] letters = w.toCharArray();
            Arrays.sort(letters);
            String key = new String(letters);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
        }
        System.out.println(groups.values());
        // [[eat, tea, ate], [bat], [tan, nat]]
    }
}

computeIfAbsent(key, k -> new ArrayList<>()) means “give me the list for this key — and if there isn’t one yet, create it first.” It replaces four lines of if-null boilerplate.

The complexity win — always show it

For n = 100,000: the O(n²) Two Sum does ~10 billion pair checks; the map version does 100,000. That’s the difference between “time limit exceeded” and instant — and in production, between a request that times out and one that returns in milliseconds.

Traps and edge cases

• Check before you store in Two Sum, or an element pairs with itself.
• Duplicates are legal input. {3, 3} with target 6 must work — it does, because index 0 is stored before index 1 checks.
• Never use == to compare keys. Integer and String need equals; == compares references and only sometimes works (small-integer caching makes it pass in tests and fail in production).
• Don’t mutate an object while it’s a key. Its hash code changes, and the map can no longer find it.
• Empty input — your loop should naturally do nothing and fall through to the “not found” path. Confirm it does.

See It Move

Watch the map fill up as Two Sum walks the array — the moment the answer appears, it’s because the map already held the partner.

Step through it and notice:

• Each step does exactly one lookup and one insert — that’s why the whole thing is one pass.
• The “found it” step never scans anything; it asks the map one question.
• The map’s size grows only as far as the answer — early exits do even less work.
• Replay it and predict, before each step, what need will be. When you’re right five times in a row, you own this pattern.

Spot The Pattern

The skill being trained: read a problem, and within 30 seconds know it’s a hashing problem. These phrases are the giveaways:

Where It Runs In Real Life

Redis — a giant hash map with a network cable. The cache that sits in front of nearly every serious backend (including the ones powering your UPI apps) is, at its core, exactly the structure you just built: keys hashed to buckets, O(1) get and set. When you hear “cache hit,” that’s containsKey returning true at datacentre scale.

Dedup in data pipelines. Payment processors see the same webhook delivered twice, the same event logged twice. The fix is your Move 1: keep a set of processed transaction IDs, drop anything already seen. Done wrong, a customer gets charged twice.

Database hash indexes. When a DB index uses hashing, WHERE user_id = 42 becomes a hash-and-jump instead of a scan — the same index-math-beats-searching idea, applied to millions of rows.

Session stores. Every logged-in user on a website is an entry in a map: session token → user data. Each incoming request does one O(1) lookup to answer “who is this?” — at the rate of thousands of requests per second.

Counting in analytics. “Top 10 products today,” “requests per endpoint,” “error counts per service” — every dashboard number starts life as map.put(key, map.getOrDefault(key, 0) + 1) running over an event stream.

Build This

You’re building TxnAnalyzer — a transaction-stream analyzer that uses all three killer moves on one dataset. Type it yourself, in the terminal, no IDE.

1. Create a folder txnanalyzer, and inside it TxnAnalyzer.java:

import java.util.*;

public class TxnAnalyzer {

    public static void main(String[] args) {
        // txnIds[i] is the id of transaction i; amounts[i] its value in rupees
        String[] txnIds = {"T1", "T2", "T3", "T2", "T4", "T5", "T3"};
        int[] amounts   = {500,  1200, 250,  1200, 800,  250,  250};

        findDuplicateIds(txnIds);
        countAmounts(amounts);
        findPairSummingTo(amounts, 1050);
    }

    // Move 1: seen-before
    static void findDuplicateIds(String[] ids) {
        HashSet<String> seen = new HashSet<>();
        for (String id : ids) {
            if (!seen.add(id)) {   // add returns false if already present
                System.out.println("DUPLICATE txn id: " + id);
            }
        }
    }

    // Move 2: count-things
    static void countAmounts(int[] amounts) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int a : amounts) {
            freq.put(a, freq.getOrDefault(a, 0) + 1);
        }
        System.out.println("Amount frequencies: " + freq);
    }

    // Move 3: remember-where
    static void findPairSummingTo(int[] amounts, int target) {
        HashMap<Integer, Integer> seenAt = new HashMap<>();
        for (int i = 0; i < amounts.length; i++) {
            int need = target - amounts[i];
            if (seenAt.containsKey(need)) {
                System.out.println("Txns at index " + seenAt.get(need)
                        + " and " + i + " sum to " + target);
                return;
            }
            seenAt.put(amounts[i], i);
        }
        System.out.println("No pair sums to " + target);
    }
}

2. Compile and run:

javac TxnAnalyzer.java
java TxnAnalyzer

You should see T2 and T3 flagged as duplicates, the frequency map, and the pair 800 + 250.

3. Break it — self-pairing. In findPairSummingTo, move seenAt.put(...) to the top of the loop, before the check. Recompile, run with target 1000 added to main (findPairSummingTo(amounts, 1000)). Watch 500 pair with itself at the same index. Now you’ve seen why check-then-store matters. Fix it back.

4. Break it — the equals trap. In findDuplicateIds, change the check to compare with == by replacing the set: loop over a plain ArrayList<String> and use if (list.contains... ) vs a manual == scan. Build the == version, then change one id to new String("T2"). The == scan misses it; equals-based structures don’t. Delete the experiment, restore the set.

5. Extend it — group-by-key. Add a method groupByAmount that builds a HashMap<Integer, List<String>> mapping each amount to the list of txn ids with that amount, using computeIfAbsent. Print it. Expected: 250 maps to T3, T5, T3.

6. Extend it — top spender. Add parallel array String[] users and a method that finds which user appears most. That’s Move 2 plus one max-scan over entrySet().

Problems To Solve

The rule: solve until you can write the template from memory. If stuck 25 minutes, read the approach, close it, re-solve from scratch. Re-solving after reading is studying; copying while reading is typing.

Check Yourself

1. What exactly do you pay and what exactly do you get in the memory-for-speed trade?
2. Why is arr[i] O(1)? Answer with the formula, not the phrase “arrays are fast.”
3. Why is inserting at the front of an array O(n)?
4. Hashing in your own three sentences — key, hash code, bucket.
5. In Two Sum, why must you check the map before inserting the current element?
6. What does getOrDefault(key, 0) save you from writing?
7. Two objects are equals but return different hash codes. What goes wrong in a HashMap?
8. A problem says “find the pair” on a SORTED array with O(1) space. Why is a hash map the wrong answer?

Explain it out loud: Explain to an empty chair why Two Sum with a hash map is O(n) while the nested-loop version is O(n²) — walk through what the map remembers at each step and why that memory means you never look back. If you can’t say what seenAt contains after step 3 on {2, 7, 11, 15}, re-run the visualizer.

Still Unclear?

Copy-paste any of these into Claude — they deepen understanding, they don’t solve for you:

I know HashMap lookups are "O(1) on average." Walk me through what happens
when many keys collide into the same bucket, what Java does about long
buckets, and when O(1) quietly stops being true. Quiz me at the end.

Here is my Two Sum solution: [paste yours]. Don't fix or rewrite it.
Ask me a series of questions that test whether I understand WHY each line
is there — especially the order of the containsKey check and the put.

Give me five one-line problem descriptions. For each, I'll answer whether
it's seen-before, count-things, remember-where, or group-by-key, and which
Java structure I'd use. Tell me which I got wrong and why.

Why AI Can’t Do This For You

AI writes a perfect Two Sum in one second — every model has seen it a million times. But in the interview, the problem won’t be called Two Sum. It’ll be “find two transactions that net to zero” or “detect if any two sensors report the same reading,” and the only thing being measured is whether you see the pattern under pressure, with no prompt box in sight.

And in the job, the pattern arrives disguised as a ticket: “the reconciliation job is timing out.” Nobody tells you it’s an O(n²) pair-scan that needs a map. The engineer who recognizes burn-memory-to-buy-speed inside a vague production problem is the one who fixes it in an afternoon — that recognition only comes from drilling it into your own head.

Module done? Add it to today’s tracker