Chapter 24

Advanced Problem Solving in Java

Java Data Structures & Algorithms Series

Chapter 24 is about combining multiple DSA techniques to solve complex problems. Real interviews
rarely test one concept — they test your ability to recognize which tools to combine and when.

1 Technique Combination Map

Binary Search + DP → Optimized LIS, Weighted Job Scheduling

BFS + Hashing → Word Ladder, Shortest Transformation
Heap + Greedy → Task Scheduler, Meeting Rooms
Graph + DP → Shortest Path with constraints
Trie + DFS/Backtrack → Word Search II, Auto-complete
Segment Tree + BIT → Range queries with updates
Two Pointers + Sorting → 3Sum, Container with Most Water
Stack + Monotonic → Largest Rectangle, Trapping Rain Water

2 Trie (Prefix Tree)

A Trie is a tree where each node represents a character. Used for prefix-based search,
autocomplete, and spell checkers.

Insert: "apple", "app", "bat", "ball"

root
/ \
a b
| |
p a
| / \
p t l
/ \ |
* l l
| |
e *
|
*
(* = end of word)

class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
}

class Trie {
TrieNode root = new TrieNode();
 // Insert word into Trie
public 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;
}

// Search exact word

public 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];
}

// Search prefix
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null) return false;
node = [Link][idx];
}
return true; // prefix exists even if not a complete word
}
}

// insert/search/startsWith: O(L) — L = word length

// Space: O(total characters × 26)

3 Monotonic Stack

A stack that maintains elements in strictly increasing or decreasing order. Solves "next
greater/smaller element" problems in O(n).

Next Greater Element

public static int[] nextGreater(int[] nums) {

int n = [Link];
int[] result = new int[n];
[Link](result, -1); // default: no greater element
Stack<Integer> stack = new Stack<>(); // stores indices

for (int i = 0; i < n; i++) {

// Pop elements smaller than current — current is their next greater
while (![Link]() && nums[[Link]()] < nums[i])
 result[[Link]()] = nums[i];
[Link](i);
}
return result;
}
// Input: [2, 1, 2, 4, 3]
// Output: [4, 2, 4,-1,-1]

// Time: O(n) | Space: O(n)

Largest Rectangle in Histogram

public static int largestRectangle(int[] heights) {

Stack<Integer> stack = new Stack<>();
int maxArea = 0, n = [Link];

for (int i = 0; i <= n; i++) {

int currHeight = (i == n) ? 0 : heights[i];

while (![Link]() && heights[[Link]()] > currHeight) {

int height = heights[[Link]()];
int width = [Link]() ? i : i - [Link]() - 1;
maxArea = [Link](maxArea, height * width);
}
[Link](i);
}
return maxArea;
}

// Time: O(n) | Space: O(n)

Trapping Rain Water

// Stack-based approach
public static int trap(int[] height) {
Stack<Integer> stack = new Stack<>();
int water = 0;

for (int i = 0; i < [Link]; i++) {

while (![Link]() && height[[Link]()] < height[i]) {
int bottom = height[[Link]()];
if ([Link]()) break;
int left = [Link]();
int h = [Link](height[left], height[i]) - bottom;
int w = i - left - 1;
water += h * w;
}
[Link](i);
}
return water;
}

// Two-pointer approach — O(1) space

public static int trapTwoPointers(int[] height) {
 int left = 0, right = [Link] - 1;
int leftMax = 0, rightMax = 0, water = 0;

while (left < right) {

if (height[left] <= height[right]) {
if (height[left] >= leftMax) leftMax = height[left];
else water += leftMax - height[left];
left++;
} else {
if (height[right] >= rightMax) rightMax = height[right];
else water += rightMax - height[right];
right--;
}
}
return water;
}

// Time: O(n) | Space: O(1) for two-pointer

4 Segment Tree

Answers range queries (sum, min, max) with point updates in O(log n).

Array: [1, 3, 5, 7, 9, 11]

Segment Tree:
[36] → sum of all
/ \
[9] [27] → sum of left/right halves
/ \ / \
[4] [5] [16] [11]
/ \ / \
[1][3] [7][9]

class SegmentTree {
int[] tree;
int n;

SegmentTree(int[] arr) {
n = [Link];
tree = new int[4 * n];
build(arr, 0, 0, n - 1);
}

private void build(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start]; // leaf node
} else {
int mid = (start + end) / 2;
build(arr, 2*node+1, start, mid);
build(arr, 2*node+2, mid+1, end);
tree[node] = tree[2*node+1] + tree[2*node+2];
}
}

// Range sum query [l, r]

public int query(int node, int start, int end, int l, int r) {
 if (r < start || end < l) return 0; // completely outside
if (l <= start && end <= r) return tree[node]; // completely inside
int mid = (start + end) / 2;
return query(2*node+1, start, mid, l, r)
+ query(2*node+2, mid+1, end, l, r);
}

// Point update — update arr[idx] = val

public void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
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];
}
}
}

// build: O(n) | query: O(log n) | update: O(log n) | Space: O(n)

5 Binary Indexed Tree (Fenwick Tree)

Simpler alternative to Segment Tree for prefix sum queries with updates.

class BIT {
int[] tree;
int n;

BIT(int n) {
this.n = n;
tree = new int[n + 1];
}

// Add val to index i (1-indexed)

public void update(int i, int val) {
for (; i <= n; i += i & (-i)) // move to next responsible node
tree[i] += val;
}

// Prefix sum [1, i]

public int query(int i) {
int sum = 0;
for (; i > 0; i -= i & (-i)) // move to parent
sum += tree[i];
return sum;
}

// Range sum [l, r]

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

// update: O(log n) | query: O(log n) | Space: O(n)

 6 Advanced Combined Problems

🔑 Problem 1 — Word Search II (Trie + DFS Backtracking)

Find all words from a dictionary that exist in a 2D board.

public List<String> findWords(char[][] board, String[] words) {

Trie trie = new Trie();
for (String w : words) [Link](w);

Set<String> result = new HashSet<>();

int m = [Link], n = board[0].length;

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)
dfsWordSearch(board, i, j, [Link], new StringBuilder(), result);

return new ArrayList<>(result);

}

private void dfsWordSearch(char[][] board, int i, int j,

TrieNode node, StringBuilder path,
Set<String> result) {
if (i < 0 || i >= [Link] || j < 0 || j >= board[0].length
|| board[i][j] == '#') return;

char c = board[i][j];
TrieNode next = [Link][c - 'a'];
if (next == null) return; // prefix not in trie, prune

[Link](c);
if ([Link]) [Link]([Link]());

board[i][j] = '#'; // mark visited

int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (int[] d : dirs)
dfsWordSearch(board, i+d[0], j+d[1], next, path, result);

board[i][j] = c; // restore (backtrack)

[Link]([Link]() - 1);
}

// Time: O(m×n×4^L) | Space: O(total word chars)

🔑 Problem 2 — Word Ladder (BFS + Hashing)

Shortest transformation from beginWord to endWord changing one letter at a time.

public static int wordLadder(String begin, String end, List<String> wordList) {

Set<String> wordSet = new HashSet<>(wordList);
if () return 0;

Queue<String> queue = new LinkedList<>();

[Link](begin);
 int steps = 1;

while (![Link]()) {
int size = [Link]();
for (int i = 0; i < size; i++) {
String word = [Link]();
char[] chars = [Link]();

for (int j = 0; j < [Link]; j++) {

char original = chars[j];
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[j] = ch;
String newWord = new String(chars);

if ([Link](end)) return steps + 1;

if ([Link](newWord)) {
[Link](newWord);
[Link](newWord); // mark visited
}
}
chars[j] = original;
}
}
steps++;
}
return 0;
}

// Time: O(M² × N) — M=word length, N=wordList size | Space: O(M × N)

🔑 Problem 3 — Median of Two Sorted Arrays (Binary Search)

Find median of two sorted arrays in O(log(min(m,n))).

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

if ([Link] > [Link])
return findMedianSortedArrays(nums2, nums1);

int m = [Link], n = [Link];

int lo = 0, hi = m;

while (lo <= hi) {

int cut1 = (lo + hi) / 2;
int cut2 = (m + n + 1) / 2 - cut1;

int maxL1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1 - 1];

int minR1 = (cut1 == m) ? Integer.MAX_VALUE : nums1[cut1];
int maxL2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[cut2 - 1];
int minR2 = (cut2 == n) ? Integer.MAX_VALUE : nums2[cut2];

if (maxL1 <= minR2 && maxL2 <= minR1) {

if ((m + n) % 2 == 1)
return [Link](maxL1, maxL2);
return ([Link](maxL1, maxL2) + [Link](minR1, minR2)) / 2.0;
} else if (maxL1 > minR2) hi = cut1 - 1;
else lo = cut1 + 1;
}
return 0.0;
}

// Time: O(log(min(m,n))) | Space: O(1)

🔑 Problem 4 — Cheapest Flights Within K Stops (Bellman-Ford + DP)

public static int findCheapestPrice(int n, int[][] flights,

int src, int dst, int k) {
int[] prices = new int[n];
[Link](prices, Integer.MAX_VALUE);
prices[src] = 0;

// Relax edges k+1 times (Bellman-Ford variant)

for (int i = 0; i <= k; i++) {
int[] temp = [Link](); // use previous iteration's values
for (int[] flight : flights) {
int from = flight[0], to = flight[1], cost = flight[2];
if (prices[from] != Integer.MAX_VALUE
&& prices[from] + cost < temp[to])
temp[to] = prices[from] + cost;
}
prices = temp;
}
return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
}

// Time: O(k × E) | Space: O(n)

🔑 Problem 5 — Maximal Square (2D DP)

Find largest square of 1s in a binary matrix.

public static int maximalSquare(char[][] matrix) {

int m = [Link], n = matrix[0].length;
int[][] dp = new int[m+1][n+1];
// dp[i][j] = side length of largest square ending at (i-1, j-1)
int maxSide = 0;

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = 1 + [Link](dp[i-1][j],
[Link](dp[i][j-1], dp[i-1][j-1]));
maxSide = [Link](maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}

// Time: O(m×n) | Space: O(m×n)

🔑 Problem 6 — Sliding Window Maximum (Deque + Monotonic)

public static int[] maxSlidingWindow(int[] nums, int k) {

int n = [Link];
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // stores indices

for (int i = 0; i < n; i++) {

// Remove elements outside window
while (![Link]() && [Link]() < i - k + 1)
[Link]();

// Remove elements smaller than current (they can never be max)

while (![Link]() && nums[[Link]()] < nums[i])
[Link]();

[Link](i);

if (i >= k - 1)
result[i - k + 1] = nums[[Link]()];
}
return result;
}

// Time: O(n) | Space: O(k)

7 Strategy Guide for Hard Problems

Use this decision tree in interviews:

Is the problem asking for...

SHORTEST PATH?
→ Unweighted → BFS
→ Weighted, no negatives → Dijkstra
→ Negative weights → Bellman-Ford
→ All pairs → Floyd-Warshall

OPTIMAL VALUE (max/min)?

→ Overlapping subproblems → DP
→ Greedy works locally → Greedy + Heap

COUNTING/EXISTENCE in RANGE?
→ Static array → Prefix Sum
→ Dynamic updates → Segment Tree / BIT

PREFIX MATCHING?
→ Trie

NEXT GREATER/SMALLER?
→ Monotonic Stack

CONNECTED COMPONENTS?
→ Union-Find (DSU)
8 Full Runnable Java Program

import [Link].*;

public class Chapter24AdvancedProblemSolving {

public static void main(String[] args) {

// Next Greater Element
int[] arr = {2, 1, 2, 4, 3};
[Link]("Next Greater: " + [Link](nextGreater(arr)));

// Largest Rectangle in Histogram

int[] hist = {2, 1, 5, 6, 2, 3};
[Link]("Largest Rectangle: " + largestRectangle(hist)); // 10

// Trapping Rain Water

int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1};
[Link]("Trapped Water: " + trapTwoPointers(heights)); // 6

// Trie
Trie trie = new Trie();
[Link]("apple"); [Link]("app");
[Link]("Search 'apple': " + [Link]("apple")); // true
[Link]("Search 'app': " + [Link]("app")); // true
[Link]("Prefix 'ap': " + [Link]("ap")); // true
[Link]("Search 'ap': " + [Link]("ap")); // false

// Segment Tree
int[] nums = {1, 3, 5, 7, 9, 11};
SegmentTree st = new SegmentTree(nums);
[Link]("Range Sum [1,3]: " +
[Link](0, 0, [Link]-1, 1, 3)); // 15
[Link](0, 0, [Link]-1, 1, 10);
[Link]("After update [1,3]: " +
[Link](0, 0, [Link]-1, 1, 3)); // 22

// Sliding Window Maximum

int[] w = {1,3,-1,-3,5,3,6,7};
[Link]("Sliding Max k=3: " +
[Link](maxSlidingWindow(w, 3)));

// Word Ladder
List<String> wordList = [Link]("hot","dot","dog","lot","log","cog");
[Link]("Word Ladder hit→cog: " +
wordLadder("hit", "cog", wordList)); // 5

// Cheapest Flights
int[][] flights = {{0,1,100},{1,2,100},{0,2,500}};
[Link]("Cheapest flight 0→2, k=1: " +
findCheapestPrice(3, flights, 0, 2, 1)); // 200

// Median of Two Sorted Arrays

[Link]("Median [1,3],[2]: " +
findMedianSortedArrays(new int[]{1,3}, new int[]{2})); // 2.0

// Maximal Square
char[][] matrix = {{'1','0','1','0'},{'1','0','1','1'},
{'1','1','1','1'},{'1','0','0','1'}};
[Link]("Maximal Square: " + maximalSquare(matrix)); // 4
}
 static int[] nextGreater(int[] nums) {
int n = [Link]; int[] res = new int[n]; [Link](res, -1);
Stack<Integer> stk = new Stack<>();
for (int i = 0; i < n; i++) {
while (![Link]() && nums[[Link]()] < nums[i])
res[[Link]()] = nums[i];
[Link](i);
}
return res;
}

static int largestRectangle(int[] h) {

Stack<Integer> stk = new Stack<>(); int max = 0, n = [Link];
for (int i = 0; i <= n; i++) {
int curr = (i == n) ? 0 : h[i];
while (![Link]() && h[[Link]()] > curr) {
int ht = h[[Link]()];
int w = [Link]() ? i : i - [Link]() - 1;
max = [Link](max, ht * w);
}
[Link](i);
}
return max;
}

static int trapTwoPointers(int[] h) {

int l = 0, r = [Link]-1, lm = 0, rm = 0, w = 0;
while (l < r) {
if (h[l] <= h[r]) { if (h[l] >= lm) lm = h[l]; else w += lm-h[l]; l++; }
else { if (h[r] >= rm) rm = h[r]; else w += rm-h[r];
r--; }
}
return w;
}

static int[] maxSlidingWindow(int[] nums, int k) {

int n = [Link]; int[] res = new int[n-k+1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (![Link]() && [Link]() < i-k+1) [Link]();
while (![Link]() && nums[[Link]()] < nums[i]) [Link]();
[Link](i);
if (i >= k-1) res[i-k+1] = nums[[Link]()];
}
return res;
}

static int wordLadder(String begin, String end, List<String> wl) {

Set<String> set = new HashSet<>(wl); if () return 0;
Queue<String> q = new LinkedList<>(); [Link](begin); int steps = 1;
while (![Link]()) { int sz = [Link]();
for (int i = 0; i < sz; i++) { char[] ch = [Link]().toCharArray();
for (int j = 0; j < [Link]; j++) { char orig = ch[j];
for (char c = 'a'; c <= 'z'; c++) { ch[j] = c; String nw = new
String(ch);
if ([Link](end)) return steps+1;
if ([Link](nw)) { [Link](nw); [Link](nw); } } ch[j]
= orig; } }
steps++; }
return 0;
}
 static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[] p = new int[n]; [Link](p, Integer.MAX_VALUE); p[src] = 0;
for (int i = 0; i <= k; i++) { int[] tmp = [Link]();
for (int[] f : flights) if (p[f[0]] != Integer.MAX_VALUE && p[f[0]]+f[2]
< tmp[f[1]]) tmp[f[1]] = p[f[0]]+f[2];
p = tmp; }
return p[dst] == Integer.MAX_VALUE ? -1 : p[dst];
}

static double findMedianSortedArrays(int[] n1, int[] n2) {

if ([Link] > [Link]) return findMedianSortedArrays(n2, n1);
int m = [Link], n = [Link], lo = 0, hi = m;
while (lo <= hi) { int c1=(lo+hi)/2, c2=(m+n+1)/2-c1;
int ml1=c1==0?Integer.MIN_VALUE:n1[c1-1], mr1=c1==m?
Integer.MAX_VALUE:n1[c1];
int ml2=c2==0?Integer.MIN_VALUE:n2[c2-1], mr2=c2==n?
Integer.MAX_VALUE:n2[c2];
if (ml1<=mr2 && ml2<=mr1) return (m+n)%2==1?[Link](ml1,ml2):
([Link](ml1,ml2)+[Link](mr1,mr2))/2.0;
else if (ml1>mr2) hi=c1-1; else lo=c1+1; }
return 0;
}

static int maximalSquare(char[][] matrix) {

int m=[Link], n=matrix[0].length, max=0;
int[][] dp=new int[m+1][n+1];
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++)
if (matrix[i-1][j-1]=='1') { dp[i][j]=1+[Link](dp[i-1]
[j],[Link](dp[i][j-1],dp[i-1][j-1])); max=[Link](max,dp[i][j]); }
return max*max;
}
}

class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd = false; }

class Trie {
TrieNode root = new TrieNode();
public void insert(String word) { TrieNode n = root; for (char c :
[Link]()) { int i=c-'a'; if ([Link][i]==null) [Link][i]=new
TrieNode(); n=[Link][i]; } [Link]=true; }
public boolean search(String word) { TrieNode n=root; for (char
c:[Link]()){int i=c-'a';if([Link][i]==null)return
false;n=[Link][i];}return [Link]; }
public boolean startsWith(String p) { TrieNode n=root; for(char
c:[Link]()){int i=c-'a';if([Link][i]==null)return
false;n=[Link][i];}return true; }
}

class SegmentTree {
int[] tree; int n;
SegmentTree(int[] arr) { n=[Link]; tree=new int[4*n]; build(arr,0,0,n-1); }
private void build(int[] arr,int node,int s,int e) { if(s==e)
{tree[node]=arr[s];}else{int
m=(s+e)/2;build(arr,2*node+1,s,m);build(arr,2*node+2,m+1,e);tree[node]=tree[2*node+1
]+tree[2*node+2];} }
public int query(int node,int s,int e,int l,int r) { if(r<s||e<l)return
0;if(l<=s&&e<=r)return tree[node];int m=(s+e)/2;return query(2*node+1,s,m,l,r)
+query(2*node+2,m+1,e,l,r); }
public void update(int node,int s,int e,int idx,int val) { if(s==e)
{tree[node]=val;}else{int m=(s+e)/2;if(idx<=m)update(2*node+1,s,m,idx,val);else
update(2*node+2,m+1,e,idx,val);tree[node]=tree[2*node+1]+tree[2*node+2];} }
}
 9 Practice Problems for Chapter 24

Solve in this order:

Difficulty Problem
Medium Implement Trie (LeetCode #208)
Medium Largest rectangle in histogram (LeetCode #84)
Medium Trapping rain water (LeetCode #42)
Medium Sliding window maximum (LeetCode #239)
Medium Word ladder (LeetCode #127)
Medium Cheapest flights within K stops (LeetCode #787)
Hard Word search II — Trie + DFS (LeetCode #212)
Hard Median of two sorted arrays (LeetCode #4)
Hard Maximal rectangle (LeetCode #85)
Hard Serialize and deserialize binary tree (LeetCode
#297)

💡 Key Insight: The best problem solvers don't memorize solutions — they recognize patterns
and reduce unknown problems to known ones.

• When you see 'prefix' → think Trie

• When you see 'next greater' → think Monotonic Stack
• When you see 'range query + update' → think Segment Tree / BIT

Next is Chapter 25 — Revision + Hard Problems, where you consolidate everything and simulate
real interview conditions! 🚀