Array
An array is a row of numbered lockers in a school hallway. Each locker holds one item. You can walk straight to locker №7 instantly because the lockers are evenly spaced and numbered—you don't have to check the other lockers first. That instant-access property is what makes arrays the fastest "go fetch me item X" structure that exists.
When to reach for it
- You know roughly how many elements you need.
- You need fast index access (e.g.,
nums[i]). - You're iterating over a fixed list, not constantly inserting in the middle.
Java essentials
// Declare & initialize
int[] nums = new int[10]; // all zeros
int[] vals = {3, 1, 4, 1, 5, 9}; // literal
// Access — O(1)
int first = vals[0];
int len = vals.length; // no parentheses!
// Iterate
for (int i = 0; i < vals.length; i++) { ... }
for (int v : vals) { ... } // enhanced-for
// 2D array
int[][] grid = new int[3][4]; // 3 rows, 4 cols
// Useful Arrays utility
Arrays.sort(vals); // in-place, O(n log n)
Arrays.fill(nums, -1); // set every element to -1
int[] copy = Arrays.copyOf(vals, vals.length);vals.length has no parentheses—it's a field, not a method. Strings use .length() (method). Collections use .size(). Mixing these up is a classic Java gotcha.
Complexity
| Access by index | O(1) |
| Search for value | O(n) |
| Insert at end (fixed array) | — |
| Insert at middle | O(n) |
String
A String is just an array of characters wearing a fancy dress. The key fact in Java: Strings are immutable. Once created, you cannot change a character. Every "modification" actually creates a brand-new String. This is great for safety, terrible for performance if you build a string inside a loop.
StringBuilder for repeated edits—it's like writing in pencil.
Java essentials
String s = "hello";
int n = s.length(); // method, with parens!
char c = s.charAt(0); // 'h'
// Compare with .equals() — NEVER ==
if (s.equals("hello")) { ... }
if (s.equalsIgnoreCase("HELLO")) { ... }
// Slicing
String sub = s.substring(1, 4); // "ell" — [start, end)
// Convert to char array
char[] chars = s.toCharArray();
// Building strings — USE StringBuilder for loops
StringBuilder sb = new StringBuilder();
for (char ch : chars) sb.append(ch);
String result = sb.toString();s1 == s2 compares references, not content. Always use s1.equals(s2). This trips up every Java beginner exactly once—make sure it's just once.
Character tricks
// Lowercase letter to index 0-25
int idx = c - 'a';
// Digit char to int
int d = c - '0';
// Character helpers
Character.isLetter(c);
Character.isDigit(c);
Character.toLowerCase(c);ArrayList
An ArrayList is an array that grows. Underneath, it's still a regular array—but when it fills up, it secretly creates a bigger one (typically 1.5× the size), copies everything over, and you keep adding. From the outside, it just feels like a list that never runs out of space.
When to use ArrayList over array
- You don't know the final size in advance.
- You need built-in helpers like
contains,indexOf,remove. - You want it to play nicely with Java's Collections framework (
Collections.sort, streams, etc.).
Java essentials
List<Integer> list = new ArrayList<>();
list.add(10); // append, amortized O(1)
list.add(0, 99); // insert at index, O(n)
list.get(2); // O(1)
list.set(2, 77); // overwrite, O(1)
list.remove(2); // remove by index, O(n)
list.remove(Integer.valueOf(77)); // remove by VALUE
list.size(); // .size() — method
list.contains(10); // O(n) — slow!
// Iterate
for (int v : list) { ... }
for (int i = 0; i < list.size(); i++) { ... }
// Sort
Collections.sort(list);
list.sort(Comparator.reverseOrder());list.remove(2) on a List<Integer> removes the element at index 2, not the value 2. To remove the value 2, write list.remove(Integer.valueOf(2)). This bug has hidden in production for decades.
Linked List
A linked list is a paper chain. Each link holds one piece of data and a pointer—an arrow—to the next link. You can't jump to the middle: you have to follow the arrows from the start. The payoff? Inserting or deleting in the middle is instant—you just snip and re-attach two pointers.
The node, hand-built
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}You'll see this exact class on almost every LeetCode linked-list problem. Memorize it.
The four moves you must know
// 1. Traverse
ListNode cur = head;
while (cur != null) {
System.out.println(cur.val);
cur = cur.next;
}
// 2. Reverse a linked list — THE classic technique
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next; // save next
curr.next = prev; // flip arrow
prev = curr; // advance prev
curr = next; // advance curr
}
return prev; // new head
// 3. Find the middle — slow/fast pointers
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow is now at the middle
// 4. Detect a cycle — Floyd's tortoise & hare
ListNode t = head, h = head;
while (h != null && h.next != null) {
t = t.next;
h = h.next.next;
if (t == h) return true; // cycle exists
}ListNode dummy = new ListNode(0);. Build off dummy.next, and return dummy.next at the end. This eliminates ugly null-checks for the first element.
Stack
A stack is a pile of dirty plates. You add a plate on top; you take a plate from the top. Last in, first out (LIFO). You never reach into the middle. That's the entire structure—and it's astonishingly useful: undo buttons, function call stacks, matching brackets, "next greater element" problems, and DFS all run on stacks.
Use cases that scream "stack"
- Matching pairs — brackets, tags, parentheses.
- "Next greater / smaller" problems — monotonic stack pattern.
- Undo / history — last action first to reverse.
- Reversing — pop order is the reverse of push order.
- Recursive simulation — when you don't want true recursion.
Java essentials
// Don't use the legacy `Stack` class — use ArrayDeque
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // add to top
stack.push(2);
stack.push(3);
int top = stack.peek(); // look at top → 3
int out = stack.pop(); // remove top → 3
boolean empty = stack.isEmpty();java.util.Stack?Stack class extends Vector, which is synchronized and slow. Every modern Java guide and interviewer prefers ArrayDeque for stack behavior.
Queue & Deque
A queue is a line at a chai stall. The first person to arrive is the first served. First in, first out (FIFO). A deque ("deck") is a double-ended queue—you can add or remove from either end. The queue is the bedrock of BFS (breadth-first search); the deque is what powers the sliding-window-maximum pattern.
Java essentials — Queue
Queue<Integer> queue = new ArrayDeque<>();
// or: Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // enqueue (returns false if full)
queue.offer(2);
int head = queue.peek(); // look — null if empty
int out = queue.poll(); // dequeue — null if empty
boolean e = queue.isEmpty();Java essentials — Deque
Deque<Integer> dq = new ArrayDeque<>();
dq.offerFirst(1); // add to front
dq.offerLast(2); // add to back
dq.peekFirst();
dq.peekLast();
dq.pollFirst(); // remove from front
dq.pollLast(); // remove from backoffer/poll/peekadd/remove/element) throws exceptions on edge cases. offer/poll/peek return special values (false, null)—much friendlier in loops.
HashMap & HashSet
If arrays are lockers in a hallway, a HashMap is the postal system. You hand the postman a name ("Riya Mehta"), and somehow—without checking every house—he delivers your letter to the right address in one step. The magic ingredient is a hash function that converts the name into an array index. HashMap stores key→value pairs; HashSet stores just keys ("is this name in the system?").
When to reach for it (almost always)
- "Have I seen this before?" → HashSet.
- "How many times has X appeared?" → HashMap<X, Integer> (frequency map).
- "Given a value, fetch its associated data fast." → HashMap.
- Deduplication, caching, lookups by key.
Java essentials
// HashMap
Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.get("apple"); // 3, or null if absent
map.getOrDefault("pear", 0); // 0 if missing — clutch for counters
map.containsKey("apple");
map.remove("apple");
// Frequency counter — the most common map pattern
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
// Iterate
for (Map.Entry<String, Integer> e : map.entrySet()) {
System.out.println(e.getKey() + " → " + e.getValue());
}
// HashSet
Set<Integer> seen = new HashSet<>();
seen.add(5);
if (seen.contains(5)) { ... }
seen.remove(5);equals() and hashCode(). Forgetting either is one of Java's most common bugs. For DSA problems, String, Integer, Long, and similar wrappers do this for you.
For pair-keys (like grid coordinates), encode them as a String
i + "," + j or as a long via (long)i * COLS + j.
TreeMap & TreeSet
A HashMap doesn't care about order—it scatters keys based on a hash. A TreeMap keeps its keys sorted at all times. It's slower per operation (O(log n) instead of O(1)), but in return it answers questions HashMap can't: "what's the smallest key bigger than X?" or "give me every key between A and B."
When to use TreeMap over HashMap
- You need keys in sorted order during iteration.
- You need "ceiling" or "floor" queries — smallest key ≥ X, or largest key ≤ X.
- You need range queries — all keys between A and B.
Java essentials
TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(3, "c");
tm.put(1, "a");
tm.put(5, "e");
tm.firstKey(); // 1
tm.lastKey(); // 5
tm.ceilingKey(2); // 3 (smallest ≥ 2)
tm.floorKey(4); // 3 (largest ≤ 4)
tm.higherKey(3); // 5 (strictly > 3)
tm.lowerKey(3); // 1 (strictly < 3)
tm.subMap(2, 5); // view: [2, 5)
// TreeSet is the same idea, no values
TreeSet<Integer> ts = new TreeSet<>();Heap / PriorityQueue
A heap is a hospital ER. Patients aren't seen in arrival order—they're seen in order of urgency. The receptionist always knows who the most critical patient is. Whenever a new patient walks in, they're slotted into the right priority. That's a heap: peek at the smallest (or largest) item in O(1), insert in O(log n), remove the top in O(log n).
Use cases that scream "heap"
- K-th largest / smallest — keep a heap of size K.
- Merge K sorted lists — heap of list heads.
- Dijkstra's shortest path — extract the closest unvisited node.
- Scheduling — always pick the most urgent next.
- Running median — two heaps facing each other.
Java essentials
// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.peek(); // 1 — smallest
minHeap.poll(); // 1, removes it
// Max-heap — supply a reverse comparator
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Comparator.reverseOrder());
// Heap of custom objects: sort by 2nd field ascending
PriorityQueue<int[]> pq =
new PriorityQueue<>((a, b) -> a[1] - b[1]);
// K-th largest: maintain a min-heap of size K
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> h = new PriorityQueue<>();
for (int n : nums) {
h.offer(n);
if (h.size() > k) h.poll();
}
return h.peek();
}Binary Tree
A binary tree is a family tree where each person has at most two children. There's one root at the top, and every node has a left and a right (either or both may be empty). Trees model anything hierarchical: file systems, decision processes, the DOM, expression evaluation, organization charts.
The node
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}The three depth-first traversals
The difference is when you visit the current node relative to its children:
// Pre-order: ROOT → LEFT → RIGHT (good for cloning a tree)
void pre(TreeNode n) {
if (n == null) return;
visit(n);
pre(n.left);
pre(n.right);
}
// In-order: LEFT → ROOT → RIGHT (sorted output on a BST)
void in(TreeNode n) {
if (n == null) return;
in(n.left);
visit(n);
in(n.right);
}
// Post-order: LEFT → RIGHT → ROOT (good for deletion, bottom-up DP)
void post(TreeNode n) {
if (n == null) return;
post(n.left);
post(n.right);
visit(n);
}Level-order traversal (BFS)
// Visit row by row — uses a queue
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode n = q.poll();
level.add(n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
res.add(level);
}
return res;
}if (node == null)), (2) what to do with the current node, and (3) recursive calls to left and right. If you can name those three pieces, you can solve it.
Binary Search Tree
A BST is a binary tree with one extra rule: every node's left subtree contains smaller values, and the right subtree contains larger values. That rule turns every search into a halving game—just like binary search, but on a tree. As long as the tree stays balanced, every operation is O(log n).
The killer property: in-order = sorted
If you in-order traverse a BST (left → root → right), you get the elements in sorted order. Use this. Many BST problems boil down to "run in-order and check something."
Search & insert
public TreeNode search(TreeNode root, int target) {
while (root != null && root.val != target) {
root = target < root.val ? root.left : root.right;
}
return root;
}
public TreeNode insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) root.left = insert(root.left, val);
else root.right = insert(root.right, val);
return root;
}TreeMap and TreeSet use a Red-Black tree, which self-balances. For interviews, you rarely implement balancing yourself.
Trie (Prefix Tree)
A trie is what powers your phone's autocomplete. It's a tree where each edge is a letter, and walking from the root to a node spells out a prefix. If thousands of words start with "pre"—precision, prefix, prepare, prevent—they all share the same "p → r → e" path through the tree. That shared path is what makes prefix queries blazing fast.
When to reach for it
- Autocomplete / type-ahead.
- Prefix matching ("how many words start with 'pre'?").
- Spell-check, word games like Boggle.
- IP routing tables (longest prefix match).
Java implementation
class Trie {
private Trie[] children = new Trie[26];
private boolean isEnd = false;
public void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new Trie();
node = node.children[i];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = find(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return find(prefix) != null;
}
private Trie find(String s) {
Trie node = this;
for (char c : s.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return null;
}
return node;
}
}Graph
A graph is a tree that gave up on having a single root and let nodes connect to anyone. Cities and the roads between them, users and their friendships, web pages and their links—anything where things connect to other things is a graph. Trees are just graphs with rules; once you can do graphs, trees come for free.
Two ways to store a graph
Adjacency list — for each node, a list of its neighbors. Compact when edges are sparse. This is what you'll use 95% of the time.
// Graph with n nodes (numbered 0 .. n-1)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
// edges: int[][] edges where edges[i] = {u, v}
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]); // omit this for directed graph
}Adjacency matrix — an n × n boolean grid. Wastes space for sparse graphs but lets you ask "is there an edge from i to j?" in O(1).
BFS — shortest path in an unweighted graph
public int shortestPath(List<List<Integer>> graph, int src, int dst) {
Queue<Integer> q = new ArrayDeque<>();
boolean[] seen = new boolean[graph.size()];
q.offer(src);
seen[src] = true;
int dist = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int node = q.poll();
if (node == dst) return dist;
for (int nb : graph.get(node)) {
if (!seen[nb]) {
seen[nb] = true;
q.offer(nb);
}
}
}
dist++;
}
return -1;
}DFS — exploring all reachable
void dfs(int node, List<List<Integer>> graph, boolean[] seen) {
if (seen[node]) return;
seen[node] = true;
for (int nb : graph.get(node)) dfs(nb, graph, seen);
}visited array or set, your BFS/DFS will loop forever. Mark a node as seen when you enqueue it, not when you dequeue it—otherwise you'll add duplicates to the queue.
Union-Find (Disjoint Set)
Union-Find answers one question really fast: "are these two things in the same group?" Start with everyone in their own group. As you process connections, merge groups. At any moment you can ask "are X and Y connected?" in essentially O(1). It's the secret weapon behind Kruskal's MST, dynamic connectivity, and a surprising number of LeetCode hards.
Java implementation
class UnionFind {
int[] parent, rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
// Find with PATH COMPRESSION
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
// Union by RANK — keeps tree shallow
boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false; // already same group
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; }
return true;
}
}With path compression and union by rank, both operations run in nearly O(1) — technically O(α(n)) where α is the inverse Ackermann function, which is at most 4 for any input you'll ever encounter.
You now have the containers. Next, the patterns that operate on them.