Hash map patterns: lookup, count, group

A hash map stores values under keys and finds the value of a key in about the same time however many keys it holds: O(1) on average. Coding problems use that one ability in four ways. Complement lookup asks whether the partner of the current item has been seen. Counting keeps how often each value has come up. Grouping files each item under a key that equivalent items share. Seen-before remembers what has already appeared. This lesson shows the four moves and the words in a problem that point to each, solves a first problem in full in four languages, and then looks at what the O(1) hides: its real cost, its worst case, the order in which each language hands the keys back, and the problems where sorting does better.

The four moves

A hash set is a hash map with keys and no values, so everything below works with either. The moves differ in what they store and in the question they ask the map about each new item. The words of a problem usually say which move it needs:

• Complement lookup asks “is this item’s partner already here?”, which turns “find two items that fit together” into one lookup per item. It stores value → position, or only a set of values when the position does not matter. For a target sum, the partner of x is target - x, and you ask the map for it before you store x.
• Counting asks “how often has this value come up?” and stores value → count. One pass that keeps a running count per value replaces a scan that counts each value again. Two collections hold the same items, repeats included, exactly when their counts are equal.
• Grouping asks “which earlier items are equivalent to this one?” and stores a canonical key → the list of items that share it. It works when you can compute a key that all equivalent items share and no others do. Words with the same letters share their letters in sorted order, so “ape” and “pea” both become “aep”.
• Seen-before asks “has this item come up before?”, and it is the simplest move: a set of everything read so far, or value → first position. It finds repeats, stops a search from visiting the same state twice, and with positions stored it says where something first appeared.

Here is each move in a few lines of Python, on an input of its own:

# The four hash map moves, each on a small input of its own.
from collections import Counter, defaultdict

# 1. Complement lookup: which two amounts add up to the target?
amounts, target = [120, 45, 300, 75, 210], 255
index_of = {}  # amount -> where it was seen
for j, amount in enumerate(amounts):
    partner = target - amount
    if partner in index_of:
        print("complement lookup:", amounts[index_of[partner]], "+", amount, "=", target)
        break
    index_of[amount] = j

# 2. Counting: how many votes did each drink get?
votes = ["tea", "coffee", "tea", "lassi", "tea", "coffee"]
print("counting:", Counter(votes).most_common())

# 3. Grouping: which codes use the same letters?
groups = defaultdict(list)  # sorted letters -> the codes that have them
for code in ["ape", "tan", "pea", "eat", "nat", "tea"]:
    groups["".join(sorted(code))].append(code)
print("grouping:", list(groups.values()))

# 4. Seen-before: which scan is the first to repeat an earlier code?
seen = set()
for j, code in enumerate([4417, 902, 3310, 902, 4417]):
    if code in seen:
        print("seen-before: scan", j, "repeats code", code)
        break
    seen.add(code)

complement lookup: 45 + 210 = 255
counting: [('tea', 3), ('coffee', 2), ('lassi', 1)]
grouping: [['ape', 'pea'], ['tan', 'nat'], ['eat', 'tea']]
seen-before: scan 3 repeats code 902

Each line of the output comes from one move. At the amount 210 the map already holds its partner 45, so the pair is found in one pass. Counter is the standard library’s counting map; it answers 0 for a value it has never seen instead of raising an error, and most_common() lists the counts from high to low, ties in the order the values were first met. defaultdict(list) starts an empty list the first time a key is used, so the grouping loop never checks whether a group exists. The last move stops at scan 3, the first scan whose code was already in the set.

Which move does the problem need?

Read the question and ask what you must remember about the items you have already read. The chart asks it in four narrower forms, one after another:

The same input can need different moves. Given a day’s payments, “do any two of them add up to 1,000?” is complement lookup, “who was paid most often?” is counting, and “which payment repeats an earlier one exactly?” is seen-before. Some problems need two moves at once: the first character of a word that appears only once needs counts and the order in which characters first appeared. When no move fits, or the answer has to come out sorted, sorting the input is often the better start; the last section of this lesson says when.

A first problem, solved in full

Four examples, which become the first tests:

• [4417, 902, 3310, 902, 4417] → 3. Two codes repeat, but the scan at position 3 (code 902) comes before the one at position 4 (code 4417).
• [7, 8, 9] → -1: no code repeats.
• [5, 5] → 1: the second scan repeats the first.
• [] → -1: an empty log has no repeat.

Which “first”?

“The first repeated code” can be read two ways, and on the first example the two readings disagree. The first scan that repeats a code is at position 3, code 902. The code whose first scan came earliest, among the codes that repeat, is 4417, first scanned at position 0. This problem asks for the first reading, and the exercise at the end of this lesson asks for the second. When a statement leaves this open in a round, ask, and confirm with an example like this one: clarifying is the first step of the six-step method.

The brute force

Compare every scan with every scan before it and return the first position that matches an earlier one. That is n(n − 1)/2 comparisons when no code repeats: about 2 × 10¹⁰ for 200,000 scans, far beyond a time limit of a few seconds. Write it anyway, because it is obviously right, and keep it to check the fast versions.

Sorting, then neighbours

Sort the pairs (code, position). Equal codes become neighbours, and within a run of equal codes the positions come out in scan order. For each code that occurs more than once, the second pair of its run is its first repeat, so the answer is the smallest position among those second pairs. This takes O(n log n) time. It works, but it needs care: sorting loses the scan order, so the positions have to travel with the codes, and the minimum has to be taken over every run.

One pass with a set

Walk the scans in order with a set of the codes seen so far. For each scan, check whether its code is in the set first; if it is, that position is the answer, and if not, add the code and go on.

Why it is right comes down to one statement that holds every time the loop reaches a position j: the set holds exactly the codes of the scans at positions 0 to j − 1. So the check is true exactly when an earlier scan had the same code. The positions are examined in increasing order, so the first j at which the check is true is the first scan that repeats a code. If the loop ends without a match, no scan repeated an earlier one, and the answer is −1. Each scan costs one lookup and at most one insertion, so the whole pass is O(n) time on average, with O(n) extra memory for the set.

Here is the dry run on the first example:

The scan at position 4 is never read, which is also why the second repeat, 4417, cannot change the answer.

The code in four languages

def first_repeat(codes):
    """Position of the first scan whose code was scanned before, or -1."""
    seen = set()  # the codes of every scan before position j
    for j, code in enumerate(codes):
        if code in seen:
            return j
        seen.add(code)
    return -1


for codes in ([4417, 902, 3310, 902, 4417], [7, 8, 9], [5, 5], []):
    print(codes, "->", first_repeat(codes))

[4417, 902, 3310, 902, 4417] -> 3
[7, 8, 9] -> -1
[5, 5] -> 1
[] -> -1

// Position of the first scan whose code was scanned before, or -1.
function firstRepeat(codes) {
  const seen = new Set(); // the codes of every scan before position j
  for (let j = 0; j < codes.length; j++) {
    if (seen.has(codes[j])) return j;
    seen.add(codes[j]);
  }
  return -1;
}

for (const codes of [[4417, 902, 3310, 902, 4417], [7, 8, 9], [5, 5], []]) {
  console.log(JSON.stringify(codes), "->", firstRepeat(codes));
}

[4417,902,3310,902,4417] -> 3
[7,8,9] -> -1
[5,5] -> 1
[] -> -1

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class FirstRepeat {
    /** Position of the first scan whose code was scanned before, or -1. */
    static int firstRepeat(long[] codes) {
        Set<Long> seen = new HashSet<>(); // the codes of the scans before j
        for (int j = 0; j < codes.length; j++) {
            // add() returns false when the code is already in the set
            if (!seen.add(codes[j])) return j;
        }
        return -1;
    }

    public static void main(String[] args) {
        long[][] logs = {{4417, 902, 3310, 902, 4417}, {7, 8, 9}, {5, 5}, {}};
        for (long[] codes : logs) {
            System.out.println(Arrays.toString(codes) + " -> " + firstRepeat(codes));
        }
    }
}

#include <cstddef>
#include <iostream>
#include <unordered_set>
#include <vector>

// Position of the first scan whose code was scanned before, or -1.
long first_repeat(const std::vector<long long>& codes) {
    std::unordered_set<long long> seen;  // the codes of the scans before j
    for (std::size_t j = 0; j < codes.size(); ++j) {
        // insert() returns a pair whose bool is false when the code was there
        if (!seen.insert(codes[j]).second) return static_cast<long>(j);
    }
    return -1;
}

int main() {
    const std::vector<std::vector<long long>> logs = {
        {4417, 902, 3310, 902, 4417}, {7, 8, 9}, {5, 5}, {}};
    for (const auto& codes : logs) {
        std::cout << '[';
        for (std::size_t i = 0; i < codes.size(); ++i) {
            std::cout << (i ? ", " : "") << codes[i];
        }
        std::cout << "] -> " << first_repeat(codes) << '\n';
    }
}

from session import run, versions

# FirstRepeat.java run as one source file; first_repeat.cpp built with
# the address and undefined-behaviour sanitizers on.
versions("java -version", "clang++ --version")
run("""
java FirstRepeat.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined first_repeat.cpp -o first_repeat
./first_repeat
""")

# openjdk version "27"
# Apple clang version 21.0.0 (clang-2100.3.34.2)
$ java FirstRepeat.java
[4417, 902, 3310, 902, 4417] -> 3
[7, 8, 9] -> -1
[5, 5] -> 1
[] -> -1
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined first_repeat.cpp -o first_repeat
$ ./first_repeat
[4417, 902, 3310, 902, 4417] -> 3
[7, 8, 9] -> -1
[5, 5] -> 1
[] -> -1

All four print the same answers for the four examples. Java and C++ fold the check and the insertion into one call. Java’s Set.add leaves the set unchanged and returns false when the element is already there, and in C++ the bool in the pair that insert returns says whether the insertion took place, so !seen.add(code) and !seen.insert(code).second both mean “this code was scanned before”. In Python and JavaScript the check is a separate lookup (in, has). It costs one more hash per scan and reads more plainly. The same pass in Go uses a map[int64]bool: the specification says that reading a key the map does not contain gives the zero value, false, so seen[code] is the check.

Test it against the brute force

# The repeated ticket three ways, plus one common slip, checked against
# the brute force on 1,000 random scan logs.
import random


def brute_force(codes):  # O(n^2): every scan against every earlier scan
    for j in range(len(codes)):
        for i in range(j):
            if codes[i] == codes[j]:
                return j
    return -1


def by_sorting(codes):  # O(n log n): equal codes end up side by side
    pairs = sorted((code, j) for j, code in enumerate(codes))
    best = -1
    for (code_a, _), (code_b, j) in zip(pairs, pairs[1:]):
        if code_a == code_b and (best == -1 or j < best):
            best = j
    return best


def with_set(codes):  # O(n) on average: remember the codes scanned so far
    seen = set()
    for j, code in enumerate(codes):
        if code in seen:
            return j
        seen.add(code)
    return -1


def add_then_check(codes):  # the slip: adds the code first, so it finds itself
    seen = set()
    for j, code in enumerate(codes):
        seen.add(code)
        if code in seen:
            return j
    return -1


rng = random.Random(41)  # a fixed seed: every run checks the same logs
logs = [[rng.randint(1, 6) for _ in range(rng.randint(0, 8))] for _ in range(1000)]
logs.sort(key=len)  # the shortest first, so that the first failure is a small one
with_repeat = sum(brute_force(codes) != -1 for codes in logs)
print(f"{len(logs):,} logs, {with_repeat} with a repeated code")
for solve in (by_sorting, with_set, add_then_check):
    name = solve.__name__
    bad = next((c for c in logs if solve(c) != brute_force(c)), None)
    if bad is None:
        print(f"{name:>14}: same answer as the brute force on every log")
    else:
        got, want = solve(bad), brute_force(bad)
        print(f"{name:>14}: wrong on {bad}: {got} instead of {want}")

1,000 logs, 577 with a repeated code
    by_sorting: same answer as the brute force on every log
      with_set: same answer as the brute force on every log
add_then_check: wrong on [5]: 0 instead of -1

The program builds 1,000 random scan logs of up to 8 scans each, with codes from 1 to 6, so that most logs have a repeat. Sorting and the set agree with the brute force on every log. The fourth version adds each code to the set before it checks, so every code finds itself: on the one-scan log [5] it returns 0 instead of −1. Because the shortest logs are checked first, the first failure is also the smallest one, and it is a complete bug report. Adding before checking is the most common slip with this move, so it is worth one line of a test: a log with a single scan.

What O(1) on average costs

Measured: the three ways on 100,000 scans

Complexity classes say how the time grows, not how long it takes. Here are the three solutions on logs in which no code repeats, the slowest case for all of them, because each has to read every scan. The program also records the most memory the sort and the set allocated at any moment:

# The three ways of finding the first repeated scan, timed on logs in which
# no code repeats (the worst case: every way reads every scan), with the most
# memory that the sort and the set allocate.
import random
import time
import tracemalloc


def brute_force(codes):
    for j in range(len(codes)):
        for i in range(j):
            if codes[i] == codes[j]:
                return j
    return -1


def by_sorting(codes):
    pairs = sorted((code, j) for j, code in enumerate(codes))
    best = -1
    for (code_a, _), (code_b, j) in zip(pairs, pairs[1:]):
        if code_a == code_b and (best == -1 or j < best):
            best = j
    return best


def with_set(codes):
    seen = set()
    for j, code in enumerate(codes):
        if code in seen:
            return j
        seen.add(code)
    return -1


def best_ms(solve, codes, runs=3):
    """The fastest of a few runs, in ms (slower runs were disturbed)."""
    fastest = float("inf")
    for _ in range(runs):
        start = time.perf_counter()
        solve(codes)
        fastest = min(fastest, time.perf_counter() - start)
    return fastest * 1000


def peak_kib(solve, codes):
    """The most memory the call had allocated at any moment, in KiB."""
    tracemalloc.start()
    solve(codes)
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return peak / 1024


def pairs(n):
    """With no repeat, the brute force compares every pair of scans once."""
    return n * (n - 1) // 2


rng = random.Random(7)
print(f"Brute force, n = 1,000: {pairs(1_000):,} comparisons")
codes = rng.sample(range(10**9), 2_000)  # 2,000 different codes
ms = best_ms(brute_force, codes, runs=5)
print(f"Brute force, n = 2,000: {pairs(2_000):,} comparisons in {ms:.1f} ms")
big = 100_000
seconds = ms / 1000 * pairs(big) / pairs(2_000)
print(f"Brute force, n = {big:,}: {pairs(big):,} comparisons,")
print(f"  about {seconds:,.0f} s at that speed")
codes = rng.sample(range(10**9), big)
for name, solve in [("Sorting", by_sorting), ("Set", with_set)]:
    ms, kib = best_ms(solve, codes), peak_kib(solve, codes)
    print(f"{name}, n = {big:,}: {ms:.1f} ms, at most {kib:,.0f} KiB allocated")

Brute force, n = 1,000: 499,500 comparisons
Brute force, n = 2,000: 1,999,000 comparisons in 111.2 ms
Brute force, n = 100,000: 4,999,950,000 comparisons,
  about 278 s at that speed
Sorting, n = 100,000: 422.2 ms, at most 10,802 KiB allocated
Set, n = 100,000: 11.3 ms, at most 6,144 KiB allocated

Expect other times on your computer, and even between two runs on the same one. What should hold is this:

• Doubling the scans from 1,000 to 2,000 multiplies the brute force’s comparisons by four, exactly, since it compares every pair once. At 100,000 scans that is five billion comparisons, and at the speed measured for 2,000 scans the estimate runs to minutes.
• The set is many times faster than sorting at 100,000 scans, although both finish in under a second. Sorting compares about n log n pairs of tuples; the set hashes each code once and looks it up once.
• In Python the sort also needs more memory than the set, about 1.8 times as much in the recorded run, because it builds a (code, position) tuple for every scan and each tuple is an object of its own. In Java, C++ or Go, a sorted array of 64-bit codes takes 8 bytes per code, while a hash set also stores, for every code, at least a link inside its bucket and a share of the bucket array, so there the comparison usually goes the other way.

The memory figures come from tracemalloc, which traces the memory blocks that Python allocates. They count the extra memory each solution needed, not the list of codes it was given, and they are smaller in the browser, where Python runs as a 32-bit program and every reference takes 4 bytes instead of 8.

The worst case: keys that collide

The O(1) assumes that the hash function spreads the keys over the table. Python’s own table of costs says that its dict figures are averages, and that each of those O(1) operations becomes O(n) when all the keys share one hash value. This program makes the worst case happen on purpose, with a ticket class whose hash can be switched to one value for everyone:

# 2,000 different tickets go into a dict (ticket -> position) twice: once
# with a hash that spreads them out, once with a hash that is the same for
# every ticket. The class counts how often the dict compares two keys (==).
class Ticket:
    comparisons = 0

    def __init__(self, code, spread):
        self.code = code
        self.spread = spread

    def __hash__(self):
        # 7 for every ticket when spread is False: they all collide
        return self.code if self.spread else 7

    def __eq__(self, other):
        Ticket.comparisons += 1
        return self.code == other.code


for spread in (True, False):
    Ticket.comparisons = 0
    position = {Ticket(code, spread): code for code in range(2_000)}
    name = "spread hash" if spread else "same hash"
    count = Ticket.comparisons
    print(f"{name:>11}: {len(position):,} tickets stored, {count:,} comparisons")

spread hash: 2,000 tickets stored, 0 comparisons
  same hash: 2,000 tickets stored, 1,999,000 comparisons

With hashes that differ, the dict never had to compare two tickets with ==: a different hash already proves that two keys differ. With one hash for all, every new ticket was compared with every ticket stored before it: 1,999,000 comparisons, which is 2,000 × 1,999 / 2, exactly the work of the brute force. The hash map has turned back into the nested loop it was meant to replace.

This is not only a classroom case. Crosby and Wallach showed in 2003 that inputs chosen to collide could make the hash tables of real programs degenerate in exactly this way, and they did it to two Perl releases, the Squid web proxy and the Bro intrusion detection system. Python’s defence is in its data model: the hashes of str and bytes are salted with an unpredictable random value in each run, so an attacker cannot work out in advance which strings collide, and PEP 456 made SipHash the hash function behind them. Java’s HashMap documentation warns that many keys with the same hashCode() are “a sure way to slow down performance of any hash table”; when the keys are Comparable it may use their order to break ties.

The same table also assumes that hashing and comparing one key takes constant time. For a string key of length L, computing its hash reads all L characters, and so does comparing it with an equal string, so a set of n strings of length L costs O(n × L) to build, not O(n).

The order of the keys

Hashing scatters keys over a table, so the order in which a hash container lists them is a property of the container, not of your data. Each language promises something different:

# The same five city names in a set and in a dict, printed by three separate
# runs of Python. Each run gets another hash seed, as two runs on two days
# would; PYTHONHASHSEED fixes each seed here, so that the output can be kept.
import os
import subprocess
import sys

program = """
cities = ["pune", "agra", "kochi", "delhi", "surat"]
print("set: ", set(cities))
print("dict:", list(dict.fromkeys(cities)))
"""
for seed in ["1", "2", "3"]:
    run = subprocess.run(
        [sys.executable, "-c", program],
        env={**os.environ, "PYTHONHASHSEED": seed},
        capture_output=True,
        text=True,
    )
    for line in run.stdout.splitlines():
        print(f"seed {seed}, {line}")

seed 1, set:  {'pune', 'agra', 'delhi', 'surat', 'kochi'}
seed 1, dict: ['pune', 'agra', 'kochi', 'delhi', 'surat']
seed 2, set:  {'agra', 'surat', 'delhi', 'pune', 'kochi'}
seed 2, dict: ['pune', 'agra', 'kochi', 'delhi', 'surat']
seed 3, set:  {'delhi', 'surat', 'agra', 'kochi', 'pune'}
seed 3, dict: ['pune', 'agra', 'kochi', 'delhi', 'surat']

// Counting scans per ticket code twice: with a plain object and with a Map.
const scans = [4417, 902, 3310, 902, 58];
const asObject = {};
const asMap = new Map();
for (const code of scans) {
  asObject[code] = (asObject[code] ?? 0) + 1;
  asMap.set(code, (asMap.get(code) ?? 0) + 1);
}
const objectKeys = Object.keys(asObject);
const mapKeys = [...asMap.keys()];
console.log("object keys:", objectKeys.join(" "));
console.log("Map keys:   ", mapKeys.join(" "));
console.log("key types:  ", typeof objectKeys[0], "and", typeof mapKeys[0]);

object keys: 58 902 3310 4417
Map keys:    4417 902 3310 58
key types:   string and number

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class Order {
    public static void main(String[] args) {
        String[] cities = {"pune", "agra", "kochi", "delhi", "surat"};
        Map<String, Integer> hashed = new HashMap<>();
        Map<String, Integer> linked = new LinkedHashMap<>();
        for (String city : cities) {
            hashed.put(city, city.length());
            linked.put(city, city.length());
        }
        System.out.println("HashMap:       " + hashed.keySet());
        System.out.println("LinkedHashMap: " + linked.keySet());
    }
}

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> hashed;
    for (std::string city : {"pune", "agra", "kochi", "delhi",
                             "surat", "jaipur", "indore", "nagpur"}) {
        hashed[city] = static_cast<int>(city.size());
    }
    std::cout << "unordered_map:";
    for (const auto& [city, length] : hashed) std::cout << ' ' << city;
    std::cout << " (" << hashed.bucket_count() << " buckets)\n";
}

from session import run, versions

# Order.java once; order.cpp built with two compilers, which bring two
# different standard libraries.
versions("java -version", "clang++ --version", "g++-16 --version")
run("""
java Order.java
clang++ -std=c++23 -Wall -Wextra order.cpp -o order && ./order
g++-16 -std=c++23 -Wall -Wextra order.cpp -o order-gcc && ./order-gcc
""")

# openjdk version "27"
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# g++-16 (Homebrew GCC 16.2.0) 16.2.0
$ java Order.java
HashMap:       [kochi, pune, agra, surat, delhi]
LinkedHashMap: [pune, agra, kochi, delhi, surat]
$ clang++ -std=c++23 -Wall -Wextra order.cpp -o order && ./order
unordered_map: indore surat delhi jaipur pune kochi nagpur agra (11 buckets)
$ g++-16 -std=c++23 -Wall -Wextra order.cpp -o order-gcc && ./order-gcc
unordered_map: nagpur indore surat delhi kochi agra jaipur pune (13 buckets)

• Python: a dict lists its keys in insertion order, which the language has guaranteed since Python 3.7. A set records no order at all. For strings it even changes between runs: the data model documentation says that changing the hash values changes the iteration order of sets, and the salt is new in every run. Three seeds gave three different orders above; the dict was the same every time.
• JavaScript: a Map lists its keys in insertion order, as the language specification requires. A plain object does not: keys that look like array indices come first, in ascending numeric order, and then the other keys in the order they were created. The object also turned the numeric codes into strings, while the Map kept them as numbers. Note that the specification asks only that Map lookups be sublinear on average; it does not promise O(1).
• Java: the HashMap documentation makes no guarantee about the order, not even that it stays the same over time. A LinkedHashMap keeps the insertion order.
• C++: the standard does not say in which order an unordered_map lists its elements. In the recorded run, the same program printed eight cities in two different orders, because the two compilers bring two different standard libraries, libc++ with clang++ and libstdc++ with g++-16, which lay out their tables differently (11 and 13 buckets here).
• Go: the specification leaves the order of a loop over a map open and warns that it may change from one loop to the next, so even two loops over one map in one run may list the keys differently.

The rule for a coding round follows: never print the contents of a hash container in the order it lists them. Sort the keys first, or keep the order yourself with a dict, a Map or a LinkedHashMap where the language guarantees insertion order. Tests that compare such output with an expected string fail at random otherwise.

When sorting does better

Hashing is the default for lookups, counts and groups on unsorted data. Sorting first is the better choice when one of these holds:

• The answer has to come out sorted anyway, for example every repeated code in increasing order. A hash map would need a sort at the end in any case.
• You need neighbours, not exact matches: the two closest scores, the codes between a and b, the next larger value. A hash map can only answer “is exactly this key here?”.
• Memory is tight and the items are plain numbers in Java, C++ or Go, where a sorted array costs 8 bytes per 64-bit value and sorting can happen in place.
• The input may be built to collide, and you want a bound that holds for every input: sorting is O(n log n) whatever the values are.
• The input is already sorted. Then equal values sit side by side, and one scan or two pointers need no extra memory at all, as the two-pointers overview shows.

Interview questions

A hash set lookup is called O(1). In what sense is that true, and when does it stop being true? It is O(1) on average: the hash of a key picks one place in the table, so a lookup inspects only a few entries however many keys the table holds, as long as the hash spreads the keys evenly and the table grows as it fills. Growing copies every entry, so a few insertions cost O(n), but spread over all insertions the cost stays O(1) each, amortised. It stops being true when many keys share a hash value: every lookup then compares with all of them, and when every key hashes alike, each operation is O(n) and building the table is O(n²). A poor hash function or input chosen to collide causes that. Hashing and comparing the key cost time too: a string of length L costs O(L).

Can you print the contents of a hash map in the order you need without sorting? Only where the language promises an order. Python dicts and JavaScript Maps list their keys in insertion order, and so does Java’s LinkedHashMap. Python sets, Java’s HashMap, C++’s unordered_map and Go maps promise no order: Java’s documentation says the order may change over time, the Go specification says it may differ from one iteration to the next, and a Python set of strings changes its order between runs because string hashes are salted in every run. Plain JavaScript objects list integer-like keys in ascending numeric order before the other keys. When the output must be in a given order, sort it, or keep an insertion-ordered structure where the language guarantees one.

Key takeaways

• A hash map answers “is this key here, and what is stored with it?” in O(1) on average. Four moves use that: complement lookup, counting, grouping and seen-before.
• To pick the move, ask what you must remember about the items already read: a partner, a count, a group or a sighting.
• Seen-before in one pass: check, then add. The set holds exactly the earlier items, which is why the first match is the answer. Test the slip of adding first with a one-item input.
• Average O(1) is still work: hashing a string costs its length, and keys that all collide turn the map back into the O(n²) brute force.
• Rely on the order of a hash container only where the language promises one: Python dicts, JavaScript Maps and Java’s LinkedHashMap keep insertion order; the others promise nothing, so sort before you print.
• Sort instead when the output must be sorted, when you need neighbours or ranges, when memory is tight for plain numbers, or when you need a bound that holds for every input.