The Java toolbox for DSA

Java gives you every structure an interview needs: lists, hash maps, stacks, queues, heaps and sorted maps. The risk is in the small print. Some calls look like one step but walk the whole list, and some give a wrong number with no error at all.

This lesson lists what each tool costs, the six traps that break correct ideas, and which class to pick for a stack, a queue and a heap.

Arrays and ArrayList

An int[] has a fixed size. An ArrayList grows as you add, and keeps its items in numbered slots like an array.

• Adding or removing at the end touches one slot.
• Adding or removing at the front moves every other item one slot over.

In a test on this laptop with Java 21:

• Emptying 100,000 items with list.remove(0) took about 0.3 seconds.
• Twice the items took about four times as long: the mark of O(n²).
• An ArrayDeque emptied the same items with poll() in under a millisecond.

remove(int) or remove(Object)

ArrayList<Integer> has two remove methods. An int argument means a position. An Integer means a value.

java

List<Integer> list = new ArrayList<>(List.of(10, 20, 30));
list.remove(1);                   // removes the item at index 1
System.out.println(list);         // [10, 30]
list.remove(Integer.valueOf(10)); // removes the value 10
System.out.println(list);         // [30]

What each operation costs

A method call is not one step. list.contains(x) inside a loop is a hidden loop inside a loop: O(n²).

HashMap and HashSet

Two tools solve a large share of array problems:

• HashSet answers "have I seen this?" in one step.
• HashMap answers "how many?" or "where?" in one step.

The counting pattern you will write most often:

java

Map<Character, Integer> count = new HashMap<>();
for (char ch : "banana".toCharArray()) {
    count.merge(ch, 1, Integer::sum);
}
System.out.println(count);          // {a=3, b=1, n=2}
System.out.println(count.get('z')); // null

• merge(ch, 1, Integer::sum) puts 1 the first time and adds 1 after that.
• The longer form does the same: count.put(ch, count.getOrDefault(ch, 0) + 1).
• get returns null for a missing key. Unboxing that null into an int throws a NullPointerException.

Two rules keep a map or set correct:

• Arrays are compared by identity, not by content. A Set<int[]> never finds a new int[]{1, 2}. For a grid cell, use List.of(row, col) or the number row * cols + col as the key.
• A HashMap keeps no order. Use LinkedHashMap for insertion order and TreeMap for sorted keys.

Stacks, queues and heaps

Java ships all three. Pick these classes:

java

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop());    // 2: last in, first out

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(4);
queue.offer(9);
System.out.println(queue.poll());   // 4: first in, first out

PriorityQueue<Integer> minHeap = new PriorityQueue<>(List.of(5, 1, 8));
System.out.println(minHeap.poll()); // 1: smallest first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.addAll(List.of(5, 1, 8));
System.out.println(maxHeap.poll()); // 8: largest first

• The Java docs say ArrayDeque is likely faster than Stack as a stack, and faster than LinkedList as a queue.
• Why not negate values for a max-heap? -Integer.MIN_VALUE is still -2147483648, so one value lands in the wrong place.

Six traps

1. int overflows without a warning

An int ends at 2,147,483,647 (2³¹ − 1). One more wraps around to the most negative value.

java

int big = Integer.MAX_VALUE;
System.out.println(big + 1);   // -2147483648
int a = 100_000;
long wrong = a * a;            // multiplied as int first
long right = (long) a * a;     // cast before the multiply
System.out.println(wrong);     // 1410065408
System.out.println(right);     // 10000000000

• Use long (up to about 9.2 × 10¹⁸) for sums of many values and for products.
• long wrong = a * a is still wrong: the multiply happens in int, and only the broken result is widened.

2. Division drops the fraction, and % keeps the sign

java

System.out.println(7 / 2);                // 3
System.out.println(-7 / 2);               // -3: rounds toward zero
System.out.println(-7 % 3);               // -1: the sign follows the left side
System.out.println(Math.floorMod(-7, 3)); // 2

• / on two int values drops the fraction. For negative values, it rounds toward zero.
• % can return a negative number. Math.floorMod always returns a value from 0 to m − 1.

You use % 10 and / 10 in the next lesson to take a number apart, digit by digit.

3. == on Integer compares objects

int is a plain value. Integer is an object, and collections hold only objects. Java converts between them for you: boxing.

┌──────────────────────────────────────────────────┐
│                                                  │
│   Integer x = 127, y = 127;    x == y is true    │
│   x ──┐                                          │
│       ├──▶ [ 127 ]   one shared object           │
│   y ──┘                                          │
│                                                  │
│   Integer p = 128, q = 128;    p == q is false   │
│   p ─────▶ [ 128 ]   object 1                    │
│   q ─────▶ [ 128 ]   object 2                    │
│                                                  │
└──────────────────────────────────────────────────┘

java

Integer x = 127, y = 127;
System.out.println(x == y);      // true
Integer p = 128, q = 128;
System.out.println(p == q);      // false
System.out.println(p.equals(q)); // true

== asks "the same object?". It passes on small test values and fails on large ones.

This bites when you compare two counts with map.get(a) == map.get(b). Use equals, or store the values in int variables first.

The same rule holds for strings: compare them with equals, never ==.

4. Sorting: int[] or Integer[]

java

int[] nums = {5, 2, 9};
Arrays.sort(nums);                                  // [2, 5, 9]
Integer[] boxed = {5, 2, 9};
Arrays.sort(boxed, Collections.reverseOrder());     // [9, 5, 2]
Integer[] big = {2_000_000_000, -2_000_000_000, 0};
Arrays.sort(big, (a, b) -> a - b);                  // [2000000000, -2000000000, 0]
Arrays.sort(big, (a, b) -> Integer.compare(a, b));  // [-2000000000, 0, 2000000000]

• Arrays.sort on an int[] sorts small to large and takes no comparator. For another order, use an Integer[] or a List<Integer>.
• a - b overflows when the values are far apart, and the sort comes out wrong. Write comparators with Integer.compare.
• To sort pairs by their first item: Arrays.sort(pairs, (p, q) -> Integer.compare(p[0], q[0])).

5. Strings cannot change

Every String method returns a new string. To build one piece by piece, use a StringBuilder.

java

String s = "hello";
s.toUpperCase();              // returns "HELLO", s stays "hello"
StringBuilder sb = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--) sb.append(s.charAt(i));
System.out.println(sb);       // olleh
int[] freq = new int[26];
for (char ch : "banana".toCharArray()) freq[ch - 'a']++;
System.out.println(freq[0]);  // 3: the count of 'a'

• result += c in a loop copies the whole string each time: O(n²). append is O(1) on average.
• A char is a number. ch - 'a' turns 'a' to 'z' into 0 to 25, a ready index for a count array.

6. The shared list

Arrays.fill puts the same object in every slot. Add to one list, and all of them change.

┌────────────────────────────────────────────┐
│                                            │
│        Arrays.fill: one shared list        │
│        adj[0] ──┐                          │
│        adj[1] ──┼──▶ [ 1 ]                 │
│        adj[2] ──┘                          │
│                                            │
│        a loop: three lists                 │
│        adj[0] ─────▶ [ 1 ]                 │
│        adj[1] ─────▶ [ ]                   │
│        adj[2] ─────▶ [ ]                   │
│                                            │
└────────────────────────────────────────────┘

java

List<Integer>[] bad = new List[3];
Arrays.fill(bad, new ArrayList<>());
bad[0].add(1);                          // [[1], [1], [1]]

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < 3; i++) adj.add(new ArrayList<>());
adj.get(0).add(1);                      // [[1], [], []]

The loop calls new ArrayList<>() once per slot, so each slot gets its own list. A grid made with new int[3][3] is safe: Java builds a new row for each slot.

Read more

• ArrayList in the Java 21 API, with the cost of each operation
• ArrayDeque in the Java 21 API, the class to use as a stack or a queue
• PriorityQueue in the Java 21 API, on the heap order and its costs
• Integer.valueOf(int) in the Java 21 API, on the cache from -128 to 127

Next: working with digits. Skip the other toolbox lessons unless you code in those languages too. You will take a number apart with % and /.