05

Java Toolkit & Collections

Know which container to grab, what each call costs, and the handful of Java traps that sink interview code.

beginner~70 min5 simulations

▶ guided lesson⚡ 1-minute summary↻ 14 recall cards

before this: Java OOP

01 · why it exists

Why this exists, and the weight it carries

since1998

The Collections Framework

Joshua Bloch (design lead) and the JDK team at Sun Microsystems

Early Java had arrays, Vector and Hashtable, with no shared interface between them. JDK 1.2 (renamed Java 2, shipped December 1998) added the Collections Framework: interfaces like List, Set and Map, plus ready-made implementations behind them. Joshua Bloch led its design. The old Vector and Hashtable were retrofitted to fit the new interfaces.

the problem it solvedEvery library invented its own containers, so code couldn't pass collections around, or swap a slow implementation for a faster one without a rewrite.

its jobs today

  • Gives every Java API one vocabulary: a method that takes a Collection<Order> accepts an ArrayList, a HashSet or an ArrayDeque.
  • Ships tested, tuned data structures in every JDK: resizable arrays, hash tables, ring buffers, heaps and red-black trees.
  • Defines the types interviews speak: LeetCode's Java signatures use List<Integer>, List<List<String>> and friends.

the weight it carries

From this chapter's own code: our stripped-down, int-only HashMap, ArrayList, ring-buffer deque and min-heap take 42 + 22 + 35 + 35 = 134 non-blank lines, with no generics and no iterators. With java.util each is one line: new HashMap<>(), new ArrayList<>(), new ArrayDeque<>(), new PriorityQueue<>(). In a timed round, those 134 lines are minutes you get back for the actual problem.

without it

Every solution would start with a hand-written hash table or heap, and every library would speak its own container dialect.

when · why · how

when
Always, unless the problem asks you to build the structure yourself (Design HashMap, Implement Queue using Stacks).
why
The JDK versions are tested, generic and fast, so your time goes into the algorithm. Knowing what's inside each one tells you the Big-O of every call.
how
Declare by interface, construct by class: Map<String, Integer> m = new HashMap<>(); · Deque<Integer> q = new ArrayDeque<>();

02 · plain english

The idea in 30 seconds

Most interview solutions are 80% choosing the right container: ArrayList, ArrayDeque, HashMap/HashSet, TreeMap/TreeSet, PriorityQueue.

Each one is a data structure you'll meet later in the course. The JDK already wrote it for you. Know what's inside, and you know what each call costs.

A few traps (Integer ==, a - b comparators, remove(int) vs remove(Object)) cause most "it works on my example" bugs.

picture this

java.util is like the tools already installed on your laptop. Nobody writes a text editor before taking notes, but you do need to know when to open Notepad and when to open Excel. Same here: pick the container whose strengths match the job.

03 · remember

What you must know

  • The map: List (ArrayList) for indexed sequences · Deque (ArrayDeque) for stacks and queues · Set/Map (Hash, LinkedHash, Tree*) for membership and lookup · PriorityQueue for "give me the smallest next".
  • ArrayList is a growable array: when full it allocates about 1.5× the slots and copies everything. That's rare, so add is amortized O(1). But add(0, x) and remove(0) shift every element: O(n).
  • Hash vs Linked vs Tree: HashMap is O(1) average with no order · LinkedHashMap is O(1) average and keeps insertion order · TreeMap is O(log n) with sorted keys plus floor/ceiling queries.
  • Use `ArrayDeque`, not `Stack` or `LinkedList`, for stacks and queues. Stack is a synchronized legacy class; ArrayDeque is a fast ring buffer.
  • int vs Integer: collections hold objects, so an int is autoboxed. == on two Integers compares references. It only seems to work for −128..127 (the Integer cache). Use equals, or unbox.
  • Order objects with comparators: Integer.compare(a, b) or Comparator.comparingInt(...), never a - b (overflow). Chain with thenComparing, flip with reversed().
  • This chapter is the Collections Framework. Strings and StringBuilder live in Java arrays & strings, overflow in Java memory, fast I/O in Java I/O & debugging, generics and records in Java OOP.
  • Utilities you'll use daily: Arrays.sort/fill/toString/asList/copyOf, Collections.sort/reverse/max, List.of, Map.getOrDefault/merge/computeIfAbsent.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Inside ArrayList: growing by 1.5×

Adds are cheap writes. When the array is full, Java allocates about 1.5× the slots and copies everything. That's rare enough that add stays amortized O(1).

loading simulation…
sim

Inside HashMap: buckets, collisions, resizing

Each key is hashed to a bucket. Watch a collision form a chain, then the table double at load factor 0.75.

loading simulation…
sim

Inside ArrayDeque: a ring buffer

head moves instead of elements. Both ends are O(1): no shifting, unlike ArrayList.remove(0).

loading simulation…
sim

Inside PriorityQueue: a heap in an array

The same heap drawn as a tree and as the array Java actually stores.

loading simulation…
sim

The Integer cache trap

Why `a == b` is true for 127 and false for 128.

loading simulation…

05 · cost

Time & space, explained

The Collections Framework map: what each call costs
AddRemoveLookup / containsOrderwhy
ArrayListO(1) amortized at end, O(n) elsewhereO(n) (O(1) at end)get(i) O(1), contains O(n)insertionA resizable array: indexing is direct, but inserting/removing in the middle shifts elements.
LinkedListO(1) at endsO(1) at endsget(i) O(n), contains O(n)insertionDoubly linked nodes: no shifting, but reaching index i walks the list. Rarely the best choice.
ArrayDequeO(1) amortized at both endsO(1) at both endscontains O(n)insertionA circular array with a moving head: the go-to stack and queue.
HashSet / HashMapO(1) averageO(1) averageO(1) averagenoneHash to a bucket; short chains on average. Big buckets become trees (Java 8+).
LinkedHashSet / LinkedHashMapO(1) averageO(1) averageO(1) averageinsertion (or access)A HashMap plus a linked list through the entries to remember order.
TreeSet / TreeMapO(log n)O(log n)O(log n), plus floor/ceilingsortedA red-black tree: always balanced, always sorted.
PriorityQueueoffer O(log n)poll O(log n), remove(x) O(n)peek O(1), contains O(n)only the head is orderedA binary heap in an array: the minimum is at index 0; the rest is only partially ordered.
Utilities and their costs
TimeNoteswhy
Arrays.sort(int[])O(n log n)dual-pivot quicksort; primitives, so stability doesn't matterSorting primitives in place; no boxing.
Arrays.sort(T[]) / Collections.sort / list.sortO(n log n)TimSort, stable; ~O(n) on nearly sorted inputMerge-based, so equal elements keep their order. Useful for multi-key sorts.
new PriorityQueue<>(collection)O(n)heapify, cheaper than n offers (O(n log n))Builds the heap bottom-up.
Arrays.fill / copyOf / equals / toStringO(n)one passTouch every element once.
Arrays.binarySearch / Collections.binarySearchO(log n)input must already be sortedHalves the range each step (on a RandomAccess list).
String += in a loop vs StringBuilderO(n²) vs O(n)+= copies the whole string each timeStrings are immutable; StringBuilder appends are amortized O(1).

06 · java

Raw vs Collections Framework

Arrays vs ArrayList

javaint[] / int[][]java.util.*
class RawArray {    static int[] squares(int n) {        int[] a = new int[n];               // fixed size, filled with 0s, primitives (no boxing)        for (int i = 0; i < n; i++) a[i] = i * i;        return a;    }     static int[] append(int[] a, int value) {        int[] bigger = Arrays.copyOf(a, a.length + 1); // arrays can't grow: copy, O(n)        bigger[a.length] = value;        return bigger;    }     static int[][] grid(int rows, int cols, int fill) {        int[][] g = new int[rows][cols];        for (int[] row : g) Arrays.fill(row, fill);       // fill each row        return g;    }}
  • int[] is fixed-size, stores primitives (fast, compact) and defaults to 0. Prefer it when the size is known: DP tables, counts, visited flags.
  • ArrayList<Integer> grows on demand but stores references to boxed Integer objects. That is several times the memory of an int[], plus boxing cost.
  • Graphs: List<List<Integer>> is the standard adjacency list. Avoid List<Integer>[]: generic arrays trigger unchecked warnings.
  • list.size() vs array.length vs string.length(): three different spellings, a classic compile error under pressure.

Inside ArrayList: a growable array

javaadd + grow by 1.5×java.util.*
class IntArrayList {    private int[] data;                       // the backing array: capacity = data.length    private int size = 0;                     // how many slots are actually used     IntArrayList(int initialCapacity) {        data = new int[initialCapacity];    }     void add(int value) {        if (size == data.length) grow();      // full? make room first        data[size++] = value;                 // the cheap O(1) part    }     private void grow() {        int oldCapacity = data.length;        int newCapacity = oldCapacity + Math.max(1, oldCapacity >> 1); // about 1.5x, like java.util.ArrayList        data = Arrays.copyOf(data, newCapacity); // copies every element: O(size)    }     int get(int i) {        Objects.checkIndex(i, size);          // same bounds check ArrayList.get does        return data[i];    }     int size() { return size; }     int capacity() { return data.length; }}
  • new ArrayList<>() starts with an empty array and allocates 10 slots on the first add. After that each grow is old + (old >> 1): 10 → 15 → 22 → 33 → … (OpenJDK 17).
  • size() is how many you stored; the capacity stays hidden. get(i) checks i < size, not the capacity.
  • Know n up front? new ArrayList<>(n) skips every resize. For primitives in hot loops, int[] is still faster (no boxing).
  • remove(0) and add(0, x) shift every element: O(n). That's why queues use ArrayDeque.

Arrays & Collections utilities

javathe everyday helpersjava.util.*
class Utilities {    static String demo() {        int[] a = {5, 2, 9, 1};        Arrays.sort(a);                                   // [1, 2, 5, 9]        int pos = Arrays.binarySearch(a, 5);              // 2 (array must be sorted)        Integer[] boxed = {5, 2, 9, 1};        Arrays.sort(boxed, Collections.reverseOrder());   // descending needs objects        List<Integer> fixed = Arrays.asList(3, 1, 2);     // fixed-size view: set OK, add throws        List<Integer> list = new ArrayList<>(fixed);      // a real, growable copy        Collections.sort(list);                           // [1, 2, 3]        Collections.reverse(list);                        // [3, 2, 1]        int max = Collections.max(list);                  // 3        int freq = Collections.frequency(List.of(1, 2, 1), 1); // 2        return Arrays.toString(a) + pos + Arrays.toString(boxed) + list + max + freq;    }}
  • Arrays.sort(int[]) can't take a comparator. For descending order or custom keys, sort an Integer[], or sort ascending and read backwards.
  • Arrays.asList(...) is a fixed-size view of the array: set works, add/remove throw. List.of(...) is fully immutable and rejects nulls.
  • Need a mutable copy? new ArrayList<>(List.of(...)).

HashMap: by hand vs java.util

javachaining + resize at 0.75java.util.*
class IntHashMap {    private List<int[]>[] buckets;            // each bucket: a chain of {key, value}    private int size = 0;     @SuppressWarnings("unchecked")    IntHashMap(int capacity) {                // capacity: a power of two        buckets = new List[capacity];    }     static int spread(int h) {        return h ^ (h >>> 16);                // same bit-mixing java.util.HashMap uses    }     private int indexFor(int key, int capacity) {        return spread(Integer.hashCode(key)) & (capacity - 1); // fast "mod capacity"    }     void put(int key, int value) {        int b = indexFor(key, buckets.length);        if (buckets[b] == null) buckets[b] = new ArrayList<>();        for (int[] entry : buckets[b])            if (entry[0] == key) { entry[1] = value; return; } // key exists: overwrite        buckets[b].add(new int[] {key, value}); // append to the chain        if (++size > buckets.length * 3 / 4) resize(); // load factor 0.75    }     Integer get(int key) {        List<int[]> chain = buckets[indexFor(key, buckets.length)];        if (chain != null)            for (int[] entry : chain) if (entry[0] == key) return entry[1];        return null;    }     @SuppressWarnings("unchecked")    private void resize() {        List<int[]>[] old = buckets;        buckets = new List[old.length * 2];   // double, then re-bucket every entry: O(n)        for (List<int[]> chain : old)            if (chain != null)                for (int[] e : chain) {                    int b = indexFor(e[0], buckets.length);                    if (buckets[b] == null) buckets[b] = new ArrayList<>();                    buckets[b].add(e);                }    }     int size() { return size; }     int capacity() { return buckets.length; }}
  • Real HashMap defaults: capacity 16, load factor 0.75, doubles on resize. The index is (n − 1) & (h ^ (h >>> 16)), exactly what the raw version does.
  • Java 8+: when a bucket already holding 8 entries gets another, it becomes a red-black tree (if the table has ≥ 64 buckets; otherwise the table is resized instead). Bad hash distributions then cost O(log n) per bucket for Comparable keys.
  • Counting idioms: map.merge(key, 1, Integer::sum) or map.put(key, map.getOrDefault(key, 0) + 1). Grouping: map.computeIfAbsent(key, k -> new ArrayList<>()).add(x).
  • Iteration order: HashMap is unspecified (don't rely on it), LinkedHashMap keeps insertion order, TreeMap is sorted by key.
  • Keys must have consistent equals and hashCode. Records and Strings do; arrays don't (int[] keys compare by identity, so use Arrays.toString(arr) or a List as the key).

Stacks & queues: ring buffer vs ArrayDeque

javacircular arrayjava.util.*
class IntRing {    private int[] data = new int[4];    private int head = 0;  // index of the first element    private int size = 0;     void addLast(int x) {        if (size == data.length) grow();        data[(head + size) % data.length] = x; // wrap around past the end        size++;    }     void addFirst(int x) {        if (size == data.length) grow();        head = (head - 1 + data.length) % data.length; // step back, wrapping to the end        data[head] = x;        size++;    }     int pollFirst() {        if (size == 0) throw new NoSuchElementException();        int x = data[head];        head = (head + 1) % data.length;        size--;        return x;    }     int pollLast() {        if (size == 0) throw new NoSuchElementException();        size--;        return data[(head + size) % data.length];    }     private void grow() {        int[] bigger = new int[data.length * 2];        for (int i = 0; i < size; i++) bigger[i] = data[(head + i) % data.length]; // unwrap in order        data = bigger;        head = 0;    }     int size() { return size; }}
  • Stack: push/pop/peek (all at the front). Queue: offer/poll/peek (back in, front out). One class does both.
  • ArrayDeque rejects null elements; poll/peek return null when empty, while pop/remove/element throw.
  • Avoid java.util.Stack (synchronized, extends Vector) and prefer ArrayDeque over LinkedList (no node object per element).

Heaps: by hand vs PriorityQueue

javaarray-backed min-heapjava.util.*
class IntMinHeap {    private int[] heap = new int[8];    private int size = 0;   // children of i: 2i+1, 2i+2; parent: (i-1)/2     void offer(int x) {        if (size == heap.length) heap = Arrays.copyOf(heap, size * 2);        heap[size] = x; // add at the bottom        int i = size++;        while (i > 0 && heap[(i - 1) / 2] > heap[i]) { // smaller than parent?            swap(i, (i - 1) / 2);            i = (i - 1) / 2;        }    }     int poll() {        if (size == 0) throw new NoSuchElementException();        int min = heap[0];        heap[0] = heap[--size]; // last leaf goes to the root        int i = 0;        while (true) {            int smallest = i, l = 2 * i + 1, r = 2 * i + 2;            if (l < size && heap[l] < heap[smallest]) smallest = l;            if (r < size && heap[r] < heap[smallest]) smallest = r;            if (smallest == i) break; // heap order restored            swap(i, smallest);            i = smallest;        }        return min;    }     int peek() { return heap[0]; }     int size() { return size; }     private void swap(int a, int b) {        int t = heap[a];        heap[a] = heap[b];        heap[b] = t;    }}
  • PriorityQueue is a min-heap. Max-heap: new PriorityQueue<>(Collections.reverseOrder()) or a reversed comparator.
  • Printing or iterating a PriorityQueue shows heap order, not sorted order. Only repeated poll() gives sorted output.
  • remove(Object) and contains are O(n): a heap can only find its minimum quickly.

int vs Integer: autoboxing traps

java== vs equalsjava.util.*
class IntegerCache {    /** Compares two boxed copies of the same int value, by reference and by value. */    static boolean[] compare(int value) {        Integer a = value, b = value; // autoboxing calls Integer.valueOf(value)        boolean sameObject = a == b; // compares REFERENCES        boolean sameValue = a.equals(b); // compares values: always true here        return new boolean[] {sameObject, sameValue};    }}
  • Integer.valueOf caches −128..127 (the upper bound can be raised with -XX:AutoBoxCacheMax). Outside it, == on a default JVM compares two different objects.
  • Unboxing null throws NullPointerException: int c = map.get(missingKey) crashes. Use getOrDefault.
  • list.remove(1) removes index 1 from a List<Integer>; list.remove(Integer.valueOf(1)) removes the value 1.

Ordering: Comparable & Comparator

javaComparable (natural order)java.util.*
class Natural {    /** A record with a natural order: by age, then by name. */    record Person(String name, int age) implements Comparable<Person> {        @Override        public int compareTo(Person other) {            int byAge = Integer.compare(age, other.age);  // never age - other.age            return byAge != 0 ? byAge : name.compareTo(other.name);        }    }     static List<Person> sorted(List<Person> people) {        List<Person> copy = new ArrayList<>(people);        Collections.sort(copy);                           // uses compareTo        return copy;    }}
  • Comparable = the one natural order of a type (compareTo). Comparator = any order you pass in (sorting, TreeMap, PriorityQueue).
  • Return negative / zero / positive. Integer.compare(a, b) does it safely; a - b overflows for far-apart values.
  • Readable chains: Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()).reversed().
Java API you will actually use
calldoescost
list.add(x) / list.get(i) / list.set(i, x)ArrayList basicsO(1) amortized / O(1) / O(1)
deque.push / pop / peekStack ops on ArrayDeque (front)O(1) amortized
deque.offer / poll / peekQueue ops on ArrayDeque (back in, front out)O(1) amortized
map.getOrDefault(k, 0)Value or a default (no null unboxing)O(1) average
map.merge(k, 1, Integer::sum)Count occurrences in one callO(1) average
map.computeIfAbsent(k, x -> new ArrayList<>())Get-or-create a groupO(1) average
treeMap.floorKey(k) / ceilingKey(k)Greatest key ≤ k / smallest key ≥ kO(log n)
treeSet.first() / last() / pollFirst()Min / max / remove min of a sorted setO(log n)
pq.offer(x) / pq.poll() / pq.peek()Heap insert / remove min / see minO(log n) / O(log n) / O(1)
Arrays.sort(a) / Arrays.sort(objs, cmp)Sort primitives / sort objects with a comparatorO(n log n)
Collections.reverseOrder()Comparator for descending orderO(1)
new StringBuilder().append(x).reverse().toString()Build, reverse, finish a stringO(n) total
Character.isLetterOrDigit(c) / toLowerCase(c)Classify / normalise charactersO(1)
Math.floorMod(a, m) / Math.abs / Math.maxNon-negative modulo and friendsO(1)
Integer.MAX_VALUE / Long.MAX_VALUESentinels for min/max searchesO(1)

Stack (LIFO) or queue (FIFO)

→ ArrayDeque

O(1) at both ends, faster than Stack and LinkedList.

Count things / group things

→ HashMap with merge / computeIfAbsent (int[26] for lowercase letters)

O(1) average per update; an array is even faster when keys are small integers.

"Have I seen it?"

→ HashSet

O(1) average add/contains.

Sorted keys, or nearest key ≤ / ≥ x

→ TreeMap / TreeSet

O(log n) with floor/ceiling/first/last.

Repeatedly take the smallest / largest

→ PriorityQueue (min-heap; reverse for max)

O(log n) offer/poll, O(1) peek.

Remember insertion order / build an LRU cache

→ LinkedHashMap (accessOrder = true + removeEldestEntry for LRU)

Hash speed with a predictable order.

A list you append to and index into

→ ArrayList (new ArrayList<>(n) if n is known)

O(1) get, amortized O(1) add at the end.

Fixed-size numbers (DP, counts, flags)

→ int[] / long[] / boolean[]

No boxing, contiguous memory, zero-initialised.

Build a string in a loop

→ StringBuilder

Amortized O(1) appends instead of O(n) copies.

07 · recognise

Spot the pattern

"Most recent", matching brackets, undo, monotonic stack

ArrayDeque as a stack

Level-by-level, BFS, "process in arrival order"

ArrayDeque as a queue

Frequencies, "how many times", grouping by a key

HashMap (merge / computeIfAbsent) or int[26]

"Closest value ≤ x", sorted keys while inserting, calendar/booking

TreeMap / TreeSet floor & ceiling

"k largest", "k closest", "next smallest event", merging k lists

PriorityQueue

Only lowercase letters

int[26] indexed by c − 'a'

Answers "modulo 10⁹+7" or values up to 10⁹ being multiplied

long arithmetic, reduce after each step

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • Comparing Integer or String values with ==: works for small numbers and literals, fails in hidden tests.
  • int c = map.get(key) when the key may be absent → NullPointerException from unboxing.
  • Comparator (a, b) -> a - b on values that can be far apart → overflow and a wrong order.
  • Expecting PriorityQueue iteration or toString() to be sorted.
  • list.remove(i) on a List<Integer> removing an index when you meant the value.
  • Using ArrayList.remove(0) as a queue: every poll shifts the whole list, O(n) each.
  • Arrays.asList(arr).add(x) → UnsupportedOperationException; and Arrays.asList(intArray) gives a List<int[]> of one element.
  • Using int[] as a HashMap key: arrays use identity equality, so convert to a String or List first.
  • -7 % 3 == -1 in Java. For indices that must be non-negative (circular arrays, hashing), use Math.floorMod.
  • Modifying a collection while looping over it with for-each → ConcurrentModificationException. Use an iterator's remove or removeIf.

tricks

  • Declare by interface, construct by class: Map<String, Integer> m = new HashMap<>();. Switching to TreeMap later is a one-word change.
  • Say why you picked a container in the interview: "ArrayDeque, because I need O(1) at both ends."
  • Bas itna yaad rakho: stack or queue → ArrayDeque, lookup → HashMap, order → TreeMap, next smallest → PriorityQueue.
  • Memorise the max-heap one-liner: new PriorityQueue<>(Collections.reverseOrder()).
  • For int[] pairs in a PriorityQueue: new PriorityQueue<int[]>((a, b) -> Integer.compare(a[0], b[0])).
  • Before submitting, scan for int sums/products that could exceed 2·10⁹.
  • Keep import java.util.*; at the top. LeetCode already includes it, but your local file and OAs may not.

09 · why & how

Questions you might be too shy to ask

Why can't I write List<int>?

Java generics only work with object types. int is a primitive, so collections use its wrapper Integer, and Java converts automatically (autoboxing). That's convenient but costs memory and time, which is why int[] is preferred for big numeric tables.

Why does a == b work for 100 but not for 1000 when both are Integer?

== checks whether two references point to the same object. Integer.valueOf keeps a cache of objects for −128..127, so both boxes of 100 are literally the same object. 1000 gets two separate objects. Use a.equals(b), or compare int values.

What do the empty <> in new HashMap<>() mean?

That's the diamond. The compiler copies the types from the left side for you. Map<String, Integer> m = new HashMap<>(); is the same as writing new HashMap<String, Integer>(). It saves typing and nothing else: no speed or behaviour difference.

HashMap or TreeMap?

HashMap by default: O(1) average. Pick TreeMap only when you need sorted keys or questions like "the largest key ≤ x" (floorKey). Those cost O(log n), but HashMap can't answer them at all.

How do I loop over a HashMap and get both the key and the value?

Loop over entrySet(): for (Map.Entry<String, Integer> e : map.entrySet()). Inside, e.getKey() and e.getValue() give you both, with no extra lookup. Need only keys? map.keySet(). Only values? map.values().

My HashMap of small Integer keys printed in sorted order. Can I rely on that?

No, it's a coincidence. An Integer's hash is the number itself, so in a fresh 16-bucket map keys 0..15 land in buckets 0..15, and printing walks the buckets in order. Now put 2 and 17 in a fresh map: it prints {17=…, 2=…}, because 17 % 16 = 1, so 17 sits in bucket 1, before 2's bucket 2. Need sorted? Use TreeMap. Need insertion order? Use LinkedHashMap.

What is Integer::sum inside map.merge(w, 1, Integer::sum)?

A method reference: a short way to write the lambda (oldValue, one) -> oldValue + one. If w is new, merge just stores 1. If w exists, it calls Integer.sum(old, 1) and stores the result. So {chai=2} becomes {chai=3}. Simple hai: one call for "insert or add".

If ArrayList sometimes copies the whole array, how is add O(1)?

Because the copies are rare and get rarer. In OpenJDK each grow makes room for about 50% more (an implementation detail: the Javadoc only promises "constant amortized time"). So 10 lakh adds trigger only about 30 grows and about 2.4 copies per add in total. Spread over all the adds, that's a constant: amortized O(1). A single add can still be O(n); the average never is.

Why ArrayDeque instead of Stack?

Stack is a legacy class built on Vector: its methods are synchronized (slower) and it exposes index-based methods a stack shouldn't have. The Java docs themselves recommend Deque implementations such as ArrayDeque.

ArrayDeque has push and offer, pop and poll. Which end does each one use?

push adds at the front; offer adds at the back. pop, poll and peek all work at the front. So push + pop = stack (LIFO), and offer + poll = queue (FIFO). Dhyan do: pick one pair per deque. Mixing push and offer on the same deque gives an order you didn't mean.

Is LinkedList ever the right choice?

Rarely in interviews. ArrayDeque beats it for stacks/queues, ArrayList beats it for indexing. It helps only when you hold an iterator and insert/remove in the middle in O(1). Even then, most problems want a hand-written linked list.

Do I need to know how HashMap works inside?

Be ready for it: "how does HashMap work?" is a common follow-up. This chapter's level is enough: an array of buckets, a hash picks the bucket, collisions share a bucket, the bucket array doubles once the map is more than 75% full (the load factor 0.75), and since Java 8 a crowded bucket becomes a tree. That lets you defend O(1) average and answer "what's the worst case?" calmly.

treeMap.floorKey(x) crashed my code with a NullPointerException. Why?

When no key is ≤ x, floorKey returns null (same for ceilingKey, lowerKey, higherKey). If you wrote int k = map.floorKey(x);, Java tries to unbox that null and throws. Store it as Integer k = map.floorKey(x); and check if (k != null) first.

There are so many methods. Do I have to memorise them all?

No. The ~15 calls in this chapter's API table cover almost every interview problem. Start with merge, getOrDefault, offer/poll, push/pop and floorKey; look the rest up while practising. They stick after a few problems.

10 · practice

Interview problems

Practise this chapter on these

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #242
    Valid Anagram
    Easyin Arrays & Strings

    Pick the container for the alphabet: int[26] for lowercase letters, HashMap<Character, Integer> for Unicode.

  2. #49
    Group Anagrams
    Mediumin Arrays & Strings

    computeIfAbsent with a String key, and why an int[] or char[] can't be a HashMap key (identity equals/hashCode).

  3. #347
    Top K Frequent Elements
    Mediumin Heaps

    merge(x, 1, Integer::sum) counting, then a PriorityQueue with a comparator: two Collections tools in one problem.

  4. #20
    Valid Parentheses
    Easyin Stacks

    ArrayDeque as a stack: push, pop, and isEmpty() before you pop.

  5. #729
    My Calendar I
    Mediumin BST

    TreeMap.floorEntry / ceilingEntry find the two neighbouring bookings in O(log n).

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    The Collections Framework = interfaces (List, Deque, Set, Map) + ready-made data structures behind them. Pick by the operation you need most.

  2. use it when

    Stack/queue → ArrayDeque. Seen it? Count? → HashSet/HashMap. Sorted or nearest key → TreeMap. Next smallest → PriorityQueue. Indexed list → ArrayList.

  3. cost

    HashMap O(1) avg · TreeMap O(log n) · PriorityQueue offer/poll O(log n), peek O(1) · ArrayList get O(1), add amortized O(1), remove(0) O(n).

  4. cost

    ArrayList grows by 1.5× (old + (old >> 1)): 10 lakh adds = only 30 grows (the first 10 slots, then 29 × 1.5), ~2.4 copies per add. Rare O(n) copies → amortized O(1).

  5. template

    map.merge(w, 1, Integer::sum); counts. map.computeIfAbsent(k, x -> new ArrayList<>()).add(v); groups.

  6. template

    Max-heap: new PriorityQueue<>(Collections.reverseOrder()). Pairs: new PriorityQueue<int[]>((a, b) -> Integer.compare(a[0], b[0])).

  7. trap

    Integer == compares references: true for −128..127 (the cache), false for 128 on a default JVM. Use equals, or unbox to int.

  8. trap

    int c = map.get(k) on a missing key → NullPointerException. (a, b) -> a - b overflows. Use getOrDefault and Integer.compare.

  9. pro tip

    Declare by interface: Deque<Integer> st = new ArrayDeque<>();. Then say why out loud: "ArrayDeque, O(1) at both ends."

12 · recall

Flip, remember, repeat

card 1 / 14
recall

Why use ArrayDeque instead of Stack for a stack?

tap or Space to flip ↻

Question 1: Why use ArrayDeque instead of Stack for a stack?

13 · check yourself

Quick quiz

  1. `Integer a = 128, b = 128;` On a default JVM, what is `a == b`?

  2. Which class should implement a stack in modern Java?

  3. A full ArrayList has capacity 10. You add one more element. What is the new capacity (JDK 17)?

  4. Since Java 8, what is the worst-case cost of `get` when all of a HashMap's `String` keys land in one bucket?

  5. You print a PriorityQueue after offering 3, 1, 2. What do you see?

  6. Why is `(a, b) -> a - b` a risky comparator?

  7. You need "the smallest key ≥ x" while also inserting keys. Which structure?

  8. `List<Integer> list = new ArrayList<>(List.of(5, 6, 7)); list.remove(1);` What's left?

  9. Which call counts word frequencies in one line?

0/0 correct · 9 left

14 · learn more

A second teacher, if you want one