Learn · DSA · Pattern 1
Arrays & Hashing
These are the two most-used building blocks in all of programming. Almost every piece of software you’ve ever touched is built from them. We’ll start from “what is it,” not from clever tricks.
Before we start
📋 What you’ll learn
- What an array really is — and how ArrayList relates to it
- What a hashmap really is, and why it is so fast
- Where both show up in real software you use every day
- The one pattern they unlock: “remember what you’ve seen”
- Why interview problems drill this exact skill
✅ After this you’ll be able to
- Explain arrays and hashmaps to someone else in plain words
- Recognise when a problem is secretly a hashmap problem
- Turn a slow O(n²) scan into a fast O(n) solution
- Solve the whole Arrays & Hashing family of problems
Why you’re learning it: arrays and hashmaps are the foundation half of all data structures stand on. Nail these two and a huge chunk of DSA — and of real backend work — suddenly makes sense. This is not a box to tick; it’s bedrock. ⏱️ ~30–40 min to read, a few days to truly own through practice.
Part 1 · What is an Array?
Picture a row of numbered lockers bolted together in a line. Each locker holds one thing, and each has a number painted on it: 0, 1, 2, 3… That’s an array. A fixed line of slots, each holding a value, each reachable by its number (called the index).
20
71
112
153
Indices start at 0, not 1. So the first locker is index 0, the second is index 1. (Everyone trips on this at first — it’s normal.)
The superpower: if you know the locker number, you open it instantly. “Give me index 2” takes the same tiny time whether the array has 10 items or 10 million. We call that O(1) — constant time. Free.
The weakness: if you don’t know the number and have to find a value — “which locker has the 11?” — you have to open lockers one by one until you find it. On a big array, that’s slow. We call that O(n) — it grows with the size.
One more thing: a classic array has a fixed size. You decide “20 lockers” when you build it. Need a 21st? You can’t just tack it on. (That limitation is exactly what ArrayList fixes — next.)
Arrays in real life — famous examples
This isn’t abstract. You use arrays every single day without noticing:
🖼️ Digital images
A photo IS an array of pixels — each cell holds a colour. A 1920×1080 image is a 2D array of ~2 million values. Turning up brightness = adding to every element.
🎵 Audio & music
A sound file is an array of thousands of samples per second. Playing = reading the array in order. Volume up = multiplying every element.
📊 Spreadsheets
Rows and columns are a 2D array. Cell at row 3, column 2 is just array[3][2].
🎮 Game boards
Chess, tic-tac-toe, Tetris — the grid is a 2D array. board[row][col] holds what sits on that square.
🔤 Text
A word is an array of characters. "HELLO" is [H,E,L,L,O] at indices 0–4. Reversing text = walking the array backwards.
📋 Lists you see daily
A playlist, a leaderboard, search results, your contacts screen — all arrays rendered in order.
A 2D array — the game board
Many real things are a grid: a spreadsheet, an image, a chess board. That’s just an array of arrays — you address a cell by row and column: board[row][col].
X
O
X
Part 1b · Array vs ArrayList — the family
Because a plain array can’t grow, most real code uses a growable version. In Java it’s ArrayList. Under the hood it’s still an array — but when it fills up, it quietly makes a bigger one and copies everything over. You just call .add() and never worry about size.
Array int[] | ArrayList | |
|---|---|---|
| Size | Fixed when created | Grows & shrinks freely |
| Speed | Fastest, least overhead | A touch more overhead |
| Use when | You know the size upfront | Size changes as you go |
| In Java | int[] a = new int[5]; | List<Integer> a = new ArrayList<>(); |
Rule of thumb: reach for ArrayList by default; drop to a raw array only when you know the exact size and want max speed.
Part 2 · What is a Hashmap?
An array finds things by position (a number). But often you want to find things by a label — a name, an id, a word. That’s a hashmap.
Think of a real dictionary: you look up a word and get its meaning. Or your phone contacts: a name gives you a number. A hashmap stores pairs of key → value, and — here’s the magic — it finds any key instantly, O(1), no matter how many it holds.
"Darshan"→9508839929
"Amit"→9876543210
"Priya"→9123456780
How is it instant? When you add a key, the map runs it through a little formula (a “hash”) that turns the key into a slot number — so it knows exactly which slot to check later. It never scans. You don’t need the formula’s internals; you just need to trust: put by key, get by key, instantly.
A hash set is the same thing with the values removed — just keys. It answers one question: “have I seen this before?” — instantly.
Hashmaps in real life — famous examples
📖 A dictionary
Look up a word (the key) → get its meaning (the value). You don’t read every page — you jump almost instantly. That’s a hashmap.
📱 Phone contacts
Name (key) → number (value). Type a name, the number appears at once — no scrolling through all contacts.
⚡ Caches
Your browser stores url → page. Visit again and it answers from memory instead of re-downloading. Speed comes from the instant lookup.
🗂️ Database indexes
So a database finds a user by email without scanning millions of rows — the index works like a hashmap.
🌐 DNS (the internet’s phonebook)
Maps a domain name (key) → an IP address (value). google.com → 142.250.x.x, instantly.
🔐 Logging in
username (key) → account (value). One lookup finds exactly who is signing in.
Array vs Hashmap — when to use which
| You want… | Use an Array | Use a Hashmap |
|---|---|---|
| Find by | position (0, 1, 2…) | a label / key (name, id) |
| Best at | ordered data, “the 3rd one” | “look this up by name” |
| Search cost | slow — scan, O(n) | instant, O(1) |
| Everyday example | a playlist in order | a phone book by name |
Part 3 · The pattern — “remember what you’ve seen”
Now the two ideas combine into the trick that solves a whole family of problems. Lots of array problems ask you to find something by re-scanning — which is slow, O(n²). The fix: as you walk the array once, remember what you’ve seen in a hashmap, so the “search” becomes an instant lookup.
Why it matters — the Big-O leap
Say you’re matching 80,000 records against 80,000 (this is real — it’s reconciliation, and your job):
O(n²) — every pair6,400,000,000
O(n) — hashmap80,000
6.4 billion operations vs 80 thousand. Same answer, 80,000× less work. That gap is why this pattern is everywhere.
Watch it work — the “Two Sum” problem
Find two numbers in [2, 7, 11, 15] that add up to 9. Walk once; for each number, ask “have I already seen the piece that completes it?”
index 0see 2 · need 7 (because 9 − 2 = 7)
memory:empty → haven’t seen 7. Remember: 2 lives at index 0.
index 1see 7 · need 2 (because 9 − 7 = 2)
memory:2 → idx 0→ 2 IS in memory! Answer = indices [0, 1]. ✅
One pass, no nested loop. The hashmap did the searching for free.
Where you’ll use it — beyond puzzles
- De-duplication everywhere: “have I already processed this?” — a hash set. (A payment webhook fires twice → stop the double charge.)
- Reconciliation / matching: build a map from one dataset, stream the other past it. This IS your Recon project and your EMV acceptance-testing work.
- Counting things: word frequencies, top-selling items, most-active users — count into a map, done.
Why we solve the questions
You don’t learn to swim by reading about water. Reading this page built understanding; only solving builds skill. Three honest reasons we do the problems:
- Recognition. Each problem is the same tool wearing a new costume. After 3–5, your brain starts shouting “that’s a hashmap!” on sight — that recognition IS the skill interviews test.
- Permanence. Pulling the answer out of your own head under a blank editor (retrieval) is the only thing that makes knowledge stick. Re-reading feels productive and teaches nothing.
- Reality. The interview doesn’t ask “have you seen this?” It asks “can you do it, right now, out loud?” Practice is the only bridge.
Now YOU do the reps
Focus mode: the core is yours. I won’t solve these — solving them is how they become permanent.
🗣️ The 2-minute explain test
After solving, close everything and say out loud, in 2 minutes: “What is an array, what is a hashmap, and how does remembering-what-I’ve-seen turn a slow O(n²) scan into a fast O(n) solution?” Teach it to the wall. Fluent? You own it. Stumble? That’s the signal to do one more rep — not a failure. Then log it in your Journal.
Permanent page. Re-visit day 1, 3, 7, 21 — but only after solving. Reading is not knowing; retrieval is.