LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

☕ JAVA

LeetCode Hard
Complete Mastery Guide
Concepts · Algorithms · Mathematical Formulas · Optimizations · Java Syntax

📘 Core Concepts Data 📐 Math Formulas Modular, ⚡ Optimizations

Structures, Algorithms & Combinatorics & Geometry Time/Space Tricks & Best
Patterns Practices

Page 1
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 1 — PROBLEM-SOLVING FRAMEWORK

🧠 Hard Problem Mindset & Strategy

Every LeetCode Hard problem, regardless of topic, can be cracked with a repeatable 5-step process:

Step Action
1. Read & Parse Identify input/output types, constraints, edge cases
(n=0, negatives, duplicates)
2. Brute Force First Think O(n²) or O(n³) — this shows you understand the
problem
3. Identify Pattern Does it need sliding window? DP? Monotonic stack?
(see section 2)
4. Optimize Remove nested loops with hashing, sorting, binary
search, or math
5. Code + Verify Write clean code, test on examples, check edge
cases, analyze complexity

🔍 Pattern Recognition Cheat Sheet

When you see this in the problem — think this pattern:

Problem Clue Best Pattern to Try

'Contiguous subarray' / 'window' Sliding Window or Monotonic Deque
'Sorted array' / 'search for value' Binary Search (possibly on answer)
'All permutations / subsets' Backtracking with pruning
'Shortest path' / weighted graph Dijkstra / Bellman-Ford / BFS
'Minimum cost over choices' Dynamic Programming (top-down or bottom-up)
'Overlapping intervals' Sort by start, then greedy merge or heap
'Count subarrays with property' Prefix Sum + HashMap
'Next greater / smaller element' Monotonic Stack
'Top K elements' Heap (PriorityQueue) or QuickSelect
'Tree path / LCA' DFS with return value or Binary Lifting
'String matching / repeated pattern' KMP, Rabin-Karp, or Trie
'Connected components' Union-Find (DSU) or BFS/DFS
Divide into two halves optimally Divide & Conquer or Segment Tree
'Matrix / grid traversal' BFS with state or DP on grid

Page 2
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 2 — ESSENTIAL DATA STRUCTURES

Data Structures for Hard Problems

1. Arrays, Strings & Prefix Sums
Prefix sums convert range-query problems from O(n) per query to O(1) after O(n) preprocessing.
// Prefix Sum Array
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
// Range sum [l, r] in O(1):
int rangeSum = prefix[r+1] - prefix[l];

// 2D Prefix Sum
int[][] p = new int[m+1][n+1];
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++)
p[i][j] = grid[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
// Submatrix sum (r1,c1) to (r2,c2):
int sum = p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];

2. HashMap / HashSet — The O(1) Lookup Weapon

// Frequency map pattern
Map<Integer,Integer> freq = new HashMap<>();
for (int x : nums) [Link](x, 1, Integer::sum);

// Two-Sum O(n) using HashMap

Map<Integer,Integer> seen = new HashMap<>();
for (int i = 0; i < [Link]; i++) {
int complement = target - nums[i];
if ([Link](complement)) return new int[]{[Link](complement), i};
[Link](nums[i], i);
}

3. Stack & Monotonic Stack

Monotonic stacks solve 'next greater/smaller element' problems in O(n).
// Next Greater Element — O(n)
int[] nge = new int[n];
[Link](nge, -1);
Deque<Integer> stack = new ArrayDeque<>(); // stores indices
for (int i = 0; i < n; i++) {
while (![Link]() && nums[[Link]()] < nums[i]) {
nge[[Link]()] = nums[i];
}
[Link](i);
}

// Largest Rectangle in Histogram (classic hard) — O(n)

// Uses monotonic increasing stack of indices

Page 3
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

4. Heap / Priority Queue

// Min-Heap (default in Java)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());

// Custom comparator (e.g., sort by second element)

PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);

// Top-K pattern: maintain heap of size K

for (int x : nums) {
[Link](x);
if ([Link]() > k) [Link]();
}
// [Link]() = Kth largest element

5. Deque (Monotonic Deque) — Sliding Window Maximum

// Sliding window maximum — O(n)
int[] result = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // stores indices
for (int i = 0; i < n; i++) {
// Remove indices outside window
while (![Link]() && [Link]() < i - k + 1) [Link]();
// Remove smaller elements (maintain decreasing deque)
while (![Link]() && nums[[Link]()] < nums[i]) [Link]();
[Link](i);
if (i >= k - 1) result[i - k + 1] = nums[[Link]()];
}

6. Trie (Prefix Tree)

class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
}
class Trie {
TrieNode root = new TrieNode();
void insert(String word) {
TrieNode node = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null) [Link][idx] = new TrieNode();
node = [Link][idx];
}
[Link] = true;
}
boolean search(String word) {
TrieNode node = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null) return false;
node = [Link][idx];
}
return [Link];
}
}

Page 4
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

7. Union-Find (Disjoint Set Union)

Connects components in near-O(1) with path compression + union by rank.
class DSU {
int[] parent, rank;
DSU(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) { // Path compression
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
boolean union(int x, int y) { // Union by rank
int px = find(x), py = find(y);
if (px == py) return false;
if (rank[px] < rank[py]) { int t=px; px=py; py=t; }
parent[py] = px;
if (rank[px] == rank[py]) rank[px]++;
return true;
}
}

8. Segment Tree
Supports range queries AND point updates in O(log n).
class SegmentTree {
int[] tree;
int n;
SegmentTree(int[] nums) {
n = [Link];
tree = new int[4 * n];
build(nums, 0, 0, n - 1);
}
void build(int[] nums, int node, int start, int end) {
if (start == end) { tree[node] = nums[start]; return; }
int mid = (start + end) / 2;
build(nums, 2*node+1, start, mid);
build(nums, 2*node+2, mid+1, end);
tree[node] = tree[2*node+1] + tree[2*node+2]; // sum tree
}
void update(int node, int start, int end, int idx, int val) {
if (start == end) { tree[node] = val; return; }
int mid = (start + end) / 2;
if (idx <= mid) update(2*node+1, start, mid, idx, val);
else update(2*node+2, mid+1, end, idx, val);
tree[node] = tree[2*node+1] + tree[2*node+2];
}
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(2*node+1,start,mid,l,r) + query(2*node+2,mid+1,end,l,r);
}
}

Page 5
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 3 — CORE ALGORITHMS & PATTERNS

⚙️Algorithms & Techniques

1. Two Pointers
Classic technique for sorted arrays. Eliminates the inner loop of a brute-force O(n²) solution.
// 3Sum — O(n²) with two pointers
[Link](nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < [Link] - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // skip duplicates
int l = i + 1, r = [Link] - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
[Link]([Link](nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++; r--;
} else if (sum < 0) l++;
else r--;
}
}

2. Sliding Window
// Minimum window substring — O(n+m)
Map<Character,Integer> need = new HashMap<>();
for (char c : [Link]()) [Link](c, 1, Integer::sum);
int left=0, formed=0, required=[Link]();
int[] ans = {-1, 0, 0}; // {window_len, left, right}
Map<Character,Integer> window = new HashMap<>();
for (int right = 0; right < [Link](); right++) {
char c = [Link](right);
[Link](c, 1, Integer::sum);
if ([Link](c) && [Link](c).equals([Link](c))) formed++;
while (formed == required) {
if (ans[0] == -1 || right-left+1 < ans[0])
ans = new int[]{right-left+1, left, right};
char lc = [Link](left++);
[Link](lc, -1, Integer::sum);
if ([Link](lc) && [Link](lc) < [Link](lc)) formed--;
}
}

3. Binary Search — Beyond Simple Search

Binary search can be applied to ANSWERS, not just sorted arrays. If f(x) is monotonic, binary search
the answer space.
// Template: Binary search on ANSWER
int lo = minPossible, hi = maxPossible;
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // avoids integer overflow

Page 6
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization
if (feasible(mid)) hi = mid; // look for smaller valid answer
else lo = mid + 1;
}
return lo; // smallest valid answer

// Example: Find first bad version

// isBadVersion(mid) == true? search left : search right

// Tip: lo + (hi - lo) / 2 NEVER overflows unlike (lo + hi) / 2

4. Backtracking with Pruning

// Permutations with backtracking
void backtrack(int[] nums, boolean[] used, List<Integer> curr,
List<List<Integer>> result) {
if ([Link]() == [Link]) {
[Link](new ArrayList<>(curr));
return;
}
for (int i = 0; i < [Link]; i++) {
if (used[i]) continue;
// PRUNING: skip duplicates in sorted array
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
[Link](nums[i]);
backtrack(nums, used, curr, result);
[Link]([Link]() - 1); // UNDO (backtrack)
used[i] = false;
}
}

5. Dynamic Programming — The Hard Problem King

Most LeetCode Hard problems involve DP. Master these templates:

5a. 1D DP — Fibonacci / Knapsack Style

// 0/1 Knapsack — O(n*W)
int[] dp = new int[W + 1];
for (int[] item : items) { // [weight, value]
for (int w = W; w >= item[0]; w--) { // iterate RIGHT to LEFT
dp[w] = [Link](dp[w], dp[w - item[0]] + item[1]);
}
}

// Unbounded Knapsack (items can repeat)

for (int[] item : items) {
for (int w = item[0]; w <= W; w++) { // iterate LEFT to RIGHT
dp[w] = [Link](dp[w], dp[w - item[0]] + item[1]);
}
}

5b. 2D DP — Substring / Sequence

// Longest Common Subsequence — O(m*n)
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {

Page 7
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization
if ([Link](i-1) == [Link](j-1))
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
}
}

// Edit Distance — O(m*n)

dp[i][j] = ([Link](i-1) == [Link](j-1)) ? dp[i-1][j-1]
: 1 + [Link](dp[i-1][j-1], // replace
[Link](dp[i-1][j], // delete
dp[i][j-1])); // insert

5c. DP on Intervals
// Matrix Chain Multiplication / Burst Balloons style
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) { // length of interval
for (int i = 0; i + len - 1 < n; i++) { // start of interval
int j = i + len - 1; // end of interval
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) { // split point
dp[i][j] = [Link](dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,k,j));
}
}
}

5d. DP with Bitmask (State Compression)

// Travelling Salesman / Assign Tasks
// dp[mask][i] = min cost to visit cities in mask, ending at city i
int[][] dp = new int[1 << n][n];
for (int[] row : dp) [Link](row, Integer.MAX_VALUE / 2);
dp[1][0] = 0; // start at city 0
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0) continue;
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0) continue;
int newMask = mask | (1 << v);
dp[newMask][v] = [Link](dp[newMask][v], dp[mask][u] + dist[u][v]);
}
}
}

Page 8
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 4 — GRAPH ALGORITHMS

🌐 Graph Algorithms
1. Dijkstra's Algorithm — Shortest Path (non-negative weights)
// Dijkstra O((V + E) log V)
int[] dist = new int[n];
[Link](dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] - b[0]);
[Link](new int[]{0, src}); // {distance, node}
while (![Link]()) {
int[] cur = [Link]();
int d = cur[0], u = cur[1];
if (d > dist[u]) continue; // stale entry
for (int[] edge : [Link](u)) { // {neighbor, weight}
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
[Link](new int[]{dist[v], v});
}
}
}

2. Bellman-Ford — Shortest Path (negative weights allowed)

// Bellman-Ford O(V*E) — detects negative cycles
int[] dist = new int[n];
[Link](dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i < n - 1; i++) { // relax n-1 times
for (int[] edge : edges) { // {u, v, weight}
int u=edge[0], v=edge[1], w=edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u]+w < dist[v])
dist[v] = dist[u] + w;
}
}
// If dist still reduces on nth iteration => negative cycle

3. Topological Sort (Kahn's BFS Algorithm)

// Detect cycle + topological order in directed graph
int[] inDegree = new int[n];
for (int[] edge : edges) inDegree[edge[1]]++;
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (inDegree[i] == 0) [Link](i);
List<Integer> order = new ArrayList<>();
while (![Link]()) {
int u = [Link]();
[Link](u);
for (int v : [Link](u)) {
if (--inDegree[v] == 0) [Link](v);
}
}

Page 9
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization
// If [Link]() != n => cycle exists

4. Tarjan's SCC — Strongly Connected Components

// Critical Connections / Bridges — O(V+E)
int[] disc = new int[n], low = new int[n];
int[] timer = {0};
void dfs(int u, int parent, List<int[]> bridges) {
disc[u] = low[u] = timer[0]++;
for (int v : [Link](u)) {
if (disc[v] == -1) { // unvisited
dfs(v, u, bridges);
low[u] = [Link](low[u], low[v]);
if (low[v] > disc[u]) [Link](new int[]{u, v}); // bridge!
} else if (v != parent) {
low[u] = [Link](low[u], disc[v]);
}
}
}

Page 10
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 5 — MATHEMATICAL FORMULAS

📐 Mathematical Formulas & Number Theory

1. Modular Arithmetic
⚠️Why Mod?
Many problems ask for answers mod 10^9 + 7 (a prime). This keeps numbers within int/long
range.
MOD = 1_000_000_007 is always prime, which allows modular inverse using Fermat's Little
Theorem.

final long MOD = 1_000_000_007L;

// Basic rules:
// (a + b) % MOD = ((a % MOD) + (b % MOD)) % MOD
// (a * b) % MOD = ((a % MOD) * (b % MOD)) % MOD
// (a - b + MOD) % MOD <-- never negative!

// Modular Exponentiation — a^b % MOD in O(log b)

long modPow(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}

// Modular Inverse (mod must be prime) — a^(MOD-2) % MOD

long modInverse(long a, long mod) { return modPow(a, mod - 2, mod); }

// Division under modulo: (a / b) % MOD = a * modInverse(b) % MOD

2. Combinatorics — nCr, nPr

// Precompute factorials and inverse factorials
int MAXN = 200_001;
long[] fact = new long[MAXN], inv_fact = new long[MAXN];
fact[0] = 1;
for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
inv_fact[MAXN-1] = modPow(fact[MAXN-1], MOD-2, MOD);
for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;

// C(n, r) = n! / (r! * (n-r)!)

long nCr(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

// Stars and Bars: ways to distribute n identical into k distinct bins

Page 11
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization
// = C(n + k - 1, k - 1)

3. GCD, LCM, and Number Theory

// Euclidean GCD — O(log min(a,b))
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

// LCM — watch for overflow! use long

long lcm(long a, long b) { return a / gcd((int)a, (int)b) * b; }

// Sieve of Eratosthenes — all primes up to N in O(N log log N)

boolean[] isPrime = new boolean[N + 1];
[Link](isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
for (int j = i*i; j <= N; j += i) isPrime[j] = false;
}
}

// Prime factorization — O(sqrt(n))

Map<Integer,Integer> primeFactors(int n) {
Map<Integer,Integer> factors = new HashMap<>();
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) { [Link](i, 1, Integer::sum); n /= i; }
}
if (n > 1) [Link](n, 1);
return factors;
}

4. Bit Manipulation
// Essential bit tricks
n & (n-1) // clear lowest set bit | n==0 if power of 2
n & (-n) // isolate lowest set bit (submask trick)
n | (1 << k) // set kth bit
n & ~(1 << k) // clear kth bit
n ^ (1 << k) // toggle kth bit
(n >> k) & 1 // check if kth bit is set
[Link](n) // count set bits (popcount)

// XOR trick: a ^ a = 0, a ^ 0 = a
// Find single number in array where all others appear twice:
int single = 0;
for (int x : nums) single ^= x;

// Enumerate all subsets of a bitmask:

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
// process subset 'sub'
}

5. Important Mathematical Identities

Formula / Identity Java Code / Application

Sum 1..n = n*(n+1)/2 long sum = (long)n*(n+1)/2;

Page 12
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

Sum of squares = n(n+1)(2n+1)/6 long sq = (long)n*(n+1)*(2*n+1)/6;

log₂(n) bits needed int bits = 32 - [Link](n);
Catalan(n) = C(2n,n)/(n+1) Used in: balanced parens, BST counts
Fibonacci via matrix exponentiation F(n) in O(log n) using 2x2 matrix
Floor division: a/b = (a - a%b)/b [Link](a, b) for unsigned
Ceiling division: ⌈a/b⌉ (a + b - 1) / b or (a - 1) / b + 1
Power of 2 check (n > 0) && (n & (n-1)) == 0
Next power of 2 ≥ n [Link]((n-1)<<1)
Hamming distance [Link](a ^ b)

Page 13
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 6 — OPTIMIZATION STRATEGIES

⚡ Optimization Tricks & Best Practices

Time Complexity Reduction Playbook

Algorithm / Pattern Time Complexity Space Complexity Notes

Nested loops O(n²) O(n log n) O(n) Sort + two
pointers / sliding
window
Sliding Window Max O(n) O(k) Monotonic deque
instead of heap
Range sum query O(1) after O(n) O(n) Prefix sum array
Repeated subproblem O(n) amortized O(n) Memoization / DP
table
Graph shortest path O((V+E)log V) O(V+E) Dijkstra with min-
heap
Dynamic connectivity O(α(n)) ≈ O(1) O(n) Union-Find with path
compress
Substring search O(n+m) O(m) KMP algorithm
Order statistics O(n) avg O(n) QuickSelect
(nth_element style)
Segment tree O(log n) O(n) Range query + point
update
BIT (Fenwick Tree) O(log n) O(n) Prefix sum + point
update, simpler

Fenwick Tree (Binary Indexed Tree) — Simpler than Segment Tree

Best for: prefix sum queries + point updates. O(log n) both operations.
class BIT {
int[] tree;
int n;
BIT(int n) { this.n = n; tree = new int[n + 1]; }

void update(int i, int delta) { // 1-indexed

for (; i <= n; i += i & (-i)) tree[i] += delta;
}

int query(int i) { // prefix sum [1..i]

int sum = 0;
for (; i > 0; i -= i & (-i)) sum += tree[i];
return sum;
}

int rangeQuery(int l, int r) { return query(r) - query(l - 1); }

}

Page 14
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

KMP String Matching — O(n+m)

// Build failure function
int[] buildLPS(String pattern) {
int m = [Link]();
int[] lps = new int[m];
int len = 0, i = 1;
while (i < m) {
if ([Link](i) == [Link](len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}

// Search pattern in text

void kmpSearch(String text, String pattern) {
int[] lps = buildLPS(pattern);
int i = 0, j = 0;
while (i < [Link]()) {
if ([Link](i) == [Link](j)) { i++; j++; }
if (j == [Link]()) {
[Link]("Found at index " + (i - j));
j = lps[j - 1];
} else if (i < [Link]() && [Link](i) != [Link](j)) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
}

Java-Specific Optimization Tips

🔑 Key Java Performance Tips

1. Use int[] arrays instead of ArrayList<Integer> for speed (avoids boxing)
2. Use StringBuilder for string concatenation in loops — String + is O(n²)
3. Use ArrayDeque instead of Stack (faster, not synchronized)
4. Use HashMap with initial capacity: new HashMap<>(n * 2) to avoid rehashing
5. [Link]() on primitives uses Dual-Pivot Quicksort O(n log n) — very fast
6. [Link]() uses TimSort — stable, O(n log n)
7. Avoid [Link]() in tight loops — use precomputed values
8. int is faster than long — use int when values fit within 2^31
9. Bitwise ops (<<, >>, &, |, ^) are faster than multiply/divide by powers of 2
10. [Link]() is faster than manual loops for array copying

Page 15
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 7 — TREE ALGORITHMS

🌳 Tree Algorithms
DFS Patterns on Binary Trees
// Pattern: return info from subtrees to solve at root
int[] dfs(TreeNode node) { // returns [maxPath, maxEndingHere]
if (node == null) return new int[]{0, 0};
int[] left = dfs([Link]);
int[] right = dfs([Link]);

int throughRoot = left[1] + [Link] + right[1];

int maxEndHere = [Link]([Link], [Link] + [Link](left[1], right[1]));
int maxPath = [Link]([Link](left[0], right[0]), throughRoot);
return new int[]{maxPath, maxEndHere};
}
// Binary Tree Maximum Path Sum pattern

Lowest Common Ancestor (LCA) — O(log n) with Binary Lifting

// Preprocess: ancestor[v][j] = 2^j-th ancestor of v
int LOG = 18; // 2^18 > 200000
int[][] ancestor = new int[n][LOG];
int[] depth = new int[n];

void dfs(int u, int par, int d) {

ancestor[u][0] = par;
depth[u] = d;
for (int j = 1; j < LOG; j++)
ancestor[u][j] = ancestor[ancestor[u][j-1]][j-1];
for (int v : [Link](u)) if (v != par) dfs(v, u, d+1);
}

int lca(int u, int v) {

if (depth[u] < depth[v]) { int t=u; u=v; v=t; }
int diff = depth[u] - depth[v];
for (int j = 0; j < LOG; j++) if ((diff >> j & 1) == 1) u = ancestor[u][j];
if (u == v) return u;
for (int j = LOG-1; j >= 0; j--)
if (ancestor[u][j] != ancestor[v][j]) { u=ancestor[u][j]; v=ancestor[v][j]; }
return ancestor[u][0];
}

Page 16
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 8 — TIPS, TRICKS & MENTAL MODELS

💡 Power Tips for Hard Problems

The 'Think Backwards' Trick
Strategy: Reverse the Problem
If adding elements is hard, think about what happens when you REMOVE them.
Example: 'Remove the last stone' problems are easier solved from the end.
Example: 'Minimum operations to destroy' → 'Maximum survivable state'
Offline queries: sort queries and process them in reverse order of deletion.

The 'Fix One Variable' Trick

Strategy: Enumerate One, Optimize the Other
When a problem has two unknowns (i, j), fix i and binary search or use HashMap for j.
Example: Count pairs (i,j) where nums[i] + nums[j] == target
→ Fix i, look up (target - nums[i]) in HashMap in O(1)
Example: Maximum XOR of two numbers → Fix one, use Trie to find best complement in O(n
log max)

The 'Binary Search on Answer' Trick

// Problem: 'minimize the maximum' or 'maximize the minimum'
// These always hint at binary searching the ANSWER

// Example: Split array into k parts, minimize the maximum subarray sum
boolean canSplit(int[] nums, int k, int maxSum) {
int parts = 1, cur = 0;
for (int x : nums) {
if (x > maxSum) return false;
if (cur + x > maxSum) { parts++; cur = x; }
else cur += x;
}
return parts <= k;
}
// Binary search: lo = max(nums), hi = sum(nums)

The 'Coordinate Compression' Trick

// When values are large but count is small
// Compress values to indices 0..n-1
int[] sorted = [Link]();
[Link](sorted);
// Map each value to its rank
Map<Integer,Integer> compress = new HashMap<>();
int rank = 0;

Page 17
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization
for (int x : sorted) [Link](x, rank++);

// Now use [Link](nums[i]) as the 'value' for BIT or Segment Tree

Common Edge Cases — Never Forget

Situation What to Check

Empty input [Link] == 0, root == null, [Link]()
Single element Returns element itself, no comparisons needed
All same elements No duplicates removed — sliding window still valid?
Negative numbers Prefix sum can be negative — use HashMap for min
index
Integer overflow Use long for sums, products — n² can exceed 2^31
Circular array Use modulo: (i + 1) % n, or duplicate the array
Graph with cycles Use visited[] array or check in-degree for topo sort
k larger than array Clamp k = k % n for rotation problems
Empty string / null char Handle charAt(0) on empty string separately
Max/Min initialization Use Integer.MAX_VALUE/MIN_VALUE, not 99999

Java Syntax Quick Reference

// Sort 2D array by first col, then second col

[Link](intervals, (a,b) -> a[0] != b[0] ? a[0]-b[0] : a[1]-b[1]);

// Sort list of strings by length, then alphabetically

[Link]([Link](String::length).thenComparing([Link]
er()));

// Infinity values
int INF = Integer.MAX_VALUE / 2; // safe for addition

// Char to int and back

int d = c - '0';
char ch = (char)('a' + idx);

// Deep copy 2D array

int[][] copy = [Link](grid).map(int[]::clone).toArray(int[][]::new);

// Fill 2D array
for (int[] row : dp) [Link](row, -1);

// List to array and back

int[] arr = [Link]().mapToInt(Integer::intValue).toArray();
List<Integer> list = new ArrayList<>([Link](arr)); // object array only

// Merge two sorted arrays efficiently

PriorityQueue<int[]> merge = new PriorityQueue<>((a,b)->a[0]-b[0]);

Page 18
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

Page 19
LeetCode Hard — Java Mastery Guide · Concepts · Algorithms · Formulas · Optimization

SECTION 9 — STUDY ROADMAP & SKILL TRACKER

Recommended Study Roadmap

Follow this sequence to build mastery progressively:

Week Focus Area Key Problems Target Pattern

1-2 Arrays & Two Pointers Trapping Rain Water, 3Sum, Two Pointers, Sliding
Container With Most Water Window
3-4 Binary Search Median of Two Sorted Arrays, Binary Search on Answer
Search in Rotated Array
5-6 Dynamic Programming I Coin Change, LCS, Edit Distance, 1D & 2D DP
Longest Inc. Subseq.
7-8 DP II + Bitmask Burst Balloons, TSP, Count Vowels Interval DP, Bitmask DP
Permutation
9-10 Graphs Network Delay, Alien Dictionary, Dijkstra, Topo Sort, Tarjan
Critical Connections
11-12 Trees & Advanced Serialize Tree, LCA, Binary Tree DFS with return, Binary
Max Path Sum Lifting
13-14 Segment Tree / BIT Range Sum Queries, Reverse Pairs, Segment Tree, BIT, Merge
Count Smaller Sort
15-16 Hard Mix + Revision Hard contest problems, timed All patterns combined
practice, mock interviews

Before Every Problem — Checklist

✅ Pre-Coding Checklist
□ Read constraints — what is n? (n≤20 → bitmask DP, n≤1000 → O(n²), n≤10⁶ → O(n log n))
□ Identify what the problem is minimizing or maximizing
□ Check if the answer is monotonic → binary search on answer
□ Draw 2-3 small examples by hand before coding
□ Identify overlapping subproblems → memoization
□ Check if output needs mod 10^9+7 → use long, apply mod everywhere
□ Plan your approach and its complexity BEFORE writing code
□ Account for edge cases: empty input, n=1, all same, negative values

Mastery comes from deliberate practice — one pattern at a time.

LeetCode Hard Java Mastery Guide · All rights to respective algorithm inventors

Page 20