Sets and Maps

The problem they solve

Checking “have I seen this value before” by scanning an array is O(N). Doing that inside a loop makes the whole solution O(N²), which fails once N passes a few thousand.

A hash set answers the same question in O(1) average time. That single change turns many O(N²) solutions into O(N).

HashSet

Stores distinct values, no order.

Set<Integer> seen = new HashSet<>();

for (int i = 0; i < n; i++) {
    if (seen.contains(a[i])) {
        System.out.println("duplicate: " + a[i]);
    }
    seen.add(a[i]);
}

add returns a boolean — true if the value was new, false if it was already present. That lets you combine the test and the insert:

if (!seen.add(a[i])) {
    // a[i] was already in the set
}

HashSet operations

HashMap

Associates each key with a value. The dominant use is counting.

Map<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < n; i++) {
    count.merge(a[i], 1, Integer::sum);
}

merge(key, 1, Integer::sum) inserts 1 if the key is absent, otherwise adds 1 to the existing value. The equivalent longer form:

count.put(a[i], count.getOrDefault(a[i], 0) + 1);

Both are correct. getOrDefault is worth knowing because it also covers reads:

int timesSeen = count.getOrDefault(x, 0);   // 0 rather than null when absent

int c = count.get(x);        // NullPointerException if x is absent

Iterating a map:

for (Map.Entry<Integer, Integer> e : count.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}

Use entrySet rather than iterating keySet and calling get for each key — it avoids a second lookup per entry.

When an array is better

If the keys are integers in a known, reasonably small range, use an array. It is faster, uses far less memory, and has no hashing overhead at all.

// values guaranteed between 1 and 100,000
int[] count = new int[100_001];
for (int i = 0; i < n; i++) {
    count[a[i]]++;
}

Values can be shifted into range when they are negative but bounded:

// values between -1000 and 1000
int[] count = new int[2001];
count[a[i] + 1000]++;

TreeSet and TreeMap

The sorted variants. Operations cost O(log N) instead of O(1), and in exchange you get order.

TreeSet<Integer> s = new TreeSet<>();
s.add(5); s.add(1); s.add(9);

System.out.println(s.first());       // 1  — smallest
System.out.println(s.last());        // 9  — largest
System.out.println(s.ceiling(6));    // 9  — smallest element >= 6
System.out.println(s.floor(6));      // 5  — largest element <= 6
System.out.println(s.higher(5));     // 9  — strictly greater
System.out.println(s.lower(5));      // 1  — strictly less

ceiling and floor are the reason to use a TreeSet. “What is the nearest value to X that I have already seen” is a question a HashSet cannot answer, and it comes up frequently in harder problems.

These methods return null when nothing qualifies, so check before unboxing:

Integer c = s.ceiling(x);
if (c != null) { /* use c */ }

Sets of pairs and coordinates

Grid problems often need “have I visited this cell”. Three approaches, in order of preference:

// 1. Best: a 2D boolean array, when the grid dimensions are known
boolean[][] visited = new boolean[rows][cols];
visited[r][c] = true;

// 2. Encode the pair into a single integer, when the grid is large but bounded
Set<Integer> visited = new HashSet<>();
visited.add(r * cols + c);

// 3. A set of strings — works, but slow; avoid in hot loops
Set<String> visited = new HashSet<>();
visited.add(r + "," + c);

Encoding as r * cols + c is valid as long as c is always less than cols, which makes the mapping unique. For coordinates that can be large or negative, use a long:

long key = (long) r * 2_000_000 + c;

static class Point {
    int r, c;
    Point(int r, int c) { this.r = r; this.c = c; }

    @Override public boolean equals(Object o) {
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return r == p.r && c == p.c;
    }

    @Override public int hashCode() {
        return Objects.hash(r, c);
    }
}

Worked example

Given N integers, count how many pairs sum to exactly X.

The brute force is O(N²). With a map of counts it becomes O(N):

Map<Integer, Integer> count = new HashMap<>();
long pairs = 0;

for (int i = 0; i < n; i++) {
    // how many earlier values complete a pair with a[i]?
    pairs += count.getOrDefault(x - a[i], 0);
    count.merge(a[i], 1, Integer::sum);
}

System.out.println(pairs);

Counting the complement before inserting the current value is what prevents an element from pairing with itself and stops each pair being counted twice. Getting that order right is the whole trick.

Next