Java for DSA

Detailed Study Notes#

You open your binary search, run it on the tiny example, and it passes. You submit. It fails one hidden case — a giant array — with a wrong answer, no crash, no stack trace. The bug: (left + right) / 2 quietly overflowed int and wrapped to a negative index. Nothing about Java told you. This is the whole reason a "just the language" chapter exists: the parts of Java that decide whether your correct algorithm actually produces correct output are small, specific, and easy to miss.

Imports: one line and move on#

Before any logic, your file needs to import the classes it uses — the compiler's way of knowing where HashMap or PriorityQueue live. On LeetCode most of this is automatic, but on a bare interview editor it is not, and fumbling imports wastes clock.

The wildcard java.util.* pulls in nearly everything DSA needs. Write it once at the top and stop thinking about it.

import java.util.*;        // ArrayList, HashMap, HashSet, Queue, PriorityQueue, etc.
import java.util.Arrays;   // Arrays.sort(), Arrays.fill(), Arrays.asList()
import java.util.Collections; // Collections.sort(), Collections.reverseOrder()

Types and the overflow trap#

Java is statically typed: every variable declares its type up front. For problems, a handful of primitives cover almost everything. The one that bites is size — an int holds roughly ±2.1 billion, and a sum or product can slip past that without warning.

The classic trap is the binary-search midpoint. When left and right are both near a billion, left + right exceeds int range and wraps negative before the divide. Computing the gap first keeps every intermediate value in range:

// BUG: if left + right > Integer.MAX_VALUE, this overflows
int mid = (left + right) / 2;

// CORRECT: safe from overflow
int mid = left + (right - left) / 2;

Reach for long whenever intermediate math can outgrow int: prefix sums over large values (10⁵ elements each up to 10⁹ → 10¹⁴), products like n * (n - 1) near 10⁵, factorials and combinations, and modulo problems where the running sum grows before you take the mod.

int  wrong      = n * (n - 1);        // int overflow at n = 100000
long correct    = (long) n * (n - 1); // cast first: safe 64-bit multiply
long stillWrong = (long)(n * (n - 1));// too late: int multiply already wrapped

The ternary operator is a compact inline if/else, handy for small choices:

int result   = (a > b) ? a : b;            // same as Math.max(a, b)
String label = (count == 1) ? "item" : "items";

Operators: modulo, bits, and short-circuits#

Most operators behave as expected; a few carry interview-relevant surprises.

Modulo (%) can return negative results for negative operands — -7 % 3 is -1, not 2. That breaks cyclic-index and hashing logic. To force a non-negative remainder, use ((n % m) + m) % m.

Many problems ask for an answer "modulo 10⁹+7" to keep it inside int. Apply the mod during computation, not just at the end, so the accumulator never overflows:

private static final int MOD = 1_000_000_007; // underscores are legal, just readability

long result = 0;
for (int i = 0; i < n; i++) {
    result = (result + values[i]) % MOD;      // reduce as you go
}
return (int) result;

Bitwise operators unlock a whole class of problems. The XOR trick is the canonical example — XOR-ing every element cancels the pairs and leaves the lone value:

// nums = [4, 1, 2, 1, 2] — every value appears twice except one
int single = 0;
for (int num : nums) single ^= num;  // duplicates cancel
// single = 4

boolean isSet = (mask & (1 << i)) != 0; // check bit i
mask = mask | (1 << i);                 // set bit i
mask = mask & ~(1 << i);                // clear bit i
mask = mask ^ (1 << i);                 // toggle bit i
int count = Integer.bitCount(mask);    // count set bits

Short-circuit evaluation with && and || stops as soon as the result is decided, left to right. Order your conditions so the bounds check protects the access:

Methods and pass-by-value#

Java is always pass-by-value — but for objects, the value passed is the reference. That one sentence explains a surprising amount of behavior.

• Primitives are copied — changing a parameter inside a method never touches the caller.
• Objects / arrays pass a copied reference — you can mutate the contents (arr[i] = 5), but reassigning (arr = new int[10]) is invisible outside.

This is why an array swap helper works, and why you cannot write a method that swaps two int variables. It is also the engine of backtracking: a shared List is mutated down each branch and restored on the way back up.

private void backtrack(List<Integer> path, List<List<Integer>> results) {
    if (isComplete(path)) {
        results.add(new ArrayList<>(path)); // MUST copy, not add the reference
        return;
    }
    for (int choice : choices) {
        path.add(choice);                    // modify shared list
        backtrack(path, results);            // recurse
        path.remove(path.size() - 1);        // undo
    }
}

Autoboxing and its traps#

Collections can't hold primitives, so Java auto-wraps int as Integer, char as Character, and back again. That conversion is convenient and mostly invisible — which is exactly why its failure modes are sneaky.

Integer a = 200, b = 200;
a == b;        // false — reference comparison
a.equals(b);   // true  — value comparison

Integer c = 100, d = 100;
c == d;        // true  — both from the −128..127 cache (misleading!)

Two more sharp edges: unboxing a null throws NullPointerException, so prefer map.getOrDefault(key, 0) over a raw get that might return null. And each boxing allocates a heap object — in a tight loop over millions of elements, prefer primitive int[] to ArrayList<Integer>.

Arrays and the frequency-count trick#

Arrays are fixed-size, zero-indexed, and the default data structure of almost every problem. Default values differ by type and quietly matter: int[] starts at 0, boolean[] at false (perfect for visited arrays), object arrays like String[] at null (must initialize before use).

DP tables often need one extra row/column for the base case (new int[n + 1]). And matrix problems lean on a directions array to visit orthogonal neighbors without four copy-pasted blocks:

int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for (int[] dir : directions) {
    int nr = row + dir[0], nc = col + dir[1];
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
        // process neighbor (nr, nc)
    }
}
// diagonals too? add {-1,-1},{-1,1},{1,-1},{1,1}

The Arrays utility class carries the workhorses: sort, fill, copyOf, copyOfRange, and toString/deepToString for debugging.

Strings: immutable, so build them right#

Java strings are immutable — every modification creates a brand-new object. Concatenating in a loop with += therefore rebuilds the whole string each pass, turning an O(n) task into O(n²).

// BAD: O(n^2) — each += allocates a new String
String result = "";
for (char c : chars) result += c;

// GOOD: O(n) — one mutable buffer
StringBuilder sb = new StringBuilder();
for (char c : chars) sb.append(c);
String result = sb.toString();

Compare strings by content with .equals(). The == operator compares object identity; it appears to work for pooled literals but fails for strings built at runtime — an unreliable source of subtle bugs.

The highest-leverage string idiom is the character-to-index map. Because chars are numbers, c - 'a' maps 'a'..'z' to 0..25, giving you a 26-slot frequency array with no HashMap:

int[] freq = new int[26];
for (char c : s.toCharArray()) {
    freq[c - 'a']++;   // freq[0]='a', freq[1]='b', ...
}

Round out the toolkit with StringBuilder's insert, reverse, deleteCharAt, and setCharAt, plus the Character tests: isLetterOrDigit, isDigit, toLowerCase, and friends.

The Collections Framework#

Choosing the right collection is often the difference between an O(n) and an O(n²) solution. The framework splits into three families: ordered sequences (List), unique membership (Set), and key–value lookup (Map), plus queue/stack shapes.

ArrayList — the result list#

Amortized O(1) append and O(1) index access; O(n) search and removal. The two remove overloads are a classic trap.

HashMap & HashSet — O(1) lookups#

The most-used pair in all of DSA. HashMap gives average O(1) put/get/containsKey; HashSet gives O(1) membership. Frequency counting is the signature pattern:

Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.put(c, freq.getOrDefault(c, 0) + 1);
}

LinkedHashMap / TreeMap — order and sorting#

LinkedHashMap preserves insertion order and, in access-order mode, is the backbone of an LRU cache (override removeEldestEntry to auto-evict). TreeMap/TreeSet keep keys sorted with O(log n) navigation — floorKey, ceilingKey, lowerKey, higherKey, headMap, tailMap, subMap — ideal for range queries and sorted-window problems.

Queue & Deque — BFS and the "better stack"#

Every BFS starts with a queue. Capture queue.size() before the inner loop when you need level-order processing:

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startRow, startCol});
while (!queue.isEmpty()) {
    int size = queue.size();          // freeze this level's count
    for (int i = 0; i < size; i++) {
        int[] cell = queue.poll();
        // process cell, enqueue neighbors
    }
}

PriorityQueue — heaps#

A min-heap by default; wrap with Collections.reverseOrder() or a comparator for max-heaps and custom orders. O(log n) insert/remove, O(1) peek. Used for top-K, k-way merge, and Dijkstra.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

Sorting and comparators#

A comparator returns negative if the first element should come first, zero if equal, positive if it should come after. Java sorts primitives with Arrays.sort and objects/lists with a lambda comparator.

// sort intervals by start (merge-intervals pattern)
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

// multi-key: length, then lexicographic
Arrays.sort(words, Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

For descending order, Collections.reverseOrder() works on Integer[] and lists — but not on primitive int[]. For a primitive array, sort ascending and reverse manually, or switch to Integer[].

Functional shortcuts & null handling#

A few Java 8 map methods collapse common boilerplate. The standout is computeIfAbsent for building adjacency lists:

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.computeIfAbsent(node, k -> new ArrayList<>()).add(neighbor);

// also: map.merge(key, 1, Integer::sum)   — increment a counter
//       map.putIfAbsent(key, value)       — set only if absent

null is the top runtime-error source in DSA, showing up in tree/linked-list traversal, map lookups, and uninitialized object arrays. Three rules cover most cases: check for null before dereferencing (if (node.left != null)), prefer getOrDefault over get, and combine null + empty guards at the top of your solution (if (nums == null || nums.length == 0) return ...;).

Modifying collections while iterating#

Removing from a collection inside a for-each loop throws ConcurrentModificationException — the iterator detects the structural change mid-walk.

// safest: Iterator.remove()
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() % 2 == 0) it.remove();
}

Recursion and the call stack#

Every method call pushes a frame onto the call stack, which holds only a few thousand frames. Recurse too deep and you get a StackOverflowError — and Java, unlike some functional languages, does not optimize tail calls, so every recursive call adds a frame regardless.

When depth scales with input and the input can be large, convert recursion to iteration with an explicit ArrayDeque stack — same traversal, no frame limit.

void dfs(int start, boolean[] visited) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;
        visited[node] = true;
        for (int nb : graph.get(node)) {
            if (!visited[nb]) stack.push(nb);
        }
    }
}

Graph representation#

Java has no built-in graph type — you build the adjacency list yourself. Two shapes cover nearly everything, chosen by how the nodes are numbered.

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) {
    graph.get(e[0]).add(e[1]);
    graph.get(e[1]).add(e[0]); // omit for directed graphs
}

Weighted graphs store int[]{neighbor, weight} pairs, feeding a comparator-ordered PriorityQueue in Dijkstra.

Pairs, dedup, and everyday idioms#

Java has no built-in Pair. In practice, int[]{row, col} is the standard — fast and concise, at the cost of type safety. Use a small custom class only when clarity genuinely suffers.

For deduplication, the sorted-array approach is preferred (used in 3Sum/4Sum): sort, then skip equal neighbors.

Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
    if (i> 0 && nums[i] == nums[i - 1]) continue; // skip duplicate
    // process nums[i]
}

A grab-bag worth memorizing: ceiling division without floats is (a + b - 1) / b; sentinels are Integer.MAX_VALUE / MIN_VALUE; and deep-copying a 2D array needs a per-row clone() because a plain clone() copies only the outer array of shared row references.

Node classes for design problems#

DSA problems define custom nodes — a ListNode for linked lists, a TreeNode for trees. Fields are left package-private with no getters/setters: this is interview code under time pressure, not production software, so encapsulation adds no value.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

The two-argument ListNode constructor lets you build a list inline — new ListNode(1, new ListNode(2, new ListNode(3))) — which LeetCode often provides for you. this disambiguates the field from the same-named parameter in the constructor.

Interview & Practice Q&A#

The follow-ups this material naturally invites. Answer each aloud before expanding.

Key Takeaways#