Arrays & Hashing Problems

Seven classic interview problems — Two Sum, Contains Duplicate, Valid Anagram, Group Anagrams, Top K Frequent Elements, Product of Array Except Self and Longest Consecutive Sequence — solved from zero. For each one you will see the slow obvious idea, the one observation that makes it fast, the pseudocode, the Dart code, and an animation you can feed your own input. By the end you will recognise the "remember what you have seen" pattern in a new problem and know which tool (a Set, a Map, a counting array, or sorting) to reach for.

How to attack an array or hashing problem

Imagine you run a cloakroom and someone asks "is there already a red umbrella here?". If the coats hang in no order, you walk the whole rail every time somebody asks. If instead you keep a notebook with one page per colour, you flip straight to "red" and answer at once. The notebook costs paper (memory) but saves walking (time). Almost every problem on this page is that trade: spend some memory on a notebook so you never walk the rail twice.

A few words first, because every problem below uses them:

An array (in Dart, a List) is a row of numbered boxes. Box numbers (the index) start at 0. Reading box 5 is instant, but finding which box holds the value 7 means looking at the boxes one by one.
A hash set (Dart Set) is a bag of values that answers "is x in here?" in about one step on average. It does that by turning x into a box number with a hash function (a recipe that maps a value to a box), so it can jump straight to the right box. How that works inside is the subject of C11 · Hash Tables.
A hash map (Dart Map) is the same idea with a value attached to each key: "7 → index 3", "apple → 2 times". Every built-in method and its cost is in D27 · Set & Map methods.
O(n) ("order n") means the work grows in step with the input size n: twice the input, about twice the work. O(n²) means twice the input gives four times the work. O(1) means the work does not grow at all. The full story is in C03 · Growth of Functions.

The four-step plan

Write the brute force first. The obvious idea, usually "try every pair" or "try everything". It is often too slow, but it proves you understand the task and gives you a reference to test against.
Spot the repeated work. Ask: "what question does my inner loop keep asking?" In Two Sum the inner loop keeps asking "is my partner somewhere in this list?" — and it answers by scanning, again and again.
Trade memory for time. Store the answers to that repeated question in a Set or Map as you go, so each later question costs one lookup instead of a scan. This usually turns O(n²) into O(n) time, at the price of O(n) extra memory.
Check the edges. Empty input, one element, duplicates, negative numbers, very large values. Most wrong answers in interviews come from these, not from the main idea.

Here is step 1 for Two Sum (find two positions whose values add up to a target). Watch how often the same nums[i] is re-read while j walks right — that is the repeated work.

Read the constraints: they tell you the speed you need

Interview problems state input sizes. A typical computer does roughly 10⁸ simple steps per second, so the size of n tells you which running times can finish in about a second:

Largest n	Fits in ~1 s	Too slow
n ≤ 20	O(2ⁿ) — try every subset	O(n!) once n passes about 11
n ≤ 3 000	O(n²) = 9·10⁶	O(n³) = 2.7·10¹⁰
n ≤ 10⁵ to 10⁶	O(n log n) or O(n)	O(n²) = 10¹⁰ or more
n ≤ 10⁸	O(n) with a tiny constant	O(n log n) starts to hurt

When sorting helps

Sorting puts equal values next to each other and puts small values on the left and big ones on the right. That alone solves many problems: duplicates become neighbours, anagrams become identical strings, and a sorted list lets two pointers walk inward (the next lesson in this level, Step 13.2 · Two Pointers, is built on that). Sorting costs O(n log n) time but can need only O(1) extra memory if done in place, so it is the right choice when memory is tight or when the problem asks you to keep extra space at O(1). How sorting works is covered in C02 · Insertion & Merge Sort and C07 · Quicksort.

Counting arrays vs maps

Many problems need "how many times does each thing appear?". If the things are small whole numbers you know in advance — the 26 letters a–z, ages 0–150, digits 0–9 — a plain List<int> of counters is fastest: box c − 97 for letter code c (97 is the code of 'a'). If the things can be anything — words, negative numbers, huge numbers, emoji — use a Map. Same idea, different storage:

The pattern of this whole page: brute force → find the question the inner loop repeats → answer it from a Set, Map or counting array instead. Sorting is the backup tool when memory must stay small.

Two Sum

The task. You get a list of whole numbers nums and one more whole number target. Find two different positions i < j whose values add up to target, and return them as [i, j]. A position may not be used twice, but two positions may hold the same value. If no pair works, return an empty list. (If several pairs work, this version returns the first one it completes while reading left to right.)

Example 1

Input: nums = [4, 9, 2, 7], target = 9

Output: [2, 3]

Why: nums[2] + nums[3] = 2 + 7 = 9.

Example 2

Input: nums = [5, -3, 8, 1], target = 5

Output: [1, 2]

Why: −3 + 8 = 5. Negative numbers work exactly like positive ones.

Example 3

Input: nums = [6, 6], target = 12

Output: [0, 1]

Why: the same value at two different positions is allowed.

Constraints

2 ≤ n ≤ 10⁵
−10⁹ ≤ nums[i] ≤ 10⁹, duplicates allowed
−2·10⁹ ≤ target ≤ 2·10⁹

Speed you need: checking every pair is n(n − 1)/2 ≈ 5·10⁹ steps, about 50 seconds → need O(n) time, O(n) extra space. Sums reach 2·10⁹, which fits easily in Dart's 64-bit int.

You are at a party and want to find someone whose age plus yours makes exactly 50. The brute force is to ask every pair of guests. The smart way: as each guest walks in, they write their age and name on a board by the door. When you arrive at age 21, you only need to look at the board for "29". One glance, no interviews.

Brute force. Try every pair (the panel above): about n²/2 checks, so O(n²) time and O(1) extra space. Fine for n = 1 000 (half a million checks), hopeless for n = 10⁵.

Key insight. For each number x, its partner is fixed: need = target − x. So the inner loop is really asking one question — "have I already passed the value need, and where?" A Map from value to index answers that in one step.

Optimal approach. Walk the list once. For each position i: compute need, look it up in the map; if found, done; otherwise store nums[i] → i and move on. Looking up before storing guarantees a position is never paired with itself.

A second worked example, on the trickiest edge: the same value appears twice and the target is exactly double it.

Complexity. Time O(n) — one pass, and each map lookup or store is O(1) on average. Space O(n) — in the worst case every value goes into the map before the pair is found.

Input size → what is feasible. n ≤ 10⁴: even the brute force (5·10⁷ checks) passes. n = 10⁵ or more: only the one-pass map version fits in a second.

Common mistakes. (1) Storing nums[i] in the map before looking up need: with nums = [5, 1, 7] and target 10 you would "find" 5 + 5 using index 0 twice. (2) Returning the values instead of the positions. (3) Sorting the list first and then returning positions from the sorted copy — the indices no longer match the original list. (4) Using seen.containsKey(need) and then seen[need]!: correct, but two lookups; reading seen[need] once and testing for null does one.

Follow-ups interviewers ask.

The list is already sorted. Then you need no map at all: put one pointer at each end and move them inward (sum too small → move the left one right; too big → move the right one left). O(n) time and O(1) space. This two-pointer idea is the subject of Step 13.2 · Two Pointers, the next lesson in this level; the code is in the question bank below.
Return every pair of values, not just one. Count each value first, then pair x with target − x, taking care with x + x. See the bank.
Three numbers that sum to zero. Sort, fix one number, then run the sorted two-pointer search on the rest: O(n²).

The idea underneath: a hash map gives O(1) average lookup — C11 · Hash Tables builds one from scratch, and D27 · Set & Map methods lists the Dart calls used here.

Contains Duplicate

The task. Given a list of whole numbers, answer true if some value appears at least twice, and false if every value is different.

Example 1

Input: nums = [3, 1, 4, 1]

Output: true

Why: 1 appears at index 1 and at index 3.

Example 2

Input: nums = [10, 20, 30]

Output: false

Why: all three values are different.

Example 3

Input: nums = [-5]

Output: false

Why: one number cannot repeat. An empty list also gives false.

Constraints

0 ≤ n ≤ 10⁵
−10⁹ ≤ nums[i] ≤ 10⁹

Speed you need: all pairs ≈ 5·10⁹ steps is too slow; sorting is n log n ≈ 1.7·10⁶ (fine); a hash set is n = 10⁵ steps → O(n) time, O(n) extra space (or O(n log n) time and O(1) extra space by sorting in place).

A bouncer at a club stamps every guest's hand and keeps a guest list. When someone arrives, the bouncer checks the list: name already there → "you are a duplicate, you came in twice". Name not there → write it down and let them in. The bouncer never re-reads the whole queue; one look at the list per guest.

Brute force. Compare every pair: O(n²) time, O(1) space.

Key insight. The inner loop asks "have I seen this value before?". A Set remembers everything seen so far and answers in O(1) on average.

Optimal approach. One pass; for each x, if it is already in the set, answer true immediately; otherwise add it. In Dart, Set.add returns false when the value was already there, so the check and the insert are one call.

The sorting alternative. After sorting, equal values sit side by side, so one scan comparing neighbours finds a repeat. O(n log n) time; O(1) extra space if you are allowed to sort the caller's list in place (this version copies it to be polite, which costs O(n)).

Complexity. Set version: time O(n) on average (one pass, O(1) per add), space O(n) for the set. Sorting version: time O(n log n), extra space O(1) in place.

Input size → what is feasible. n ≤ 10³: anything works. n = 10⁵ to 10⁷: Set or sort. Memory-limited (say 10⁸ numbers, no room for a second copy): sort in place.

Common mistakes. (1) Writing nums.toSet().length != nums.length — correct and short, but it always builds the whole set even when the very first two numbers repeat; the loop can stop early. (2) Sorting the caller's list without being asked: the caller's data changes order behind their back. (3) Forgetting the empty list: the answer is false, and your code must not read nums[0].

Follow-ups interviewers ask. Duplicates only count when they are at most k positions apart (keep the latest index of each value in a Map). Values within t of each other and at most k apart (bucket the values by width t + 1). Return the first repeated value. All three are in the bank below.

Underlying ideas: C11 · Hash Tables (why add is O(1) on average) and C02 · Insertion & Merge Sort (the sorting alternative).

Valid Anagram

The task. Two words s and t made of lowercase letters a–z. Answer true if t uses exactly the same letters as s, each the same number of times, just in a different order (an anagram); otherwise false.

Example 1

Input: s = "night", t = "thing"

Output: true

Why: both are one each of g, h, i, n, t.

Example 2

Input: s = "apple", t = "paper"

Output: false

Why: same length, but apple has an l where paper has an r.

Example 3

Input: s = "ab", t = "abc"

Output: false

Why: different lengths can never be anagrams.

Constraints

1 ≤ |s|, |t| ≤ 5·10⁴
only lowercase English letters a–z

Speed you need: trying every rearrangement is n! (impossible), sorting both is n log n ≈ 8·10⁵ (fine) → best is O(n) time with O(1) extra space (26 counters, whatever n is).

Two friends each tip a bag of Scrabble tiles onto a table. To check whether the bags hold the same tiles, you do not try to arrange one into the other. You keep a tally sheet with 26 rows: for each tile from bag one add a stroke to its letter, for each tile from bag two remove a stroke. If every row ends at zero, the bags matched.

Brute force. For each letter of s, search t for an unused copy and cross it out: O(n²). Or sort both words and compare: O(n log n) — a fine answer, but not the best.

Key insight. Order does not matter, only how many of each letter. With only 26 possible letters, a List of 26 counters is a perfect "map" whose key is letter code − 97.

Optimal approach. If the lengths differ, answer false. Otherwise walk both words together: the letter from s adds 1 to its box, the letter from t takes 1 away. At the end every box must be 0.

Complexity. Time O(n) — one pass over both words plus 26 checks. Space O(1) — always exactly 26 counters, however long the words are.

Input size → what is feasible. Words up to 10⁶ letters: counting is instant. The sort-and-compare version also passes up to about 10⁶, just with more work.

Common mistakes. (1) Skipping the length check: then t.codeUnitAt(i) reads past the end of a shorter t, or "ab" vs "abb" slips through on a one-sided count. (2) Using two Sets instead of counts: {"a","b"} equals {"a","b"} for "aab" and "abb", which are not anagrams. (3) Assuming only a–z when the input can contain capitals, spaces or accented letters: then use a Map keyed by runes (Unicode code points) — see the bank, and string internals in D24 · String methods.

Follow-ups interviewers ask. Support any Unicode text (Map over runes). Find all anagrams of a short word inside a long text (slide a window of letter counts along the text). Group many words by anagram — the next problem.

Underlying idea: counting instead of comparing, the same trick as counting sort in C08 · Counting, Radix & Bucket Sort.

Group Anagrams

The task. Given a list of lowercase words, put words that are anagrams of each other into the same group. Return the groups. (This version lists groups in the order their first word appears, and keeps words inside a group in input order.)

Example 1

Input: words = ["stop", "pots", "bat", "tops", "tab", "cat"]

Output: [["stop", "pots", "tops"], ["bat", "tab"], ["cat"]]

Why: stop, pots and tops all use o, p, s, t once; bat and tab use a, b, t; cat is alone.

Example 2

Input: words = [""]

Output: [[""]]

Why: the empty word is a group of its own.

Example 3

Input: words = ["ab", "ba", "abc"]

Output: [["ab", "ba"], ["abc"]]

Why: abc has an extra letter, so it cannot join ab.

Constraints

1 ≤ number of words n ≤ 10⁴
0 ≤ word length L ≤ 100
lowercase a–z

Speed you need: comparing every pair of words is 5·10⁷ pair checks, each up to 100 steps (too slow) → need about O(n · L log L) time (sort each word once) or O(n · L) with a counting key, O(n · L) extra space.

A librarian files books by a label instead of reading them side by side. Here the label is "the word's letters in alphabetical order": stop, pots and tops all get the label opst. Every book with the same label goes on the same shelf. One look at each book, one shelf per label.

Brute force. Compare each word with every other word using the Valid Anagram check: O(n² · L).

Key insight. Give every word a key (a canonical form) that is identical for anagrams and different otherwise. Sorting the letters gives such a key. Then a Map from key to list of words does the grouping in one pass.

Optimal approach. For each word, compute its key by sorting its letters, and append the word to that key's list (creating the list the first time). Dart's putIfAbsent does "create if missing, then give it to me" in one call. A Dart Map literal remembers insertion order, so the groups come out in order of first appearance.

Complexity. Time O(n · L log L) — each of the n words is sorted once (L letters). Space O(n · L) — the keys and the groups hold every letter once more.

Input size → what is feasible. n = 10⁴ words of length 100: sorting keys is about 7·10⁶ steps (instant). Very long words (L = 10⁴): switch to a counting key (26 counts), which is O(L) per word — in the bank.

Common mistakes. (1) Using the set of letters as the key: "ab" and "aab" both give {a, b} but are not anagrams. (2) Building a counting key by gluing counts together without a separator: counts 1, 11 and 11, 1 both become "111". Put a comma between counts. (3) Using a List as a Map key in Dart: two different lists with equal contents are different keys, because List uses identity for ==. Turn the key into a String.

Follow-ups interviewers ask. Use a counting key so each word costs O(L) instead of O(L log L). Return only the largest group. Handle uppercase and spaces ("Dormitory" vs "dirty room") by normalising first.

Underlying ideas: sorting letters (C02 · Insertion & Merge Sort) and Map with list values (D27 · Set & Map methods, see putIfAbsent).

Top K Frequent Elements

The task. Given a list of whole numbers and a number k, return the k values that appear most often, most frequent first. You may assume the answer is unique (no tie at the cut-off). (When frequencies tie inside the answer, this version lists the value that appeared first in the input first.)

Example 1

Input: nums = [5, 5, 5, 2, 2, 9], k = 2

Output: [5, 2]

Why: 5 appears 3 times, 2 appears twice, 9 once.

Example 2

Input: nums = [8], k = 1

Output: [8]

Why: the only value is the most frequent.

Example 3

Input: nums = [4, -1, 4, -1, 4, 6], k = 2

Output: [4, -1]

Why: 4 three times, −1 twice; negative values are counted like any other.

Constraints

1 ≤ n ≤ 10⁵
−10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ k ≤ number of distinct values
the answer is unique

Speed you need: sorting the distinct values by count is O(n log n) ≈ 1.7·10⁶ (fine, but interviewers ask for better) → target O(n) time with buckets, O(n) extra space.

A teacher wants the k most popular lunch choices. First, a tally per dish (a Map). Then, instead of sorting the dishes, she sets out shelves labelled "chosen 1 time", "chosen 2 times", up to "chosen n times" (nobody can be chosen more than n times when there are n votes). Each dish goes on the shelf matching its tally. Reading shelves from the top down gives the most popular dishes first — no sorting needed.

Brute force. Count with a Map, then sort the distinct values by count: O(n log n). Correct, and a good first answer.

Key insight. Counts are whole numbers between 1 and n. Numbers in a small known range can be "sorted" by dropping them into buckets — the idea behind bucket sort — in O(n).

Optimal approach. (1) Count each value. (2) Make n + 1 buckets; put each value into the bucket numbered by its count. (3) Walk the buckets from n down to 1, collecting values until you have k.

Complexity. Time O(n) — counting is n steps, filling buckets is one step per distinct value, and the bucket walk visits n + 1 buckets. Space O(n) for the counts and the buckets.

Input size → what is feasible. n ≤ 10⁵: buckets or sorting both pass. n = 10⁷ in a stream with small k: a size-k min-heap uses only O(k) memory besides the counts — in the bank, and heaps are explained in C06 · Heapsort & Priority Queues.

Common mistakes. (1) Making only max count buckets but indexing by count n when every value is the same — off by one; n + 1 buckets (0 to n) is always safe. (2) Returning the counts instead of the values. (3) Using a max-heap of all distinct values: O(n log n) and O(n) heap memory — no better than sorting. The useful heap is a min-heap capped at size k, which throws away the weakest candidate each time.

Follow-ups interviewers ask. Use a size-k heap (better when k is tiny and the data is huge or streamed). Top k frequent words, with ties broken alphabetically. Top k when the counts change over time. All with code in the bank.

Underlying ideas: bucket sort in C08 · Counting, Radix & Bucket Sort; heaps in C06 · Heapsort & Priority Queues.

Product of Array Except Self

The task. Given a list nums, build a new list answer where answer[i] is the product of every number except nums[i]. You may not use division, and the work must be O(n).

Example 1

Input: nums = [2, 3, 4, 5]

Output: [60, 40, 30, 24]

Why: answer[0] = 3 × 4 × 5 = 60, answer[1] = 2 × 4 × 5 = 40, and so on.

Example 2

Input: nums = [-1, 2, 0, 4]

Output: [0, 0, -8, 0]

Why: every product that includes the 0 is 0; only position 2 skips it: −1 × 2 × 4 = −8.

Example 3

Input: nums = [0, 5, 0]

Output: [0, 0, 0]

Why: with two zeros, every product still contains at least one 0.

Constraints

2 ≤ n ≤ 10⁵
−30 ≤ nums[i] ≤ 30
every prefix and suffix product fits in a 32-bit int
division is not allowed

Speed you need: multiplying the n − 1 others for each i is n² = 10¹⁰ steps (too slow) → need O(n) time, O(1) extra space (the output list does not count).

People stand in a queue, each holding a number. To find "the product of everyone except me", each person can ask the person in front "what is the product of everyone ahead of you, times you?" — a running total passed backward — and separately the person behind "what is the product of everyone behind you, times you?". Left part times right part is "everyone except me". Two walks down the queue, no division.

Brute force. For each i, multiply all the others: O(n²). Using the total product and dividing by nums[i] would be O(n), but division is banned — and it breaks on zeros anyway.

Key insight. "Everything except i" = "everything left of i" × "everything right of i". Both are running products: a prefix product built left to right and a suffix product built right to left.

Optimal approach. First pass: write the prefix product (everything left of i) into answer[i]. Second pass, right to left: multiply answer[i] by the suffix product (everything right of i). Only two extra variables are used, so the extra space is O(1) besides the output.

Complexity. Time O(n) — two passes. Extra space O(1) — just prefix and suffix; the output list is required by the task and is not counted.

Input size → what is feasible. n = 10⁵ or 10⁶: two passes, instant. The brute force passes only up to about n = 10⁴ (10⁸ multiplications).

Common mistakes. (1) Updating prefix before writing it into answer[i]: then nums[i] sneaks into its own product. (2) Starting prefix at 0 instead of 1 — the product of "nothing" is 1, just as the sum of nothing is 0. (3) Ignoring overflow: in Dart native code int is 64-bit and silently wraps around past about 9.2·10¹⁸; on the web, numbers are JavaScript doubles and lose precision past 2⁵³. The constraints here keep every product small.

Follow-ups interviewers ask. Division is allowed: count the zeros (none: total ÷ nums[i]; one zero: only the zero's position is non-zero; two or more: all zeros). Answer the same question modulo a prime. Product of every range [l, r] — prefix products again. See the bank.

Underlying idea: prefix sums and products, the same running-total trick used for "subarray sum equals k" in the bank. List basics are in D26 · List methods.

Longest Consecutive Sequence

The task. Given an unsorted list of whole numbers, find the length of the longest run of consecutive values (like 7, 8, 9, 10) that all appear somewhere in the list, in any order. Repeated values count once. The work must be O(n).

Example 1

Input: nums = [8, 3, 10, 2, 9, 4, 7]

Output: 4

Why: 7, 8, 9, 10 are all present (length 4); 2, 3, 4 is only length 3.

Example 2

Input: nums = [5, 5, 6, 5]

Output: 2

Why: the run is 5, 6; the extra 5s do not make it longer.

Example 3

Input: nums = []

Output: 0

Why: no numbers, no run.

Constraints

0 ≤ n ≤ 10⁵
−10⁹ ≤ nums[i] ≤ 10⁹, duplicates allowed

Speed you need: sorting is n log n ≈ 1.7·10⁶, but the task asks for O(n) time → use a hash set, O(n) extra space.

Numbered tiles are scattered on a floor. To find the longest unbroken stretch, you would not start counting from every tile — from tile 9 you would recount 9, 10 that you already counted from 7. Instead, only start counting at a tile whose left neighbour (one less) is missing: that tile is the beginning of a stretch. Count rightwards from beginnings only, and every tile is counted once.

Brute force. For every number x, count upward x + 1, x + 2, … by scanning the list each time: O(n³) with list scans, O(n²) with a set but no "start" check. Sorting and scanning for runs is O(n log n) — a decent answer, but not the O(n) the task demands.

Key insight. Put every value in a Set for O(1) "is v present?". Then only begin counting at values x where x − 1 is not present. Each run is then walked exactly once, from its first value.

Optimal approach. Build the set. For each value x in the set: if x − 1 is in the set, skip x (it is in the middle of some run). Otherwise count x, x + 1, x + 2, … while they are present, and keep the best length.

Complexity. Time O(n) on average. The inner while looks scary inside a for, but it only runs from run starts, and the runs do not overlap — so across the whole program the while body runs at most n times in total. Space O(n) for the set.

Input size → what is feasible. n = 10⁵ to 10⁶: the set version is about 2n to 3n lookups. Without the "start only" check, a single long run of length n makes the work n²/2 — 5·10⁹ steps for n = 10⁵.

Common mistakes. (1) Forgetting the x − 1 check: the code still gives the right answer, but on input 1, 2, …, n it does n²/2 steps. (2) Looping over nums instead of the set: with many duplicates of a run start, the same run is walked many times. (3) Returning 1 for an empty list: the answer is 0.

Follow-ups interviewers ask. Return the run itself, not only its length (remember the best start). Numbers arrive one at a time and you must report the longest run after each arrival — keep run lengths at the two ends of each run in a Map (in the bank). Do it with union-find (merge x with x + 1).

Underlying idea: O(1) average membership tests from C11 · Hash Tables; Set methods in D27 · Set & Map methods.

Quiz

Interview questions

Variations and follow-ups of the seven problems above — the questions interviewers move to once you have solved the classic version. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow reference.

Cheat sheet

Problem	Pattern	Time	Space	Key trick
Two Sum	Map: value → index	O(n)	O(n)	Look up `target − x` before storing x
Contains Duplicate	Set membership	O(n)	O(n)	`Set.add` returns false on a repeat; sort for O(1) space
Valid Anagram	Counting array	O(n)	O(1)	s adds, t subtracts, all 26 boxes must end at 0
Group Anagrams	Map: canonical key → list	O(n · L log L)	O(n · L)	Key = sorted letters (or a comma-separated letter count)
Top K Frequent	Count + bucket by frequency	O(n)	O(n)	Counts are 1..n, so bucket instead of sorting; size-k min-heap for streams
Product Except Self	Prefix × suffix products	O(n)	O(1) extra	Write prefix first, then multiply by suffix on the way back
Longest Consecutive	Set + start-of-run check	O(n)	O(n)	Only count from x when x − 1 is missing

All times are average-case for hash-based structures; a hash table's worst case is O(n) per operation if every key collides (see question p01-q31 in the bank).