02 — Java Collections Toolkit

The data structures the 150 require: what each one is, which methods you actually use, what each method does, and when to pick it over the alternatives.

Aim to write every snippet here from memory without an IDE. If a structure is new to you, read its "what it is" paragraph before the method lists — the mechanics make much more sense once you know what the thing is doing internally.

Every behaviour claimed here was verified by running it.

1. HashMap

1.1 What it is

A HashMap stores key → value pairs and finds any key in roughly one step.

How: it runs the key through a hash function, turning it into a number. That number picks a slot ("bucket") in an internal array. To store, jump to the slot and put the value there. To retrieve, run the same hash, jump to the same slot, read it back.

The consequence that matters: lookup time doesn't depend on how many entries there are. A map with 10 entries and one with 10 million both answer get in about the same time. That is what O(1) means here.

The costs are memory (the internal array has empty slots) and no ordering — iterating a HashMap gives entries in an essentially arbitrary order.

1.2 Core methods

Map<String, Integer> map = new HashMap<>();

Map<String,Integer> m = Map.of("a", 1, "b", 2);     // IMMUTABLE, up to 10 pairs
Map<String,Integer> mutable = new HashMap<>(m);     // wrap to make it mutable

Map.of is convenient for test data but immutable and rejects nulls — wrap it in new HashMap<>(...) before modifying.

1.3 The compute family — the methods worth knowing well

These six solve "update a value that may or may not exist yet". Choosing the right one removes most of the if (containsKey) boilerplate people write.

computeIfAbsent vs putIfAbsent

Both "insert if missing", but they differ in two important ways:

// putIfAbsent: you must build the value FIRST, even when it's not needed
map.putIfAbsent("k", new ArrayList<>());   // allocates a list every call, used or not
map.get("k").add(1);                       // then a second lookup

// computeIfAbsent: builds only when missing, AND hands the value back
map.computeIfAbsent("k", k -> new ArrayList<>()).add(1);   // one lookup, one allocation

computeIfAbsent returns the value (existing or newly created), so you can chain .add(...) straight onto it. That's why it's the standard idiom for maps of lists.

null return means delete

For compute, computeIfPresent, and merge, returning null from the function removes the entry:

Map<String,Integer> m = new HashMap<>(Map.of("x", 1));
m.merge("x", -1, (old, val) -> old + val == 0 ? null : old + val);
m;        // {}  ← verified: the entry was deleted, not set to 0

This is genuinely useful — "decrement, and drop the key when it reaches zero" is one line instead of four.

1.4 Frequency counting

The most common use in the 150. Three equivalent idioms:

map.put(c, map.getOrDefault(c, 0) + 1);      // most readable — use by default
map.merge(c, 1, Integer::sum);               // most concise
map.compute(c, (k, v) -> v == null ? 1 : v + 1);

Reading idiom 1: "get the current count, or 0 if this is the first time, add one, store it back."

Reading idiom 2: merge(key, valueIfAbsent, howToCombineIfPresent) — if the key is missing store 1; if present, combine the old value with 1 using Integer::sum (shorthand for (a, b) -> a + b).

Decrementing and removing at zero:

map.merge(c, -1, (old, v) -> old + v == 0 ? null : old + v);

1.5 Grouping into buckets

Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);

Read as: "get the list for this key; if there isn't one, create an empty list and store it. Either way, hand me back the list so I can add to it."

The manual equivalent it replaces:

if (!groups.containsKey(key)) groups.put(key, new ArrayList<>());
groups.get(key).add(word);

1.6 The three views

keySet(), values(), and entrySet() are live views, not copies. Changing them changes the map:

map.keySet().remove("a");                 // removes the ENTRY from the map — verified
map.values().removeIf(v -> v == 0);       // removes all entries with value 0 — verified
for (Map.Entry<String,Integer> e : map.entrySet()) e.setValue(e.getValue() * 10);   // writes through

entry.setValue(v) is the only safe way to modify values while iterating — it goes through the view rather than calling map.put, so it doesn't trigger ConcurrentModificationException.

To get an independent copy, construct one: new ArrayList<>(map.keySet()).

1.7 Iteration

Use entrySet(). Iterating keySet() and calling get inside does two lookups per entry instead of one:

for (Map.Entry<String, Integer> e : map.entrySet()) {
    String k = e.getKey();
    int v = e.getValue();
}

for (String key : map.keySet()) { ... }         // keys only
for (int val : map.values()) { ... }            // values only
map.forEach((k, v) -> { ... });                 // lambda form

1.8 Traps

• map.get(missingKey) returns null. Assigning to an int throws NullPointerException. Use getOrDefault.
• Modifying the map during a for-each throws ConcurrentModificationException. See §12.
• Mutable keys break the map. Mutating a key after insertion makes its entry unreachable. See 05.
• int[] cannot be a key. Arrays use identity, not content. See 05.

2. LinkedHashMap

2.1 What it is

A LinkedHashMap is a HashMap with a doubly linked list threaded through all its entries, recording an order.

HashMap buckets (for O(1) lookup)      Linked list (for order)
  [ ][a][ ][c][ ][b][ ]                 head → a → b → c → tail

You get both at once:

• Lookup is still O(1) — the buckets are unchanged from HashMap.
• Iteration follows a defined order — the linked list.

The cost is two extra pointers per entry, so roughly 30–40% more memory than HashMap. Everything else is identical.

The one-line summary: LinkedHashMap is what you use when you want HashMap speed but need iteration to come out in a predictable order.

2.2 Why you would want one

Four concrete situations:

1. Deterministic output. A HashMap's iteration order is arbitrary and can change between runs or JDK versions. If you're printing results, writing a file, or comparing against expected output in a test, HashMap gives you flaky ordering. LinkedHashMap gives you the order you inserted.

2. Preserving an order you just computed. This is the common one. You sort a map's entries — then putting them into a HashMap throws the ordering away:

// ✗ the sort is wasted — HashMap reorders it arbitrarily
Map<String,Integer> bad = freq.entrySet().stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

// ✓ LinkedHashMap keeps the sorted order
LinkedHashMap<String,Integer> good = freq.entrySet().stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
                              (a, b) -> a, LinkedHashMap::new));

See 04 §5.4.

3. Deduplicating while keeping first-seen order. A HashSet deduplicates but scrambles; LinkedHashSet does both:

new LinkedHashSet<>(List.of("pear","apple","pear","fig"));   // [pear, apple, fig]  ← verified
new HashSet<>(List.of("pear","apple","pear","fig"));         // [apple, pear, fig]  ← arbitrary

4. An LRU cache. With access-order mode, the least-recently-used entry is always the first one. See §2.5.

2.3 Mode 1 — insertion order (the default)

LinkedHashMap<String,Integer> map = new LinkedHashMap<>();
map.put("c", 1);
map.put("a", 2);
map.put("b", 3);
map;                      // {c=1, a=2, b=3}  ← insertion order, not sorted

Note it is insertion order, not sorted order. LinkedHashMap never sorts anything — for that you want TreeMap (§3).

Two behaviours worth knowing:

map.put("c", 99);         // {c=99, a=2, b=3}  ← re-putting does NOT move the key

Updating an existing key leaves its position alone. Only new keys go to the end.

map.remove("a");
map.put("a", 5);          // {c=99, b=3, a=5}  ← now it moves to the end

Remove-then-insert does move it, because the second put is inserting a genuinely new key.

2.4 Mode 2 — access order

Pass true as the third constructor argument:

new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder)
new LinkedHashMap<>(16, 0.75f, true)        // 16 and 0.75f are the standard defaults

Now reading an entry moves it to the end of the order, so the list runs least-recently-used → most-recently-used.

Verified, starting from {a=1, b=2, c=3}:

containsKey is not an access. Only operations that actually retrieve or store a value count. This catches people out — checking for a key doesn't refresh it.

2.5 Automatic eviction: removeEldestEntry

LinkedHashMap has one protected hook, called after every insertion:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

Return true and the eldest entry (the head of the list) is evicted. Combine with access-order mode and you have an LRU cache in six lines:

int capacity = 3;
LinkedHashMap<Integer,String> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest) {
        return size() > capacity;
    }
};

lru.put(1,"a"); lru.put(2,"b"); lru.put(3,"c");
lru.get(1);              // touching 1 makes it most-recent, so 2 is now eldest
lru.put(4,"d");          // over capacity → evict 2
lru;                     // {3=c, 1=a, 4=d}   ← verified

The { ... } creates an anonymous subclass — that's how you override a protected method inline.

In insertion-order mode the same hook gives you an FIFO cache instead (evict the oldest inserted, regardless of use).

For the LRU Cache interview question, do NOT use this. The question is testing whether you can build the mechanism — a hash map plus a doubly linked list, by hand (11). Say: "LinkedHashMap gives this for free with access-order and removeEldestEntry, but I'll implement it directly since that's what's being asked." You get credit for knowing both.

2.6 Methods

LinkedHashMap implements Map, so every method from §1.2 and §1.3 works identically — put, get, getOrDefault, merge, computeIfAbsent, entrySet, and the rest. It adds no new public methods.

What it changes is a guarantee: keySet(), values(), entrySet(), and forEach all iterate in the defined order. The only additional API is the protected removeEldestEntry hook.

Useful order-dependent idioms that only make sense here:

// First (eldest) entry
Map.Entry<K,V> eldest = map.entrySet().iterator().next();

// First key
K firstKey = map.keySet().iterator().next();

There is no getFirst/getLast — for that you want TreeMap's firstEntry/lastEntry (§3), or a Deque.

2.7 Which map should I use?

The decision in one sentence each:

• Don't care about order → HashMap.
• Want insertion or access order → LinkedHashMap.
• Want sorted order, or floorKey/ceilingKey → TreeMap.

A common mistake is reaching for TreeMap when you only want deterministic output. If you don't need sorted order, LinkedHashMap gives you determinism at O(1) instead of O(log n).

2.8 LinkedHashSet

The set equivalent — a HashSet that remembers insertion order:

Set<String> seen = new LinkedHashSet<>();
seen.add("pear"); seen.add("apple"); seen.add("pear");
seen;                                   // [pear, apple]  ← verified

Same O(1) operations as HashSet, same API, plus ordered iteration. Use it whenever you deduplicate something whose original order matters.

3. TreeMap / TreeSet

3.1 What it is

A TreeMap stores key → value pairs like a HashMap, but keeps the keys sorted at all times.

Internally it's a self-balancing binary search tree (a red-black tree), not a bucket array. Every operation costs O(log n) instead of HashMap's O(1) — you are paying that log n to get ordering.

Why O(log n): to find a key you start at the root and compare. Each comparison tells you to go left or right, discarding half the remaining keys. About log₂ n steps gets you anywhere — 20 steps for a million entries.

What that buys you, which HashMap cannot do at any price:

• Iteration comes out in sorted key order.
• You can ask for the nearest key: "the largest key ≤ 25", "the smallest key > 20".
• You can ask for the first or last key, or a range of keys.

3.2 Creating one

There are four constructors. This is the part to get comfortable with first.

(a) Natural ordering — the default

TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple",  1);
map.put("cherry", 3);

map;                          // {apple=1, banana=2, cherry=3}   ← verified, alphabetical

You insert in any order; the map keeps them sorted. Keys are ordered by their natural ordering — compareTo. For String that's alphabetical, for Integer numeric, and so on (04 §2.6).

(b) With a comparator — any order you like

Pass a Comparator to the constructor:

TreeMap<String, Integer> desc = new TreeMap<>(Comparator.reverseOrder());
desc.put("banana", 2);
desc.put("apple",  1);
desc.put("cherry", 3);

desc;                         // {cherry=3, banana=2, apple=1}   ← verified, reversed

This is also how you order keys whose class isn't Comparable — see §3.7.

TreeMap<String, Integer> byLength =
    new TreeMap<>(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

(c) From an existing Map — copy and sort

Map<String, Integer> hm = new HashMap<>(Map.of("pear", 4, "fig", 5, "date", 6));
TreeMap<String, Integer> sorted = new TreeMap<>(hm);

sorted;                       // {date=6, fig=5, pear=4}   ← verified, now sorted

This is the standard way to sort a HashMap by key — one line, and the result stays sorted as you keep using it (04 §5.4).

(d) From a SortedMap — copy and keep its comparator

TreeMap<String, Integer> copy = new TreeMap<>(desc);     // desc uses reverseOrder
copy;                         // {cherry=3, banana=2, apple=1}   ← verified, comparator preserved
copy.comparator();            // the reverse comparator, not null

A subtle trap. There are two constructors — TreeMap(Map) and TreeMap(SortedMap) — and Java picks by the static type of what you pass. Passing a TreeMap uses the SortedMap version and keeps the comparator. Casting it to Map first uses the other one and silently reverts to natural ordering:

Java

new TreeMap<>((Map<String,Integer>) desc);   // {apple=1, banana=2, cherry=3}  ← verified, order LOST

If you're copying a map and want its ordering kept, don't widen the type on the way in.

Which constructor to use

new TreeMap<>(comparator) starts empty — to fill it from another map, follow with putAll:

TreeMap<String,Integer> descCopy = new TreeMap<>(Comparator.reverseOrder());
descCopy.putAll(hm);

3.3 Basic operations — it's still a Map

Everything from §1.2 and §1.3 works exactly as it does on a HashMap. Only the cost and the ordering differ.

TreeMap<Integer, String> m = new TreeMap<>();

m.put(1, "a");                  // returns null (no previous value)      ← verified
m.put(1, "b");                  // returns "a" (the OLD value)           ← verified
m.get(1);                       // "b"
m.getOrDefault(9, "none");      // "none" — key absent
m.containsKey(9);               // false
m.remove(1);                    // returns "b", the removed value        ← verified
m.size();  m.isEmpty();  m.clear();
m.putAll(otherMap);

The compute family works too — merge, computeIfAbsent, getOrDefault and the rest all behave identically:

TreeMap<String,Integer> counts = new TreeMap<>();
for (String w : words) counts.merge(w, 1, Integer::sum);
// counts is now a frequency map, already sorted by word

3.4 Iteration comes out sorted

This is the everyday reason to use one:

TreeMap<Integer,String> m = new TreeMap<>();
m.put(30, "c");  m.put(10, "a");  m.put(20, "b");

for (Map.Entry<Integer,String> e : m.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}
// 10 -> a
// 20 -> b
// 30 -> c                                          ← verified

m.keySet();       // [10, 20, 30]   — sorted
m.values();       // [a, b, c]      — in key order

Compare with a HashMap, where all three of those come out in arbitrary order.

3.5 Navigation — the "nearest key" methods

These are what you're really buying. Every one is O(log n).

Take nav = {10=a, 20=b, 30=c} for the examples below.

All verified.

Remembering the four:

        lowerKey(x)   floorKey(x)  │  ceilingKey(x)   higherKey(x)
             <             ≤       x        ≥               >
        └── strict ──┘ └─ inclusive ─┘ └─ inclusive ─┘ └── strict ──┘

floor goes down (like flooring a number), ceiling goes up. lower/higher are the strict versions.

Key variants vs entry variants

Every method above has an ...Entry twin returning the whole Map.Entry instead of just the key:

nav.floorKey(25);        // 20          — just the key
nav.floorEntry(25);      // 20=b        — key AND value, one lookup    ← verified
nav.floorEntry(25).getValue();   // "b"

firstEntry(), lastEntry(), floorEntry(x), ceilingEntry(x), lowerEntry(x), higherEntry(x).

Use the entry version when you need the value too — it saves a second get.

Take-and-remove

nav.pollFirstEntry();    // returns 10=a AND removes it    ← verified
nav.pollLastEntry();     // returns the largest and removes it

This is "take the smallest remaining", which is exactly the loop in Hand of Straights (20).

Empty-map behaviour differs between the two families

new TreeMap<>().firstKey();      // throws NoSuchElementException    ← verified
new TreeMap<>().firstEntry();    // returns null                     ← verified

The ...Key methods throw; the ...Entry methods return null. Guard with isEmpty() or prefer the entry form.

3.6 Range views

m.headMap(x);                    // keys < x                        (exclusive by default)
m.tailMap(x);                    // keys >= x                       (inclusive by default)
m.subMap(lo, hi);                // [lo, hi)
m.subMap(lo, true, hi, true);    // inclusive on both ends
m.tailMap(x, false);             // keys > x
m.descendingMap();               // the whole map, reversed
m.descendingKeySet();            // [30, 20, 10]

Verified on {10=a, 20=b, 30=c}: subMap(10,20) is {10=a}; subMap(10,true,20,true) is {10=a, 20=b}; tailMap(20) is {20=b, 30=c}; tailMap(20,false) is {30=c}.

Note the default asymmetry: headMap excludes its bound, tailMap includes it — matching subMap(lo, hi) being [lo, hi). When it matters, use the explicit boolean form and make it obvious.

These are live views, not copies. Creating one is O(1), and modifying it modifies the underlying map:

TreeMap<Integer,String> base = new TreeMap<>(Map.of(1,"a",2,"b",3,"c",4,"d"));
base.headMap(3).remove(1);
base;                            // {2=b, 3=c, 4=d}   ← verified, the removal wrote through

Use new TreeMap<>(base.headMap(3)) if you want an independent copy.

3.7 Ordering custom objects

By default a TreeMap orders keys by natural ordering, so the key class must implement Comparable. If it doesn't:

TreeMap<Employee, String> tm = new TreeMap<>();
tm.put(someEmployee, "x");       // ClassCastException — on the FIRST put

Two fixes: make the class Comparable, or pass a comparator:

TreeMap<Employee, String> bySalary =
    new TreeMap<>(Comparator.comparingInt((Employee e) -> e.salary).reversed());

map.comparator() tells you which is in use — it returns null for natural ordering (verified).

The comparator is fixed at construction and cannot be changed. For the opposite order use descendingMap(); for a genuinely different order, build a new map.

A comparator used for TreeMap keys must be a total order — it must never return 0 for two keys you consider different, or one will silently overwrite the other. Full treatment in 04 §5.2.

3.8 TreeSet

The same structure without values — sorted membership.

TreeSet<Integer> set = new TreeSet<>();                    // natural ordering
TreeSet<Integer> desc = new TreeSet<>(Comparator.reverseOrder());
TreeSet<Integer> from = new TreeSet<>(List.of(5, 1, 3));   // [1, 3, 5]   ← verified

set.add(x);  set.contains(x);  set.remove(x);  set.size();

It gets the set equivalent of every navigation method:

set.first();  set.last();                         // 1 / 5
set.floor(4);  set.ceiling(4);                    // 3 / 5      ← verified
set.lower(4);  set.higher(4);
set.pollFirst();  set.pollLast();                 // take and remove
set.headSet(x);  set.tailSet(x);  set.subSet(lo, hi);
set.descendingSet();

Note the names drop the Key: floor not floorKey.

3.9 When to reach for it

Where it shows up in the 150:

• Time Based Key-Value Store (10) — floorEntry(timestamp) is literally the whole question: "the value at or before time T".

  Java

  TreeMap<Integer,String> versions = new TreeMap<>();
  versions.put(1,"v1");  versions.put(5,"v5");  versions.put(10,"v10");
  versions.floorEntry(7).getValue();        // "v5"   ← verified

• Hand of Straights (20) — firstKey() gives the smallest remaining card, which must start the next group.

• Interval and sweep-line problems (21) — a TreeMap<time, delta> iterates events in chronological order.

3.10 Traps

• null keys are rejected. TreeMap.put(null, v) throws NullPointerException (verified), because it has to compare the key. A HashMap allows one null key.
• firstKey()/lastKey() throw on an empty map; firstEntry()/lastEntry() return null.
• floorKey/ceilingKey return null when nothing qualifies — check before unboxing to int.
• Casting a SortedMap to Map when copying loses the comparator (§3.2d).
• A non-total comparator silently drops or overwrites keys (§3.7).
• Everything is O(log n), not O(1). Don't use a TreeMap as a general-purpose map "just in case" you need ordering.

4. HashSet and friends

4.1 What it is

A HashSet is a HashMap that only stores keys. It answers one question — "have I seen this before?" — in O(1).

Set<Integer> seen = new HashSet<>();
seen.add(x);  seen.contains(x);  seen.remove(x);  seen.size();

The add return value

add returns false if the element was already present, letting you test and insert in one call:

if (!seen.add(x)) return true;      // "add failed" = "already there" = duplicate

That's the whole of Contains Duplicate. The longer form does the same work twice:

if (seen.contains(x)) return true;  // lookup 1
seen.add(x);                        // lookup 2

remove similarly returns true only if something was actually removed.

4.2 Set algebra

Three bulk operations turn a Set into a proper mathematical set. All three mutate the receiver, so copy first:

Set<Integer> union = new HashSet<>(s1);  union.addAll(s2);      // s1 ∪ s2
Set<Integer> inter = new HashSet<>(s1);  inter.retainAll(s2);   // s1 ∩ s2  (keep only shared)
Set<Integer> diff  = new HashSet<>(s1);  diff.removeAll(s2);    // s1 − s2  (drop shared)

Verified on {1,2,3,4} and {3,4,5}: union [1,2,3,4,5], intersection [3,4], difference [1,2].

containsAll(s2) tests the subset relation.

4.3 The three Set implementations

4.4 Building from an array

Set<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);                                   // clearest

Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());

boxed() is needed because nums is int[] (primitives) and a Set can only hold objects — see 03.

5. ArrayDeque

5.1 What a stack and a queue are

A stack is last-in-first-out (LIFO), like a stack of plates: you add and remove at the same end. Use one whenever the most recently seen unresolved item is the one to handle first — matching brackets, undo, backtracking.

A queue is first-in-first-out (FIFO), like a line at a shop. Use one for breadth-first search, where everything at distance 1 must be handled before anything at distance 2.

A deque ("double-ended queue", said deck) allows adding and removing at both ends — so one class covers both roles.

5.2 Why ArrayDeque for both

• java.util.Stack is a legacy class that synchronizes every method — thread-safety you aren't using, paid for on every call. Interviewers notice.
• LinkedList works but scatters nodes across memory, so it's measurably slower.

5.3 The full method table

Deque has two methods for every operation: one throwing an exception on failure, one returning a special value. Mixing them up is a common source of bugs.

Verified on an empty deque: poll() and peek() return null; remove() throws NoSuchElementException.

Prefer the offer/poll/peek family — a null return is easier to handle than an exception, and the standard idiom while (!dq.isEmpty()) means you rarely hit either case.

5.4 As a stack

Deque<Integer> stack = new ArrayDeque<>();
stack.push(x);          // addFirst
stack.pop();            // removeFirst — throws if empty
stack.peek();           // peekFirst — null if empty
stack.isEmpty();

5.5 As a queue

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(x);         // addLast
queue.poll();           // removeFirst — null if empty
queue.peek();           // peekFirst

Note the asymmetry: push adds to the front and offer adds to the back, but pop and poll both remove from the front. That's exactly what makes one LIFO and the other FIFO. Pick one vocabulary per use and stay consistent — mixing push with poll on the same structure is confusing to read.

5.6 As a monotonic deque

Sliding Window Maximum (08) needs both ends:

dq.offerLast(i);        // add to the back
dq.pollLast();          // discard from the back to maintain monotonicity
dq.peekFirst();         // the window's answer
dq.pollFirst();         // evict indices that slid out of the window

5.7 Trap

ArrayDeque rejects null — it uses null internally to mean "empty slot", so storing one would be ambiguous. If you genuinely need a queue holding nulls, use LinkedList.

6. PriorityQueue

6.1 What it is

A PriorityQueue keeps its elements so that the smallest is always instantly available at the front. Everything else is only loosely ordered.

That weakness is the point. Full sorting costs O(n log n). If you only ever need the minimum, a binary heap — where each element is smaller than its two children — suffices, and inserting or removing only has to fix one path up or down the tree.

6.2 Configuration

PriorityQueue<Integer> minHeap = new PriorityQueue<>();                           // smallest first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // largest first

// Pairs — the common interview shape: {distance, nodeId}
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{dist, node});
int[] top = pq.poll();

PriorityQueue<Integer> h = new PriorityQueue<>(existingList);    // O(n) bulk build

Ordering custom objects follows the same rules as TreeMap — Comparable, or a comparator in the constructor, else ClassCastException on the first offer. See 04.

6.3 Traps

• contains / remove(Object) are O(n). The heap is only organized around its root, so finding an arbitrary element means scanning. The workaround is lazy deletion — see 14.
• Iteration is not sorted. Only repeated poll() gives sorted order. Printing a heap shows the raw internal array, which looks scrambled.
• peek/poll return null on empty, not an exception.

See 14 for the patterns heaps solve.

7. ArrayList and List

7.1 What it is

An ArrayList wraps an array that grows automatically. Indexed access is O(1); inserting or removing in the middle is O(n) because elements shift.

Why add is O(1) amortized: when the internal array fills, a new one of double the size is allocated and everything is copied — that single add is O(n). But doubling means n adds cost O(n) of copying in total, averaging constant. See 01.

7.2 Core methods

add(i, e) vs set(i, e) is a common mix-up: add makes the list longer and shifts; set replaces and keeps the size.

remove is ambiguous on List<Integer>:

list.remove(1);                       // removes INDEX 1
list.remove(Integer.valueOf(1));      // removes the VALUE 1

A bare int picks the index overload. See 03.

7.3 subList is a view, not a copy

List<Integer> base = new ArrayList<>(List.of(1,2,3,4,5));
List<Integer> sub = base.subList(1, 4);      // [2, 3, 4]

sub.set(0, 99);
base;                                        // [1, 99, 3, 4, 5]  ← verified, wrote through

sub.clear();
base;                                        // [1, 5]            ← verified, removed from base

Useful for operating on a range without copying — and a hazard if you didn't expect it. To get an independent copy: new ArrayList<>(base.subList(1, 4)).

7.4 The three ways to make a list

Arrays.asList(arr).set(0, 42);     // OK — writes THROUGH to the backing array (verified)
Arrays.asList(arr).add(4);         // UnsupportedOperationException (verified)
List.of(1, null);                  // NullPointerException (verified)

Arrays.asList returns a view of the array — set writes through to it, but the size is fixed. List.of is fully immutable.

To get a mutable list from either: new ArrayList<>(List.of(1, 2, 3)).

7.5 Conversions

// int[] -> List<Integer>
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());

// List<Integer> -> int[]
int[] arr = list.stream().mapToInt(Integer::intValue).toArray();

// T[] -> List<T>  (fixed-size view)
List<String> view = Arrays.asList(strArr);

// List<T> -> T[]
String[] out = list.toArray(new String[0]);

Arrays.asList(intArray) where intArray is int[] gives a List<int[]> of size 1, not a list of ints. Autoboxing applies to individual values, never to whole arrays. Use the stream form.

8. Arrays — the static helper class

8.1 Creating and filling

int[] a = new int[n];                     // zero-filled
int[][] grid = new int[rows][cols];       // zero-filled
int[] b = {1, 2, 3};                      // literal

a.length;                                 // a FIELD — no parentheses

Arrays.fill(a, -1);                       // fill everything
Arrays.fill(a, from, to, -1);             // fill a range [from, to)
for (int[] row : grid) Arrays.fill(row, -1);   // 2-D needs a loop per row

Arrays.setAll(a, i -> i * i);             // compute each element from its index
                                          // verified: [0, 1, 4, 9, 16]

Arrays.fill on a 2-D array does not work as expected — new int[3][3] is an array of three row references, so Arrays.fill(grid, -1) would try to store -1 as a row. Loop over the rows.

8.2 Copying

int[] copy  = a.clone();                  // full copy, same length
int[] grown = Arrays.copyOf(a, newLen);   // truncates, or pads with 0/null
int[] slice = Arrays.copyOfRange(a, from, to);        // [from, to)
System.arraycopy(src, srcPos, dest, destPos, length); // copy into an EXISTING array

System.arraycopy is the low-level one — it doesn't allocate, so use it when the destination already exists.

The 2-D shallow-copy trap

int[][] g = {{1,2},{3,4}};
int[][] shallow = g.clone();
shallow[0][0] = 99;
g[0][0];                                  // 99  ← verified: they share the same rows!

clone() on a 2-D array copies the array of row references, not the rows. Both arrays point at the same row objects.

For an independent copy, clone each row:

int[][] deep = new int[g.length][];
for (int i = 0; i < g.length; i++) deep[i] = g[i].clone();

Verified: mutating deep then leaves g untouched.

8.3 Searching and comparing

Arrays.sort(a);                           // ascending; primitives only, no comparator
Arrays.sort(a, from, to);                 // sort a subrange
Arrays.sort(objArr, comparator);          // objects — see [04]

Arrays.binarySearch(a, key);              // array MUST be sorted first
Arrays.equals(a, b);                      // element-by-element, 1-D
Arrays.deepEquals(g1, g2);                // nested arrays
Arrays.hashCode(a);   Arrays.deepHashCode(g);
Arrays.toString(a);                       // "[1, 2, 3]" — debug print
Arrays.deepToString(grid);                // "[[1, 2], [3, 4]]" — 2-D debug print

Arrays.binarySearch's negative return encodes the insertion point. If the key is absent it returns -(insertionPoint) - 1; recover it with -(result + 1). Verified: searching for 25 in [10,20,30] returns -3, and -(-3 + 1) = 2, the index where 25 belongs.

Arrays.equals and Arrays.hashCode are static helpers only. HashMap never calls them — it calls the instance methods on the key, which for an array means identity. That's why int[] fails as a map key. See 05.

8.4 Streams over arrays

Arrays.stream(a).sum();
Arrays.stream(a).max().getAsInt();        // returns OptionalInt
Arrays.stream(a).min().getAsInt();
Arrays.stream(a).average().orElse(0);
Arrays.stream(a).filter(x -> x > 0).count();
Arrays.stream(a, from, to).sum();         // a range
Arrays.stream(a).boxed().toArray(Integer[]::new);   // int[] -> Integer[]

8.5 2-D arrays and the direction vector

int rows = grid.length;
int cols = grid[0].length;                // guard rows > 0 first

Every grid traversal in the 150 uses the direction vector rather than four near-identical blocks:

int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};      // right, left, down, up

for (int[] d : DIRS) {
    int nr = r + d[0], nc = c + d[1];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;   // bounds check FIRST
    // ... visit (nr, nc)
}

Lower-allocation variant:

int[] dr = {0, 0, 1, -1}, dc = {1, -1, 0, 0};
for (int k = 0; k < 4; k++) { int nr = r + dr[k], nc = c + dc[k]; }

9. StringBuilder

9.1 Why it exists

Java strings are immutable. So s += c doesn't append — it builds an entirely new string by copying everything. Over n characters that's 1 + 2 + ... + n copies: O(n²).

StringBuilder keeps a mutable buffer and appends in O(1) amortized, converting to a String once at the end. For n = 100,000 that's the difference between instant and unusable.

9.2 Methods

StringBuilder sb = new StringBuilder("hello");
sb.insert(0, ">>")                    // ">>hello"
  .append("!")                        // ">>hello!"
  .replace(2, 3, "H")                 // ">>Hello!"
  .deleteCharAt(sb.length() - 1);     // ">>Hello"     ← verified

setLength(sb.length() - 1) is the standard "undo" step in backtracking (15) — append a character, recurse, then remove it to try the next option. deleteCharAt(sb.length()-1) does the same thing.

Pre-sizing avoids intermediate regrowth when you know the final size: new StringBuilder(n).

10. Collections — the static helper class

Static methods on java.util.Collections, operating on List unless noted:

Verified: frequency([1,2,2,3], 2) is 2; swap on [1,2,3] at 0 and 2 gives [3,2,1]; nCopies(3,"x") is [x, x, x].

Collections.reverse(list) vs Collections.reverseOrder() — the first flips the list you already have; the second is a comparator you pass to a sort. Confusing them is common. See 04.

11. Using custom objects in collections

A class of your own only works correctly in these structures if you give it the right methods:

int[] is never a valid HashMap key — arrays don't override equals/hashCode, so only the identical reference ever matches. This bites in Group Anagrams and Detect Squares; 05 covers the fixes.

12. Iterating and removing safely

Modifying a collection while a for-each walks it throws ConcurrentModificationException:

for (Integer x : list) {
    if (x % 2 == 0) list.remove(x);        // ConcurrentModificationException
}

Four correct approaches:

// 1. removeIf — shortest and idiomatic
list.removeIf(x -> x % 2 == 0);

// 2. Iterator.remove() — the only way to remove during a manual walk
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() % 2 == 0) it.remove();
}

// 3. Loop backwards by index
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i) % 2 == 0) list.remove(i);
}

// 4. Collect first, remove after
List<Integer> doomed = new ArrayList<>();
for (Integer x : list) if (x % 2 == 0) doomed.add(x);
list.removeAll(doomed);

Why backwards works but forwards doesn't: removing index i shifts everything after it left by one, so a forward loop skips the next element. Going backwards, the shift only affects indices you've already passed.

Maps follow the same rule:

map.entrySet().removeIf(e -> e.getValue() == 0);      // verified
map.values().removeIf(v -> v == 0);                   // equivalent

Iterator<Map.Entry<String,Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getValue() == 0) it.remove();
}

13. Choosing the right structure

The two most common mis-picks:

• Reaching for TreeMap when you only want deterministic output. If you don't need sorted order or neighbour queries, LinkedHashMap gives determinism at O(1) instead of O(log n).
• Reaching for LinkedList. ArrayList is faster for almost everything, and ArrayDeque beats it for queue use. LinkedList is only preferable when you need a queue that accepts null.