glossary
Stuck on a word? Each one here has a one-line meaning, a tiny example, and the chapter that teaches it properly. Type to filter, or jump by letter.
194 terms
== asks "same object?"; equals() asks "same value?". For primitives, == compares values.
new String("a") == new String("a") is false; .equals is true.
Use == for int, char, boolean and for null checks. Use .equals() for String, Integer and your own classes.
Shortest paths when every edge weighs 0 or 1, using a deque instead of a heap: O(V + E).
A 0-weight edge's vertex goes to the front of the deque; a 1-weight edge's vertex goes to the back.
Same answers as Dijkstra, without the log factor.
A data type defined by what it does (its operations and their rules), not by how it's built.
"A stack has push, pop and peek, last in first out" is the ADT; an array or a linked list is how you build it.
In design questions, agree the API (method names, inputs, costs) first, then choose the structures inside.
For each vertex, a list of its neighbours. The standard way to store a graph: O(V + E) space.
List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
Visiting all neighbours of every vertex once costs O(V + E) in total.
A V × V table where m[u][v] says whether (or how heavily) u connects to v. O(V²) space.
Checking one edge is O(1), but listing a vertex's neighbours is O(V).
Good for small, dense graphs and for Floyd–Warshall; wasteful for big sparse ones.
The average cost per operation over a whole sequence, even if a few single operations are expensive.
ArrayList.add sometimes copies the whole array, but copies are rare enough that n adds cost O(n) in total: O(1) each, amortized.
Amortized is a guarantee over the sequence, not luck. That's different from "average case" over random inputs.
Two strings with exactly the same letters in the same counts, maybe in a different order.
"listen" and "silent" are anagrams. Check with a 26-slot count array: O(n).
Sorting both strings and comparing also works, in O(n log n).
A fixed-size row of same-type slots side by side in memory, read by index in O(1).
The address of slot i is start + i × slot size, so a[i] is one calculation, not a search. That's why indices start at 0.
The size is fixed at creation: new int[n]. Inserting in the middle means shifting everything after it: O(n).
Java's go-to stack and queue: a resizable ring buffer with O(1) (amortized) adds and removes at both ends.
As a stack: push, pop, peek (all at the front). As a queue: offer at the back, poll from the front.
Prefer it over the old Stack class, which is synchronized and built on Vector. It doesn't allow null elements.
also called dynamic array
A resizable array: O(1) get by index, amortized O(1) add at the end.
When it's full, Java allocates a bigger array and copies everything across. OpenJDK 17 grows it by about 1.5×; that's an implementation detail, not a promise of the spec.
That copy is rare, so add averages out to O(1). But add(0, x) or remove(0) shifts every element: O(n).
Java automatically converting between a primitive and its wrapper, like int ↔ Integer.
list.add(5) boxes 5 into an Integer; int x = list.get(0); unboxes it back.
It's convenient but not free: each boxed value can be a separate object, which is slower in hot loops.
Comparing two Integers with == compares references, not values. Use .equals() or unbox first.
Build a solution one choice at a time, and undo the last choice when it can't lead anywhere.
The template is choose → explore → un-choose: path.add(x); solve(…); path.remove(path.size() - 1);.
It explores a tree of choices, so it's often exponential. Pruning cuts the dead branches early.
A tree whose height stays about log n, so searches don't degrade into walking a long chain.
LeetCode's "height-balanced": at every node, the left and right subtree heights differ by at most 1.
Insert 1, 2, 3, 4, 5 into a plain BST and you get a chain of height n; balancing prevents that.
The smallest input a recursive method answers directly, without calling itself again.
For trees it's usually if (node == null) return 0;. For arrays, an empty range or one element.
Write it first. A missing base case means infinite recursion and a StackOverflowError.
Shortest paths that allow negative edge weights: relax every edge V − 1 times. O(V × E).
After V − 1 rounds every shortest path is found. If a V-th round still improves something, there's a negative cycle.
Also handles "at most k stops": run only k + 1 rounds, copying the distances each round.
Explore a graph in rings: first all neighbours, then their neighbours, using a queue. O(V + E).
In an unweighted graph, BFS reaches each vertex by a shortest path (fewest edges), like the fewest moves on a game map.
Mark a vertex visited when you add it to the queue, not when you poll it, or it can be added many times.
A way to say how fast work grows with input size n, ignoring constants: O(1), O(log n), O(n), O(n²)…
Formally it's an upper bound: f(n) is O(g(n)) if, beyond some n, f(n) ≤ c·g(n) for a constant c.
We drop constants and smaller terms: 3n² + 5n + 2 is O(n²). Doubling n roughly quadruples the work.
Ω is a lower bound ("at least this much"); Θ is a tight bound (both O and Ω).
Any comparison sort is Ω(n log n) in the worst case. Merge sort is Θ(n log n): never better, never worse.
In interviews people usually say "O" when they mean the tight bound. That's fine, but know the difference.
also called min-heap · max-heap
A complete binary tree in an array where every parent is ≤ its children (min-heap) or ≥ them (max-heap).
In a min-heap the smallest item is always at index 0. Insert and remove-min are O(log n): one sift up or down a single path.
For index i: parent (i - 1) / 2, children 2i + 1 and 2i + 2. Java's PriorityQueue is one.
Find a target in sorted data by halving the search range each step: O(log n).
Check the middle: if it's the target, you're done; if the target is bigger, drop the left half; if smaller, drop the right half.
Write the middle as lo + (hi - lo) / 2: (lo + hi) / 2 can overflow when both are large.
Binary-search over possible answers, using a yes/no check that is monotonic.
"Minimum speed to eat all bananas in h hours": if speed s works, every faster speed works too. Search s in 1..max.
Time is O(log(range) × cost of one check).
A binary tree where every node's left subtree holds smaller values and its right subtree bigger ones.
Search, insert and delete walk one path down: O(h), which is O(log n) when balanced but O(n) for a chain.
An inorder traversal of a BST gives its values in sorted order.
"Every node in the left subtree", not just the left child, must be smaller. That's the classic validation trap.
A tree where each node has at most two children, called left and right.
On LeetCode, TreeNode has val, left and right. A missing child is null.
A binary tree is not automatically sorted; that's a binary search tree.
A graph whose vertices split into two groups with every edge going between the groups, never inside one.
Test it by two-colouring with BFS/DFS: give each neighbour the opposite colour; a clash means not bipartite.
A graph is bipartite exactly when it has no cycle of odd length.
Move all bits left or right. x << k multiplies by 2ᵏ (if it doesn't overflow); x >> 1 halves, rounding down.
>> keeps the sign bit, so negatives stay negative. >>> fills with 0s: the unsigned shift.
1 << 31 is already negative (it's Integer.MIN_VALUE), and 1 << 32 is 1, because an int shift uses only the count's low 5 bits. For bits 31 and up as a positive long, use 1L << i.
An integer used as a set of yes/no flags: bit i is 1 when item i is included.
For 3 items, mask 5 (binary 101) means items 0 and 2. Loop masks 0 to (1 << n) - 1 to see all 2ⁿ subsets.
Check item i: (mask >> i) & 1. Integer.bitCount(mask) counts the chosen items.
Operators that work on each bit of an integer: & (and), | (or), ^ (xor), ~ (not).
x & 1 is 1 when x is odd. x | (1 << i) turns bit i on; x & ~(1 << i) turns it off.
Don't confuse them with && and ||, which work on booleans and short-circuit.
also called critical connection
An edge whose removal disconnects part of the graph.
Like the only road into a village: cut it and the village is cut off.
Find all bridges in one DFS (Tarjan's low-link method), O(V + E).
The simplest correct solution: try every possibility. Usually slow, always a good first step.
For "two numbers that add to target", check every pair: O(n²).
Saying it out loud first shows the interviewer you understand the problem; then you remove the bottleneck.
The stack of method calls still running. Each call gets a frame with its own parameters and local variables.
When main calls f, a frame for f is pushed on top. When f returns, its frame is popped and main continues.
Recursion is just many frames of the same method, each with its own n.
The exception stack trace you see is a printout of this stack.
A Java char is a 16-bit number (a UTF-16 code unit), so you can subtract and compare characters.
'c' - 'a' is 2, so count[c - 'a']++ maps a to 0 … z to 25 in an int[26].
'7' - '0' is the number 7. (char) ('a' + 2) is 'c'.
Uppercase letters come before lowercase: 'A' is 65, 'a' is 97.
also called ring buffer
A fixed array used as a loop: when the index passes the end, it wraps back to 0.
Move forward with i = (i + 1) % capacity. Keep a head index and a size, and nothing ever shifts.
ArrayDeque is a growable circular buffer under the hood.
Java's built-in data structures in java.util: lists, sets, maps, queues, plus helpers like Collections.sort.
The main ones for DSA: ArrayList, HashMap, HashSet, TreeMap, ArrayDeque, PriorityQueue.
Each is an interface + implementation pair, so picking one is picking a set of time costs.
An interface that gives a class its natural order through compareTo. Integer and String have one.
a.compareTo(b) returns a negative number if a comes first, 0 if equal, positive if a comes after.
Collections.sort(list) and TreeMap use this order when you don't pass a comparator.
An object that tells Java how to order two values, passed to sort, PriorityQueue or TreeMap.
compare(a, b) is negative when a should come first. Sort intervals by start: Arrays.sort(iv, Comparator.comparingInt(x -> x[0]));
Max-heap: new PriorityQueue<>(Comparator.reverseOrder()).
Avoid (a, b) -> a - b: the subtraction can overflow and flip the sign. Use Integer.compare(a, b).
A sort that only learns about the data by comparing two items at a time. None can beat O(n log n) in the worst case.
Merge sort, quicksort, heapsort and Java's TimSort are all comparison sorts.
To go faster you must use the values themselves, like counting sort does for small integer ranges.
A binary tree with every level full except maybe the last, which is filled from the left.
This shape lets a tree live in a plain array with no gaps: children of index i are at 2i + 1 and 2i + 2.
That's exactly how a binary heap is stored.
Thrown (best-effort) when a collection is changed while a for-each loop is walking over it.
for (int x : list) if (x == 0) list.remove(…); will usually crash with it, even in single-threaded code.
Fix: use iterator.remove(), list.removeIf(x -> x == 0), or collect changes and apply them after the loop.
A group of vertices where each can reach the others, and none can reach outside the group.
"Number of islands" counts connected components of land cells.
Count them by starting a BFS/DFS from each unvisited vertex, or with union-find.
also called input limits
The limits in a problem statement (like n ≤ 10⁵) that tell you how fast your solution must be.
A common rule of thumb is about 10⁸ simple steps per second. So n ≤ 10⁵ rules out O(n²) (10¹⁰ steps) but allows O(n log n).
n ≤ 20 hints at O(2ⁿ) (subsets); values up to 10⁹ hint that long may be needed for sums.
Sort small integers by counting each value, then writing them back in order: O(n + k) for values 0..k−1.
Exam marks 0–100: count each mark in an int[101], then output each mark as many times as it was counted.
Great when k is small; useless when values go up to 10⁹.
A path that comes back to where it started, like a linked list whose last node points back into the list.
In a directed graph, a cycle in prerequisites (A needs B, B needs A) means no valid order exists.
Detect it with three DFS colours (directed graphs), union-find (undirected edges), or fast/slow pointers (linked lists).
A directed graph with no cycles. Every DAG has at least one topological order.
Git history is a DAG: each commit points to its parents, and following those links never brings you back to where you started.
Build steps, course plans and spreadsheet formulas are DAGs too. DP on a DAG is easy in topological order.
Depth: how far a node is from the root. Height: the longest path from a node down to a leaf.
Many textbooks count edges (root depth 0), while LeetCode's "maximum depth" counts nodes (a single node has depth 1). Check which one the problem wants.
Height in code: 1 + Math.max(height(left), height(right)), with null giving 0. That counts nodes; for edges, return −1 at null.
A double-ended queue: add and remove at both the front and the back in O(1).
Pronounced "deck". Methods: offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast.
It can act as a stack or a queue, and powers sliding-window maximum and 0-1 BFS.
Explore a graph by going as deep as possible along one path before backing up. O(V + E).
Written with recursion or an explicit stack. Good for connected components, cycle detection and topological order.
DFS doesn't give shortest paths in general; BFS does (for unweighted graphs).
Record many range updates in O(1) each, then rebuild the final values with one prefix-sum pass.
To add v to every index in l..r: diff[l] += v; diff[r + 1] -= v;.
After all updates, a running sum over diff gives each index's final value: O(n + number of updates).
Shortest paths from one source when no edge weight is negative, using a min-heap of distances.
Always settle the closest unsettled vertex next, then relax its edges. With a binary heap: O((V + E) log V).
In Java, skip stale heap entries: if (d > dist[u]) continue;.
One negative edge can break it; use Bellman–Ford then.
In a directed graph each edge is one-way (u → v); in an undirected graph every edge goes both ways.
Course prerequisites and Git commits are directed. Friendships and two-way roads are undirected.
For an undirected edge [u, v], add it to both lists: adj.get(u).add(v); adj.get(v).add(u);.
A small array of moves like {{0,1},{1,0},{0,-1},{-1,0}} to visit a cell's neighbours in one loop.
for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; … } replaces four copy-pasted if blocks.
Always check 0 <= nr < rows and 0 <= nc < cols before reading the cell.
Split the problem into independent parts, solve each part recursively, then combine the answers.
Merge sort splits the array in half, sorts each half, then merges: O(n log n).
Unlike DP, the parts don't overlap, so there's nothing to cache.
A linked list where each node points to both the next and the previous node.
Removing a node you already hold is O(1): link its neighbours to each other.
That O(1) removal, plus a HashMap from key to node, is how an LRU cache works.
The few values that fully describe one subproblem, like dp[i] = the best answer for the first i items.
Say the state in one sentence before coding: "dp[i][j] is the edit distance between the first i letters of a and the first j letters of b."
Number of states × work per state = the DP's time.
also called trace table
Running your code by hand on a tiny input, writing each variable's value after each step.
Take [2, 7, 11], target 9: write i, nums[i], and the map after every loop pass.
It catches off-by-one errors and wrong updates before the judge does. The 3D sims are dry runs you can watch.
Solve a problem by combining answers to smaller overlapping subproblems, solving each one only once.
It needs two things: the same subproblems keep coming back, and the best answer is built from best sub-answers.
Like filling an Excel sheet where each cell is a formula over cells you already filled.
Steps: define the state, write the recurrence, set the base cases, pick the fill order.
An unusual input at the boundary of what's allowed, where code most often breaks.
Typical ones: empty input, one element, all equal values, negatives, duplicates, already sorted, and the maximum size.
Before coding, list two or three aloud. After coding, dry-run at least one.
also called Levenshtein distance
The fewest single-letter inserts, deletes and replacements that turn one string into another.
"horse" → "ros" takes 3 edits.
Two-string DP in O(n × m): each cell picks the cheapest of insert, delete, or replace (free if the letters match).
A type with a fixed set of named constants, like enum Dir { UP, DOWN, LEFT, RIGHT }.
Safer than magic numbers: the compiler only accepts real values.
Enums work in switch and have values() and ordinal(). Good for states in a machine-coding round.
A walk that uses every edge exactly once. An Euler circuit also ends where it started.
First, all edges must be in one connected piece (ignore arrows when checking). Undirected: a circuit needs every degree even; a path needs exactly 0 or 2 odd-degree vertices.
Directed: a circuit needs in-degree = out-degree at every vertex; a path also allows one start with one extra out-edge and one end with one extra in-edge.
Hierholzer's algorithm finds it in O(E). "Reconstruct Itinerary" is this problem in disguise.
An object Java throws when something goes wrong, which unwinds the call stack until something catches it.
ArrayIndexOutOfBoundsException, NullPointerException and ArithmeticException (divide by zero) are the common ones in DSA.
The stack trace's first line inside your code tells you exactly where to look.
A way to prove a greedy choice is safe: show that swapping it into any optimal answer never makes it worse.
For meetings, take the one that ends earliest: replacing an optimal plan's first meeting with it still leaves room for the rest.
If you can't find such an argument, try to find a counter-example. If you find one, use DP.
Work that multiplies with every extra element, like O(2ⁿ) or O(n!). Fine only for tiny n.
Listing all subsets of n items is 2ⁿ: about a million (1,048,576) for n = 20, already too much by n = 40.
Plain recursive Fibonacci is exponential; memoization makes it O(n).
also called Floyd's cycle detection · tortoise and hare
Two pointers through a list, one moving 2 steps for every 1 step of the other.
If there is a cycle, the fast one eventually meets the slow one inside it; if not, fast reaches null.
When fast reaches the end, slow is at the middle. O(n) time, O(1) space.
Reading and printing large input quickly, using BufferedReader and PrintWriter instead of Scanner and many printlns.
Scanner is convenient but slow for input with lakhs of numbers; that alone can cause a Time Limit Exceeded verdict.
Read whole lines with BufferedReader, split them, and print everything through one PrintWriter you flush at the end.
also called binary exponentiation
Computing aⁿ in O(log n) multiplications by squaring: a⁸ = ((a²)²)².
Look at n's bits: if the lowest bit is 1, multiply the answer by a; then square a and shift n right.
With a modulus, take % M after every multiplication.
also called binary indexed tree · BIT
A compact array that supports prefix sums and point updates in O(log n) each.
It's 1-indexed. Moving by the lowest set bit (i & -i) jumps between the slots responsible for each range.
Shorter to code than a segment tree, but handles fewer kinds of queries.
Starting from one cell, spreading to every connected cell with the same property, like a paint bucket tool.
It's BFS or DFS on a grid, using a direction array for the 4 neighbours.
Number of Islands = count how many times you start a new flood fill.
Shortest paths between every pair of vertices with three nested loops: O(V³).
For each middle vertex k, try dist[i][k] + dist[k][j] for every pair i, j. k must be the outer loop.
Fine for V up to a few hundred; works with negative edges (but not negative cycles).
also called counting array
An int[] where the index is the value and the slot counts how often it appears.
For lowercase letters: int[] count = new int[26]; count[c - 'a']++;.
Faster and lighter than a HashMap when the values fit a small known range.
A HashMap from each value to how many times it appears.
for (int x : nums) freq.merge(x, 1, Integer::sum);
Use it when values are big, negative or not numbers at all (like words). For a–z, a frequency array is simpler.
The JVM automatically frees objects that no reference can reach any more.
You never call free in Java. Once nothing points to an object, the garbage collector may reclaim its memory.
Unlink a node from a list (prev.next = node.next) and, once nothing else points to it, it can be collected.
GCD: the largest number dividing both a and b. LCM: the smallest number both divide.
Euclid's algorithm: gcd(a, b) = gcd(b, a % b), ending at gcd(a, 0) = a. gcd(12, 18) = 6.
lcm(a, b) = a / gcd(a, b) * b. Divide first so the product doesn't overflow.
Type parameters like <T> that let one class work for many types safely: List<String>, Map<Integer, Long>.
The compiler checks the types, so List<String> can't accidentally hold an Integer.
Type arguments must be reference types (objects), so it's List<Integer>, never List<int>.
new ArrayList<>() uses the diamond <>: Java infers the type from the left side.
A set of things (vertices) and connections between them (edges). Trees, grids and maps are all graphs.
Cities and roads, people and friendships, courses and prerequisites, web pages and links.
Many graph problems become much easier once you build the adjacency list and pick BFS or DFS.
At each step, take the choice that looks best right now, and never go back.
Fast and simple, but only correct when you can prove local choices lead to the best total.
Coins {1, 3, 4} for 6: greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 (2 coins) is better. That problem needs DP.
Two different keys landing in the same bucket of a hash table.
Collisions are normal; the table must handle them. Java's HashMap keeps colliding keys in a small list in that bucket.
Since Java 8, a bucket that grows past 8 keys becomes a small red-black tree (if the table has at least 64 buckets; otherwise the table grows instead), so a crowded bucket usually costs O(log n), not O(n).
A function that turns a key into a number used to pick a bucket in a hash table.
A good hash spreads keys evenly, so each bucket stays tiny and lookups stay O(1) on average.
Java's HashMap mixes the high bits of hashCode() into the low bits before choosing the bucket.
If two objects are equals, they must return the same hashCode(). Override both or neither.
HashMap first jumps to a bucket using hashCode(), then checks keys with equals().
A class with equals but no matching hashCode gets "lost" in a HashSet: contains usually says false for an equal key.
Arrays don't override either, so an int[] key is compared by identity. Use a record, List<Integer> or a string key.
Java's key → value table: average O(1) put, get and containsKey.
map.merge(x, 1, Integer::sum) counts; map.getOrDefault(x, 0) reads a missing key as 0.
map.computeIfAbsent(k, z -> new ArrayList<>()).add(v) builds a list per key in one line.
It promises no iteration order (small Integer keys may come out sorted, by luck). Use TreeMap or LinkedHashMap when order matters.
A collection of unique values with average O(1) add, remove and contains. Built on a HashMap.
if (!seen.add(x)) … checks and inserts in one step: add returns false when x was already there.
Great for "have I seen this before?", like duplicates or a visited set in BFS.
The memory area where every object made with new lives, until the garbage collector frees it.
Local variables live in the method's stack frame; the objects they point to live on the heap.
Not the same thing as the heap data structure (a priority queue). Same word, two meanings.
Too many live objects gives OutOfMemoryError; too many nested calls gives StackOverflowError.
also called build heap
Turning an unsorted array into a heap in O(n) by sifting down from the last parent to the root.
Most nodes are near the bottom and sift down only a little, so the total is O(n), not O(n log n).
In OpenJDK, new PriorityQueue<>(collection) builds its heap this way (the Javadoc doesn't promise a cost). Calling offer n times is O(n log n).
An object that can never change after it is created. Java's String is immutable.
s.toUpperCase() does not change s; it returns a new String.
Immutable objects are safe to share and safe as HashMap keys, because their hash can't change.
A graph you never store: you generate a vertex's neighbours when you need them.
Word Ladder: each word is a vertex, and its neighbours are the words one letter different.
Lock combinations, puzzle boards and grid states work the same way. Keep the visited set as a HashSet of states.
also called degree
In a directed graph, in-degree counts edges coming in to a vertex; out-degree counts edges going out.
For a course plan, a course's in-degree is how many prerequisites it still waits for. In-degree 0 means "ready to take".
In an undirected graph there's just "degree": the number of neighbours.
Changing the input itself instead of building a new copy, using O(1) extra space.
Reversing an array by swapping a[i] and a[n - 1 - i] is in-place; copying into a new array is not.
If the problem says "in-place", the judge checks the array you were given (sometimes along with a returned length).
Autoboxing (Integer.valueOf) always reuses one shared object for each value from −128 to 127.
The Java spec requires this range. Values outside it are usually new objects (a JVM flag can grow the cache).
So Integer a = 100, b = 100; a == b is true (same cached object), but with 1000 it is usually false.
This is why map.get(x) == map.get(y) works in small tests and fails on big inputs.
Always compare boxed values with .equals() or Integer.compare.
When a result is too big for its type, Java silently wraps around instead of throwing an error.
An int holds −2,147,483,648 to 2,147,483,647. Integer.MAX_VALUE + 1 gives Integer.MIN_VALUE.
Use long for sums of many values or products like a * b when both can be near 10⁹: (long) a * b.
Math.abs(Integer.MIN_VALUE) is still negative, because +2,147,483,648 doesn't fit in an int.
A contract: a list of methods a class promises to have. List is an interface; ArrayList implements it.
Write List<Integer> list = new ArrayList<>(); so your code depends on the contract, not one implementation.
Queue<Integer> q = new ArrayDeque<>(); lets you use only the queue methods, which keeps intent clear.
An interval is a range [start, end]. Two closed intervals overlap when each starts no later than the other ends.
[a, b] and [c, d] overlap exactly when a <= d && c <= b.
Most interval problems start by sorting by start (to merge) or by end (to schedule).
Choosing the most non-overlapping intervals: sort by end time and greedily keep each one that fits.
Picking an end-earliest meeting leaves the most time for the rest.
"Minimum removals to make no overlap" is n minus this count.
A fact your loop keeps true at every step. It's how you know the loop is correct.
Binary search: "if the target exists, it's inside [lo, hi]". Each step must keep that true.
Writing the invariant as a comment before coding fixes most off-by-one bugs.
Finds the maximum-sum subarray in one pass: O(n) time, O(1) space.
At each index, either extend the best subarray ending just before, or start fresh here: cur = max(x, cur + x).
Keep the best cur seen. For [-2, 1, -3, 4, -1, 2, 1] the answer is 6 ([4, -1, 2, 1]).
Topological sort by repeatedly taking a vertex with in-degree 0 and removing its outgoing edges.
Queue every in-degree-0 vertex; poll one, add it to the order, and decrement its neighbours' in-degrees.
If the final order has fewer than V vertices, the rest are stuck on a cycle or behind one.
also called prefix function · lps array
Finds a pattern in a text in O(n + m) without ever moving backwards in the text after a mismatch.
It precomputes, for each prefix of the pattern, the longest proper prefix that is also a suffix (the lps array).
On a mismatch, the lps value says how much of the pattern is already matched, so the text pointer never moves back.
Pick items with weights and values to get the most value under a weight limit W.
0/1 knapsack (each item once): loop capacity from W down to the item's weight. Unbounded (reuse allowed): loop upwards.
O(n × W): fast when W is small. "Partition equal subset sum" and "target sum" are knapsacks in disguise.
In a segment tree, postponing a range update by leaving a note on a node, and pushing it down only when needed.
"Add 5 to every index in 2..900" then costs O(log n) instead of touching every element.
Before visiting a node's children, push its pending note down to them.
Visiting a tree level by level, top to bottom, using a queue: BFS on a tree.
Inside the loop, read int size = q.size(); first, then poll exactly that many nodes. That's one level.
Use it for "right side view", "zigzag" and "minimum depth" questions.
Dictionary order: compare character by character, and the first difference decides.
"apple" < "apply" because 'e' < 'y'. A prefix comes first: "app" < "apple".
Java's compareTo compares char values, so "Zebra" comes before "apple" ('Z' is 90, 'a' is 97).
A chain of nodes where each node holds a value and a reference to the next node.
No index: reaching the k-th node means walking k steps, O(k). But inserting after a known node is O(1).
On LeetCode, ListNode has int val and ListNode next; the last node's next is null.
A HashMap that also remembers order (insertion order, or access order if you ask), using a linked list.
With accessOrder = true and an overridden removeEldestEntry, it becomes an LRU cache in a few lines.
In an interview, you may be asked to build that same LRU from a HashMap and a doubly linked list yourself.
How full a hash table may get before it grows. Java's HashMap default is 0.75.
With the default 16 buckets, the table doubles to 32 when it holds more than 12 entries (16 × 0.75).
Growing keeps buckets short. Each resize is O(n), but rare, so put stays O(1) amortized.
also called logarithm
How many times you can halve n before reaching 1. In DSA, log means log base 2.
log₂(1,024) = 10, and log₂(10⁶) is about 20. So binary search finds an item among 10 lakh in about 20 steps.
O(log n) shows up whenever each step throws away half: binary search, balanced trees, heaps.
The longest sequence that appears, in order, in both of two strings.
LCS of "abcde" and "ace" is "ace": length 3.
dp[i][j]: if the letters match, 1 + dp[i-1][j-1], else max(dp[i-1][j], dp[i][j-1]). O(n × m).
File diff tools use the same idea to find what changed between two versions.
The longest subsequence whose values strictly increase.
In [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 18]: length 4.
Simple DP is O(n²). Keeping the smallest possible tail for each length, with binary search, gives O(n log n).
Lower bound: the first index with a value ≥ x. Upper bound: the first index with a value > x.
In [1, 2, 2, 2, 5], for x = 2: lower bound is 1, upper bound is 4, so 2 appears 4 − 1 = 3 times.
If x is bigger than everything, both return n (one past the end). Java's TreeMap.ceilingKey is a similar idea for keys.
The deepest node that has both given nodes in its subtree. A node counts as its own ancestor.
Like the closest shared folder of two files in File Explorer.
In a BST, walk down from the root: go left if both values are smaller, right if both are bigger, else you're at the LCA.
A fixed-size cache that throws out the Least Recently Used item when it's full.
Like a browser cache keeping your recent pages. get and put must both be O(1).
Build it with a HashMap (key → node) and a doubly linked list ordered by recent use.
A shortcut for the time of divide-and-conquer recursions like T(n) = a·T(n/b) + O(nᵈ).
Merge sort is T(n) = 2T(n/2) + O(n), which solves to O(n log n). Binary search is T(n) = T(n/2) + O(1): O(log n).
If you forget it, draw the recursion tree and add the work level by level. You get the same answer.
Caching the result of each recursive call so the same subproblem is never solved twice.
Keep a long[] memo (or a HashMap); at the start of the call, return the saved value if it exists.
Fibonacci drops from O(2ⁿ)-ish to O(n). This is top-down dynamic programming.
Split the array in half, sort each half, then merge the two sorted halves: always O(n log n).
Merging two sorted lists is one pass with a pointer in each, always taking the smaller head.
It's stable and uses O(n) extra space for merging.
In a two-player game, you pick the move that is best for you, assuming the opponent then picks what's worst for you.
Game DP often stores the score difference ("my total minus yours") for whatever is left, like dp[i][j] for a row of coins.
Then dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1]).
The cheapest set of edges that connects every vertex of a weighted graph, with no cycles.
Like laying the least cable to connect every office: n offices need exactly n − 1 links.
Kruskal: sort edges, add each one that joins two different groups (union-find). Prim: grow one tree with a min-heap.
Doing arithmetic on remainders. Problems ask for the answer "mod 10⁹ + 7" when the true number is huge.
Take the remainder after every + and *: (a + b) % M and (a * b) % M, so values never grow.
10⁹ + 7 is prime and fits in an int; the product of two such remainders fits in a long. Multiply in long.
Only ever moving in one direction: always non-decreasing, or always non-increasing.
[1, 3, 3, 7] is monotonic (non-decreasing). A yes/no test like "can we finish in d days?" is monotonic if once it's yes, it stays yes.
Monotonic is what makes binary search and monotonic stacks work.
A deque of indices kept in sorted order of their values, giving the max (or min) of every window in O(1).
For the window maximum: pop smaller values from the back before adding, and drop the front once it leaves the window.
The front is always the current window's maximum. Total time O(n) for all windows.
A stack kept in sorted order by popping everything that breaks the order before each push.
For "next greater element": while the top is smaller than x, pop it, because x is that element's answer.
Every element is pushed and popped at most once, so the whole pass is O(n).
A BFS that starts with many sources in the queue at once, so every cell gets its distance to the nearest one.
"Rotting oranges": put every rotten orange in the queue first; each BFS level is one minute.
Same O(V + E) as a normal BFS, instead of one BFS per source.
The number of ways to choose r items from n when order doesn't matter.
5C2 = 10: from {a, b, c, d, e} there are 10 pairs.
Pascal's rule builds them without overflow-prone factorials: C(n, r) = C(n−1, r−1) + C(n−1, r).
A cycle whose edge weights add up to less than zero, so going around it again always gets "shorter".
With one reachable, "shortest path" has no answer: you could loop forever.
Bellman–Ford and Floyd–Warshall can detect one; Dijkstra cannot.
In Java, % keeps the sign of the left number, so -7 % 3 is -1. Math.floorMod(-7, 3) is 2.
This bites in circular indexing: (i - 1) % n is −1 when i is 0, which is not a valid index.
Use Math.floorMod(i - 1, n) or ((i - 1) % n + n) % n to always land in 0..n−1.
Thrown when you use a reference that is null: call a method on it, read a field, or index it.
TreeNode left = root.left; left.val crashes when root.left is null.
In tree and list code, check if (node == null) return …; first. That line is often the base case too.
Unboxing a null Integer (from map.get(key) with a missing key) also throws it.
A bug where a loop or index is one too many or one too few: < vs <=, n vs n - 1.
An array of length n has indices 0 to n − 1, so for (int i = 0; i <= n; i++) reads past the end.
Fix by deciding what each bound means (inclusive or exclusive) and checking with a dry run on 1–2 elements.
In interview talk, the best time and space you can reasonably reach for the problem's limits.
Usually the brute force with its slow part replaced: a nested loop becomes a HashMap lookup, a re-scan becomes a window.
"Optimal" is about the constraints. O(n log n) is fine for n = 10⁵; you don't always need O(n).
The best answer to a problem can be built from the best answers to its subproblems.
A shortest path from A to C through B contains a shortest path from A to B.
Without it, neither DP nor greedy can work.
When a recursion solves the same smaller problem again and again. It's the sign that DP will help.
In plain recursive Fibonacci, fib(3) is computed again in many branches of the recursion tree.
If subproblems never repeat (like merge sort's halves), caching gives nothing: that's divide and conquer.
A string that reads the same forwards and backwards, like "racecar" or "abba".
Check with two pointers from both ends moving inward: O(n) time, O(1) space.
To find palindromic substrings, expand around each centre; there are 2n − 1 centres (letters and gaps).
Rearranging an array in-place so items matching a rule come first and the rest after.
Quicksort partitions around a pivot. "Move zeroes to the end" is a partition too.
Three-way partition (Dutch national flag) splits into less / equal / greater in one O(n) pass.
Java always passes a copy of the variable into a method. For objects, the copy is the reference.
Changing an int parameter never changes the caller's variable.
Passing an array copies the address, so arr[0] = 1 inside the method is seen by the caller.
But arr = new int[5] inside the method only re-points the local copy. The caller's array is untouched.
A sequence of vertices where each consecutive pair is joined by an edge.
Its length is the number of edges, or the sum of weights in a weighted graph.
A simple path never repeats a vertex.
An arrangement of all items in some order. n distinct items have n! permutations.
[1, 2, 3] has 3! = 6: 123, 132, 213, 231, 312, 321.
n! grows very fast (10! = 3,628,800), so generating all permutations is only for small n.
The element a partition step compares everything against, in quicksort and quickselect.
In the common (Lomuto) partition, the pivot ends at its final sorted position: smaller items to its left, bigger to its right.
A pivot near the median splits the work evenly; a bad pivot (always the minimum) makes quicksort O(n²).
also called Reverse Polish notation · RPN
Writing operators after their operands, like 3 4 +, so no brackets or precedence rules are needed.
Evaluate with a stack: push numbers; on an operator, pop two, apply it, push the result.
3 4 + 2 * means (3 + 4) × 2 = 14.
An array where pre[i] is the sum of the first i elements, so any range sum is one subtraction.
For [2, 4, 1]: pre = [0, 2, 6, 7]. Sum of indices 1..2 is pre[3] - pre[1] = 7 - 2 = 5.
Build once in O(n), answer each range query in O(1). The extra leading 0 removes special cases.
Three depth-first orders for visiting a binary tree: node first, node in the middle, or node last.
Preorder: node, left, right (copying a tree). Inorder: left, node, right (a BST comes out sorted). Postorder: left, right, node (sizes, heights, deleting).
All three are O(n) time and O(h) stack space, where h is the height.
A plain value type built into Java: int, long, double, char, boolean, byte, short, float.
A primitive holds the value itself, not a pointer to an object. int x = 5; stores the number 5 right in x.
Primitives can't be null and have no methods. Fields and array slots start at a default: 0, false, or '\u0000'.
In hot loops, int[] beats List<Integer> because there is no object per number.
Java's binary heap. By default poll() returns the smallest element: a min-heap.
offer and poll are O(log n); peek is O(1). remove(x) for an arbitrary x is O(n).
Max-heap: new PriorityQueue<>(Comparator.reverseOrder()). Iterating over it is not in sorted order.
Skipping a whole branch of a search as soon as you know it can't produce a valid or better answer.
In Combination Sum with sorted candidates, stop the loop once a candidate is bigger than the remaining target.
In N-Queens, never place a queen on an attacked column or diagonal.
also called FIFO
First in, first out: add at the back, remove from the front, like a print queue.
offer and poll are O(1). In Java: Queue<Integer> q = new ArrayDeque<>();.
poll returns null when empty, while remove throws. BFS is built on a queue.
A queue made of an "in" stack and an "out" stack, with amortized O(1) operations.
Push onto in. To pop, if out is empty, move everything from in to out (which reverses the order), then pop out.
Each element moves at most once, so n operations cost O(n) in total.
Find the k-th smallest item by partitioning and recursing into only one side: O(n) on average.
After one partition, if the pivot lands at index k you're done; otherwise go left or right, never both.
Worst case is O(n²) like quicksort. A size-k heap is the safe O(n log k) alternative.
Pick a pivot, partition smaller items left and bigger items right, then sort each side.
O(n log n) on average, O(n²) in the worst case when pivots are always the smallest or largest. Random pivots make that very unlikely.
It sorts in-place but is not stable.
A compact, immutable data class (standard since Java 16). Java writes the constructor, getters, equals, hashCode and toString.
record Point(int r, int c) {} gives you p.r(), p.c() and value-based equals/hashCode for free.
That makes records good HashMap/HashSet keys for pairs, like a visited set of grid cells.
also called transition
The formula that computes a state from smaller states.
Climbing stairs: dp[i] = dp[i - 1] + dp[i - 2] (last step was 1 or 2).
Each term in the formula is one choice for the last move. Missing a choice is the usual bug.
A method that solves a problem by calling itself on a smaller version of the same problem.
fact(n) = n * fact(n - 1), and fact(0) = 1 stops it.
Trust the smaller call to be correct, and only think about one step. That "leap of faith" is the whole trick.
A drawing of every call a recursive method makes: each call is a node, its sub-calls are its children.
fib(5) calls fib(4) and fib(3), and so on. Count the nodes to get the time.
If the same call (like fib(3)) appears many times in the tree, memoization will help.
A variable that holds the address of an object, not the object itself.
int[] a = new int[3]; creates the array on the heap; a only stores where it lives.
int[] b = a; copies the address, so b[0] = 9 also changes a[0]. Two names, one array.
null means the reference points at nothing.
Improving a vertex's best-known distance through a neighbour: if dist[u] + w < dist[v], set dist[v].
Every shortest-path algorithm here is a way to choose which edges to relax, and in what order.
Start with dist[source] = 0 and every other distance at "infinity" (a large value like Integer.MAX_VALUE, used carefully).
A hash of a window of text that updates in O(1) as the window slides one character.
Treat the window as a number in some base; remove the leaving character's part and add the new one, all modulo M.
Rabin–Karp uses it to find a pattern in O(n + m) on average. Equal hashes must still be checked, because of collisions.
The root is the top node; a parent points to its children; a leaf has no children.
Nodes with the same parent are siblings. Everything below a node is its subtree.
In code a leaf is node.left == null && node.right == null.
Storing a grid row by row, so cell (r, c) of a grid with cols columns is at index r * cols + c.
Lets you turn a 2D cell into one number, for a visited array or union-find, and back: r = i / cols, c = i % cols.
In Java, int[][] is an array of row arrays, so looping row by row is the natural (and cache-friendly) order.
A tree over an array where each node stores a summary (sum, min, max) of a range: O(log n) query and update.
The root covers the whole array; each child covers half of its parent's range. An array of 4n slots is always enough.
Use it when values change between range queries, so a plain prefix sum would need rebuilding.
also called AVL tree · red-black tree
A BST that rotates nodes after inserts and deletes to keep its height O(log n).
AVL and red-black trees are the classic kinds. Java's TreeMap and TreeSet are red-black trees.
You'll rarely code one in an interview; you use TreeMap and explain why it's O(log n).
also called dummy node · dummy head
A fake node placed before the real head, so the head never needs special-case code.
ListNode dummy = new ListNode(0); dummy.next = head; … return dummy.next;
Deleting or inserting at the front now works like anywhere else, and building a result list needs no if (head == null).
Turning a data structure into a string (or bytes) so it can be saved or sent, and rebuilt later.
A tree as preorder with # for each null: 1,2,#,#,3,#,#. The markers make the shape unambiguous.
LeetCode prints trees in level order with null: [1,2,3,null,4].
The path between two vertices with the fewest edges, or the smallest total weight.
Unweighted: BFS. Non-negative weights: Dijkstra. Negative weights: Bellman–Ford. Every pair: Floyd–Warshall.
Network routing and map apps are shortest-path problems at huge scale.
Find all primes up to n by crossing out the multiples of each prime: O(n log log n).
Start from 2; cross out 4, 6, 8…; move to the next uncrossed number (3) and repeat.
You can start crossing at p·p, because smaller multiples were already crossed by smaller primes.
Keep a contiguous range [left, right] and slide it, updating its summary instead of recounting.
Fixed size k: add the element entering, remove the one leaving. Variable size: grow right, shrink left while the window breaks a rule.
Each index enters and leaves at most once, so it's O(n) even with a while inside the for.
How much extra memory your solution needs as the input grows, written in Big-O.
Interviewers usually mean auxiliary space: memory beyond the input. A HashMap of n keys is O(n).
Recursion counts too: each call on the stack uses space, so a recursion n deep is O(n) space.
A sort that keeps equal items in their original order.
Sort students by marks: with a stable sort, Rahul stays before Priya if both have 90 and he was first.
Java's Arrays.sort for objects and Collections.sort are guaranteed stable (TimSort). For primitives, Arrays.sort uses Dual-Pivot Quicksort, which is not stable, but that can't matter: equal numbers are identical.
also called LIFO
Last in, first out: you add and remove only at the top, like Ctrl+Z undoing your latest change first.
push, pop and peek are O(1). In Java use Deque<Integer> st = new ArrayDeque<>();.
Use it for matching brackets, undo history, "nearest bigger" questions, and turning recursion into a loop.
Java's error when nested calls use up all the stack space, usually recursion that never stops.
A missing or unreachable base case means every call makes another call, forever.
Even correct recursion can overflow when it goes very deep, for example DFS down a path of 10⁵ nodes.
Fix: check the base case first; for very deep inputs, switch to a loop with your own ArrayDeque.
also called stdin · stdout
The text stream a program reads from (System.in) and writes to (System.out).
Online assessments often give input on stdin and compare what you print on stdout with the expected output.
On a strict judge, an extra space or a missing newline can turn a right answer into a Wrong Answer verdict.
also called finite-state machine
A small set of states plus rules for moving between them on each input character or event.
Parsing "is this a valid number?" is easier as states like sign, digits, dot, exponent than as nested ifs.
The same idea drives DP problems like stock buying with a cooldown: each day you're in a state (holding, resting…).
A class declared inside another with static. It doesn't need an outer object, unlike an inner class.
Helper types like static class Node { int val; Node next; } should be static nested classes.
A non-static inner class silently keeps a reference to its outer object and can't be created from static main without one.
Comparing your fast solution with a simple brute force on many random small inputs, to find a failing case.
Generate random arrays of size 1–8, run both, and stop at the first input where the answers differ.
That tiny failing input is much easier to debug than a hidden test case.
The JVM keeps one shared copy of each string literal, so equal literals are the same object.
"hi" == "hi" is true (same pooled object), but a string built at runtime is a new object.
So == on strings sometimes "works" and then fails on real input. Always use s.equals(t).
A growable, changeable buffer of characters, for building a string piece by piece.
s += c in a loop copies the whole string every time: O(n²) for n characters.
StringBuilder sb = new StringBuilder(); sb.append(c); grows in place: O(n) in total, then sb.toString() once.
It also has reverse(), insert(), setCharAt() and deleteCharAt().
In a directed graph, a largest group of vertices where every vertex can reach every other.
Squash each SCC into one vertex and what remains is always a DAG.
Kosaraju's and Tarjan's algorithms find all SCCs in O(V + E).
A contiguous slice of an array: no gaps allowed.
In [1, 2, 3], [1, 2] and [2, 3] are subarrays; [1, 3] is not.
An array of n elements has n(n+1)/2 non-empty subarrays, so checking all of them is O(n²) or worse.
"Subarray" in a problem hints at sliding windows, prefix sums or Kadane.
A subarray must be contiguous; a subsequence keeps the order but may skip elements.
In [3, 1, 4]: [3, 1] is both; [3, 4] is a subsequence but not a subarray; [4, 3] is neither (order changed).
n elements have 2ⁿ subsequences (counting the empty one) but only n(n+1)/2 non-empty subarrays.
Subsequence problems usually need DP; subarray problems often need a window or prefix sums.
Any selection of elements where order doesn't matter, including the empty set and the whole set.
{1, 2, 3} has 2³ = 8 subsets: each element is either in or out.
Generate them with backtracking (take / skip), or with a bitmask from 0 to 2ⁿ − 1.
A contiguous part of a string: the string version of a subarray.
"abc".substring(1, 3) is "bc": start index included, end index excluded.
substring copies characters, so calling it inside a loop adds O(length) each time.
A node together with everything below it. Every node is the root of its own subtree.
Tree recursion works because a subtree is itself a full tree: solve both subtrees, then combine at the node.
"Subtree of another tree" asks whether some node's subtree is identical to a given tree.
Turn intervals into start and end events, sort them by time, and scan left to right keeping a running count.
Meeting rooms: +1 at each start, −1 at each end; the highest running count is the number of rooms needed.
At equal times, decide which comes first (an end before a start, for touching meetings) and say it out loud.
also called bottom-up DP
Filling a DP table from the smallest subproblems up with loops, instead of recursion with a memo.
No recursion means no stack overflow on large inputs.
If dp[i] only needs the last row or two, keep just those (rolling variables) and drop the space to O(1) or O(row).
How the number of steps grows as the input grows, written in Big-O.
One loop over n items: O(n). A loop inside a loop over the same items: O(n²). Halving each step: O(log n).
Count the work per element and the number of elements; that usually gives the answer.
Using extra memory to save time, or the other way round.
Two Sum with a HashMap uses O(n) extra space to drop the time from O(n²) to O(n).
Interviewers like hearing you name the trade-off before you choose.
Keep the k best items with a heap of size k: O(n log k).
For the k largest, use a min-heap: push each item and pop when the size passes k. The heap's top is the k-th largest.
Like a cricket leaderboard that only keeps the top 10 scores: any new score has to beat the smallest of them.
An ordering of a DAG's vertices where every edge u → v puts u before v.
For courses: every prerequisite comes before the course that needs it. There can be many valid orders.
It exists only if the graph has no cycle. Find it with Kahn's algorithm or reverse DFS post-order, both O(V + E).
A hierarchy of nodes with one root, where every other node has exactly one parent and there are no cycles.
Your File Explorer is a tree: folders inside folders, one top-level drive.
A tree with n nodes always has exactly n − 1 edges.
Solve a tree problem by asking both children for their answers, then combining them at the current node.
Max depth: if (node == null) return 0; return 1 + Math.max(depth(node.left), depth(node.right));
Decide two things: what each call returns, and what happens at null.
A sorted map (a red-black tree): O(log n) put/get, plus floor, ceiling, first and last keys.
map.floorKey(x) gives the largest key ≤ x; ceilingKey(x) the smallest key ≥ x.
Use it when you need "the nearest key" or keys in sorted order. TreeSet is the set version.
also called prefix tree
A tree of characters where each path from the root spells a prefix, so prefix lookups take O(length of word).
Contacts search on your phone: type "Pr" and every name under that path (Priya, Pranav…) is right there.
Each node has up to 26 children (TrieNode[] next = new TrieNode[26]) and an isWord flag.
Two indices moving through the data in a coordinated way, replacing a nested loop with one pass.
Opposite ends: in a sorted array, move left up if the sum is too small, right down if too big: O(n) for pair sums.
Same direction: a slow "write" pointer and a fast "read" pointer filter an array in-place.
How Java stores negative integers: −x is the bits of x flipped, plus 1.
So the top bit acts as the sign, and ~x == -x - 1. In a 32-bit int, −1 is all 32 bits set.
x & -x keeps only the lowest 1-bit of x, and x & (x - 1) clears it. Fenwick trees use the first trick.
also called DSU · disjoint set union
Tracks which items are in the same group, with near-O(1) find (which group?) and union (merge groups).
Each item points to a parent; the root names the group. Path compression and union by size keep trees flat.
With both, each operation is O(α(n)) amortized, where α is the inverse Ackermann function: tiny for any real n.
Great for "are these connected?" as edges keep arriving, and for Kruskal's MST.
also called online judge
What an online judge says about your submission: Accepted, Wrong Answer, Time Limit Exceeded, Memory Limit Exceeded, Runtime Error.
WA: wrong output on some test. TLE: correct idea maybe, but too slow for the limits. RE: it crashed, like an exception.
Each verdict points to a different fix: WA → edge cases, TLE → better complexity or fast I/O, RE → nulls and bounds.
also called node
A vertex (or node) is one thing in a graph; an edge connects two vertices.
In problems, vertices are usually numbered 0..n−1, and edges come as pairs like [0, 1].
V is the number of vertices and E the number of edges, so BFS is written O(V + E).
A record of which vertices you've already reached, so a search never processes one twice or loops forever.
Use boolean[] seen = new boolean[n] for numbered vertices, or a HashSet for strings or states.
On grids you can mark cells in the input itself (like setting '1' to '0'), if changing the input is allowed.
A graph where each edge carries a number: a distance, time, or cost.
Store neighbours as pairs: List<int[]> with {next, weight}.
With weights, BFS no longer finds the cheapest path; use Dijkstra (non-negative) or Bellman–Ford (negatives allowed).
The cost on the hardest input, on a typical (random) input, and on the easiest input.
Quicksort: O(n log n) on average, O(n²) in the worst case (bad pivots every time).
HashMap.get is O(1) on average; the worst case depends on collisions.
When you state a complexity, say which one you mean.
The object version of a primitive: Integer for int, Long, Character, Boolean, Double…
Collections store objects only, so List<int> is not allowed; you write List<Integer>.
A wrapper can be null, and has helpers like Integer.parseInt("42") and Character.isDigit(c).
a ^ b sets a bit when exactly one of the two bits is 1. Equal values cancel: a ^ a = 0.
Also a ^ 0 = a, and order doesn't matter. So XOR of [4, 1, 2, 1, 2] leaves the single number 4.
That "pairs cancel" trick finds a missing or unpaired number in O(n) time and O(1) space.