The Language Toolkit: Dynamic Arrays, Maps and Sets

Functions and Data Containers · 30 min

DSA · Foundations · Toolkit

Dynamic Arrays, Maps and Sets

Every language ships the same small box of containers. This lesson is about using them — what each one is for, what it costs, and why one hash map turns a nested loop into a single pass.

Count the letters in BANANA →
input · B A N A N A
→
counts · A 3 · N 2 · B 1

01 The idea

Stop writing the second loop

Whatever language you answer an interview in, you get the same handful of containers. Java calls them ArrayList, HashMap, HashSet, ArrayDeque, PriorityQueue. C++ calls them vector, unordered_map, unordered_set, deque, priority_queue. Python calls them list, dict, set, deque, heapq. Different names, the same five ideas.

How they are built inside is a later module. What you need first is what each one is for and what it costs, because the gap between a passing answer and a good one is usually one line. Instead of walking the array a second time to find out how many times a value appeared, you look the value up.

When a question asks how many times or have I seen this before, build a map or a set in one pass instead of scanning the data a second time.
Dynamic arrayA list that grows as you append to it, so you never declare a size. Reading by index is one step; appending is one step on average.
Hash mapA container of key → value pairs. Putting, getting and testing a key each take one step on average, whatever the key is.
Hash setA hash map with the values thrown away. It answers exactly one question: have I seen this value before?

02 Hand trace

Counting the letters in BANANA

Six letters: B A N A N A. You read them left to right and keep one map from letter to count. Every letter triggers the same two moves — look the key up, then either put it in at 1 or add 1 to what is already there. Follow A: it goes in at letter 2 and is bumped twice after that. The columns below are the map's keys, in the order they were created.

map keyBAN
after B A N111three new keys — each one put in with count 1
4th · A121A is already there → 1 becomes 2
5th · N122N is already there → 1 becomes 2
6th · A132A again → 2 becomes 3
result1321 + 3 + 2 = 6 letters · 3 keys · A wins

Six letters in, six map updates out — one per letter, and the string is never read a second time. The counts add back to 6, which is the check worth doing every single time. Reading off the winner then costs a walk over 3 keys, not 6 letters. Section 03 is this trace written as code, twice.

03 Two ways to count

26 slots, or a hash map

Both versions count the letters of B A N A N A and both report A with 3. The left one uses the letter itself as an array index. The right one hashes the letter. On this input the difference is not speed — it is what happens when the keys stop being letters.

Fixed array · one slot per letter

count = new int[26]          # all zerofor ch in s:    count[ch - 'A'] += 1     # 'B'-'A' is 1best = 0for i = 1 to 25:    if count[i] > count[best]: best = ireturn letter(best)         # 'A', seen 3

Hash map · any key at all

freq = empty mapfor each item in list:    freq[item] = freq.getOrDefault(item, 0) + 1best = nonefor (key, count) in freq:    if best == none or count > freq[best]: best = keyreturn best                # 'A', seen 3

These are not two algorithms. Both do exactly one update per item. The array finishes in O(n) flat; the map finishes in O(n) on average, because each of its n updates is only constant-time on average. The array is a hash map whose hash function is ch - 'A' — a hash so perfect that two different letters can never collide, which is why it needs no buckets and no worst case.

What the fixed array buys. Every update on line 3 is a single memory write into a block of 26 integers. There is no hashing to compute, no entry object to allocate, and the whole table fits in a cache line or two. When you are told the input is lowercase letters only, this is the answer an interviewer is fishing for.

What it costs. It only works when you can list every possible key in advance and that list is short — 26 letters, 10 digits, 256 ASCII values. The moment the keys are words, user IDs or arbitrary integers, 26 slots becomes four billion, and only the map survives.

Why the map's second loop is shorter. Line 5 on the left walks all 26 slots even though only 3 were ever touched, so it makes 25 comparisons. Line 5 on the right walks the 3 keys that actually exist and makes 2. The array pays for the alphabet; the map pays only for what turned up.

One place they disagree. Both use a strict >, so on a tie neither swaps — but "first" means different things. The array keeps the lowest index, so it reports the alphabetically earliest of the tied letters. The map keeps the earliest key it inserted, so it reports whichever tied letter showed up first in the input. On WWQQ the array says Q and the map says W. When a question has ties, say out loud which winner you are returning.

05 Cheat sheet

The toolkit, and what each piece costs

Container or operationReach for it whenCost
Dynamic array — ArrayList, vector, listYou need indexed access and do not know the size up frontget O(1) · append O(1) amortised
Insert or delete in the middle of oneAlmost never on purpose — everything after it shiftsO(n)
String builder — StringBuilder, "".join(parts), C++ string::+=You are assembling a string inside a loopO(n) for n pieces
+ or += on a Java or Python string inside a loopNever — this is the trap, not the tool. The string is immutable, so every step copies it wholeO(n²)
Hash map — HashMap, unordered_map, dictCount, group, or look something up by keyput / get / contains O(1) average
Hash map when the keys collide badlyThe worst case an interviewer will ask aboutO(n) per operation
Hash set — HashSet, unordered_set, setThe only question is "have I seen this before?"add / contains O(1) average
Built-in sort with a comparatorYou need an order the default does not give youO(n log n)
Stack, queue, deque — all ArrayDeque / dequeLast-in-first-out, first-in-first-out, or both endspush / pop / peek O(1)
Priority queue (heap) — previewYou repeatedly need the smallest or largest itempush / pop O(log n) · peek O(1)
O(1) is an average, not a promiseHash operations assume the keys spread out across buckets. A bad hash or a hostile key set collapses a map towards a list, which is why the honest answer is "constant on average".
No hash map hands you sorted orderJava's HashMap and C++ unordered_map give you an arbitrary order. A Python dict and Java's LinkedHashMap do promise insertion order — which still is not sorted order. Only TreeMap or std::map keeps keys sorted, at O(log n) per operation.
Space is the price you payA map costs O(k) extra memory for k distinct keys, plus an object per entry in most languages. That memory is what you are trading the second loop away for.

06 Where & why

When the map is the right answer, and when it is lazy

A hash map is the default answer to most counting and lookup questions and it is rarely wrong. It is just not always the cheapest thing available, and knowing where a plain array or a sorted scan beats it is what separates a memorised answer from an understood one.

Reach for it when…

The question says "how many times"Majority element, the mode of an array, a character histogram, word counts across a document. Every one of them starts with the same map you built for BANANA.
You are about to write a second loopIf the inner loop only asks "does this value appear somewhere else", a set replaces it outright and O(n²) becomes O(n).
The keys are not small integersWords, IDs, dates, coordinate pairs, whole objects. You cannot index an array by any of those. You can key a map by all of them.
You can spare O(k) memoryOn 10⁵ values with 10³ distinct ones the map holds a thousand entries and removes an entire pass. That trade is almost free.

Use something else when…

SituationBetter choiceWhy
The keys are exactly the 26 letters, or the 10 digitsint[26] or int[10]The index is the hash, so there is nothing to compute and nothing to allocate. No collisions means no worst case at all.
You need the keys back in sorted orderTreeMap, std::map, or sorting the key listNo hash map gives you sorted order — Java's is arbitrary, Python's is insertion order. A tree map keeps keys sorted, at O(log n) per operation instead of O(1).
You only ever want the smallest or largest, over and overPriority queueA map cannot hand you the minimum without scanning every key it holds. A heap peeks in O(1) and removes in O(log n).
The data is already sorted and you are hunting duplicatesA neighbour scanEqual values sit next to each other, so comparing each item with the one before it answers it in O(n) time and O(1) extra space. The set would buy nothing.
"I'd build a frequency map in one pass" is a complete first answer to a large slice of array and string questions. Say it, then say the cost out loud — O(n) time and O(k) extra space for k distinct keys — and say why you did or did not use an int[26] instead.

07 Interview questions

Answer these out loud

Each answer is about twenty seconds spoken. Give the direct answer first, then the reason, then the cost.

What is a dynamic array, and what does it cost to add to one?
A list that grows on its own — ArrayList in Java, vector in C++, list in Python. Reading by index is O(1) and appending to the end is O(1) amortised. Inserting or deleting in the middle is O(n), because every element after the gap has to shift.
Appending is O(1), but the memory underneath has a fixed size. What happens when it fills up?
It allocates a bigger block — usually double — copies everything across and carries on. That one append costs O(n), but it only happens after a run of n cheap ones, so the average per append stays constant. That is what amortised means: a rare expensive step paid for by many cheap ones.
Why is building a string with + inside a loop a problem?
Because strings are immutable in Java, Python and C#, so every + allocates a whole new string and copies the old one into it. Joining n pieces that way copies about n²/2 characters. Use a StringBuilder, collect the pieces in a list and join once, or use += on a C++ std::string, which appends in place.
What is a hash map, and why do we say its operations are O(1) "on average"?
It stores key → value pairs and finds a key by computing a hash of it rather than searching for it. Put, get and contains are O(1) on average. The qualifier matters because keys can collide into the same bucket: with a bad hash the map degrades towards a list and a lookup becomes O(n).
HashMap or HashSet — how do you choose?
Use a set when the only thing you need is "have I seen this before". Use a map when you need to remember something about the key — a count, an index, a list of items. A set is a map whose values you never read, so if you catch yourself storing a dummy value like true, you wanted a set.
Count how many times each letter appears in BANANA. What do you write, and what does it cost?
One pass with a map: for each character, freq[ch] = freq.getOrDefault(ch, 0) + 1. That gives A→3, N→2, B→1, and the counts add back to 6. Time is O(n) for n characters, extra space is O(k) for k distinct characters — here 6 and 3.
For letters you could use an int[26] instead of a map. Which do you pick?
int[26] when the alphabet is small and known in advance — 26 letters, 10 digits, 256 ASCII values — because the index is the hash, so there is no hashing cost, no entry object and no collision worst case. A hash map the moment the keys are words, IDs, negative numbers or anything you cannot enumerate. Both are one pass; only the constant factor and the memory shape change.
How do you check whether an array contains a duplicate?
Walk it once, adding each value to a hash set, and stop the first time a value is already there. That is O(n) time and O(n) extra space, and it usually stops early. If extra space is banned, sort first and compare neighbours — O(n log n) time and O(1) extra, but it destroys the original order.
You need to sort by something other than the natural order. How?
Pass a comparator to the built-in sort rather than writing a sort. Java: list.sort(Comparator.comparingInt(Person::getAge)). Python: list.sort(key=lambda p: p.age). C++: sort(v.begin(), v.end(), cmp). It is O(n log n) and already handles every edge case you would get wrong.
Stack, queue and deque — what is the difference, and what do you actually instantiate?
A stack is last-in-first-out, a queue is first-in-first-out, and a deque does both ends. In practice one class covers all three: ArrayDeque in Java, deque in C++ and Python. Push, pop and peek are all O(1). Java’s old Stack class is synchronised and slower, and interviewers notice when you still reach for it.
What is a priority queue for, and how is it different from keeping a sorted list?
It hands you the smallest — or largest — element on demand: O(log n) to push, O(log n) to pop, O(1) to peek. It does not keep everything sorted; it only guarantees the top. That is exactly right for "merge k sorted lists" or "always take the next-cheapest job", where the order of everything else never matters.
When would a hash map actually be the wrong tool?
When you need the keys in sorted order, because no hash map gives you that — use a TreeMap or sort the key list. When the array is already sorted, because comparing each item with the one before it finds duplicates in O(1) extra space. And when the keys are dense small integers, because a plain array beats the map on speed, memory and worst case all at once.

08 Practice problems

Six problems, one map

Every one of these is the BANANA pass with something different recorded in the value — a count, an index, a signature, a list. Solve them in order; the twist is the part worth thinking about.

First Non-Repeating Character

Easy
Given a string, return the first character that appears exactly once, or the underscore character if every character repeats.
Follow-up
A finished map tells you which characters are unique but not which one came first, because map order is not input order. The count for the character at index 0 is not even known until the last character has been read.
Show the hint
Nothing in the question limits you to reading the string once.

Two Sum

Easy
Given an array of numbers and a target, return the two indices whose values add up to the target, assuming exactly one such pair exists.
Follow-up
The value you store is not a count. The question asks for positions, so the map has to remember where each number was — and you have to decide whether to look a number up before or after storing it, because those two orders give different answers when a number pairs with itself.
Show the hint
For the number in front of you there is exactly one number that would complete the pair, and you can compute it.

Valid Anagram

Medium
Given two strings, return true if one is a rearrangement of the other.
Follow-up
Sorting both strings answers it in O(n log n), but counting answers it in O(n). The work is then in choosing the test on the counts that proves "anagram" — and doing it without building and comparing two whole maps.
Show the hint
Compare the lengths before you count anything; once they match, one counter table is enough for both strings.

Group Anagrams

Medium
Given a list of words, return the groups of words that are rearrangements of one another.
Follow-up
The map key is not a word — it is a signature you have to design, and every word in a group must produce exactly the same signature. Get the signature wrong and the grouping silently collapses.
Show the hint
Two words are anagrams exactly when they hold the same letters in any order, so you need something built from a word that throws the order away and keeps nothing else.

Top K Frequent Elements

Medium
Given an array and a number k, return the k values that appear most often.
Follow-up
Counting is the easy half. Ordering the distinct keys is the real work, and fully sorting them does more than the question asks when k is much smaller than the number of distinct keys.
Show the hint
Once the map is built the original array is irrelevant — you are picking k out of the distinct keys, and that list is usually far shorter.

Longest Run of Distinct Values

Hard
Given an array, return the length of the longest contiguous stretch that contains no repeated value.
Follow-up
A set tells you a value has been seen but not where, so on a repeat you would have to throw the set away and restart — that is O(n²). Staying at one pass means the container has to remember a position, not just a presence.
Show the hint
Track the left edge of the current stretch and never let it move backwards — a value last seen before the left edge is not a repeat inside the stretch.