DSA 50+ Java Questions and Answers

Includes concise Java implementations, short explanations, and time/space complexity.

1. Two Sum
Find indices of two numbers that add up to a target.

Java Solution:
// HashMap approach - O(n)
import java.util.*;
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{}; // not found
}

Explanation: Use a HashMap to store value→index. For each number check if complement exists
— O(n) time, O(n) space.

Complexity: Time: O(n), Space: O(n)

2. Maximum Subarray (Kadane)

Find maximum sum of a contiguous subarray.

Java Solution:
public int maxSubArray(int[] nums) {
int maxSoFar = nums[0], curr = nums[0];
for (int i = 1; i < nums.length; i++) {
curr = Math.max(nums[i], curr + nums[i]);
maxSoFar = Math.max(maxSoFar, curr);
}
return maxSoFar;
}

Explanation: Keep current running sum; reset when it becomes worse than starting at current
element.

Complexity: Time: O(n), Space: O(1)

3. Move Zeroes
Move all zeros to the end while maintaining relative order.

Java Solution:
public void moveZeroes(int[] nums) {
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) nums[j++] = nums[i];
}
while (j < nums.length) nums[j++] = 0;
}

Explanation: Two-pointer: compact non-zeros then fill rest with zeros.

Complexity: Time: O(n), Space: O(1)

4. Best Time to Buy and Sell Stock

Max profit from single buy & sell.

Java Solution:
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, maxProfit = 0;
for (int p : prices) {
minPrice = Math.min(minPrice, p);
maxProfit = Math.max(maxProfit, p - minPrice);
}
return maxProfit;
}

Explanation: Track minimum price seen so far and compute profit at each step.

Complexity: Time: O(n), Space: O(1)

5. Find Duplicate Number (Floyd's cycle)

Find duplicate in array of n+1 integers where values 1..n.

Java Solution:
public int findDuplicate(int[] nums) {
int tortoise = nums[0], hare = nums[0];
do {
tortoise = nums[tortoise];
hare = nums[nums[hare]];
} while (tortoise != hare);
hare = nums[0];
while (tortoise != hare) {
tortoise = nums[tortoise];
hare = nums[hare];
}
return hare;
}

Explanation: Treat array as linked list with cycle. Use Floyd's cycle detection.

Complexity: Time: O(n), Space: O(1)

6. Merge Intervals
Merge overlapping intervals.
Java Solution:
import java.util.*;
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
List<int[]> res = new ArrayList<>();
int[] cur = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= cur[1]) {
cur[1] = Math.max(cur[1], intervals[i][1]);
} else {
res.add(cur);
cur = intervals[i];
}
}
res.add(cur);
return res.toArray(new int[res.size()][]);
}

Explanation: Sort by start, then merge overlapping by comparing current end with next start.

Complexity: Time: O(n log n), Space: O(n)

7. Rotate Array
Rotate array to the right by k steps.

Java Solution:
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length-1);
reverse(nums, 0, k-1);
reverse(nums, k, nums.length-1);
}
private void reverse(int[] a, int i, int j) {
while (i < j) {
int t = a[i]; a[i++] = a[j]; a[j--] = t;
}
}

Explanation: Reverse whole array, then reverse first k and remaining elements.

Complexity: Time: O(n), Space: O(1)

8. Reverse Words in a String

Reverse the order of words in a string.

Java Solution:
public String reverseWords(String s) {
String[] parts = s.trim().split("\s+");
Collections.reverse(Arrays.asList(parts));
return String.join(" ", parts);
}

Explanation: Split on whitespace, reverse array of words, join with single space.
Complexity: Time: O(n), Space: O(n)

9. Valid Palindrome
Check if string is palindrome ignoring non-alphanumerics and case.

Java Solution:
public boolean isPalindrome(String s) {
int i = 0, j = s.length()-1;
while (i < j) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
if (Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j--)))
return false;
}
return true;
}

Explanation: Two-pointer skipping non-alphanumerics and comparing lowercase characters.

Complexity: Time: O(n), Space: O(1)

10. Longest Substring Without Repeating Characters

Find length of longest substring with unique characters.

Java Solution:
public int lengthOfLongestSubstring(String s) {
int[] last = new int[256];
Arrays.fill(last, -1);
int start = 0, maxLen = 0;
for (int i = 0; i < s.length(); i++) {
start = Math.max(start, last[s.charAt(i)] + 1);
maxLen = Math.max(maxLen, i - start + 1);
last[s.charAt(i)] = i;
}
return maxLen;
}

Explanation: Use sliding window and store last seen index for characters.

Complexity: Time: O(n), Space: O(1) (256)

11. Reverse a Linked List

Reverse singly linked list iteratively.

Java Solution:
class ListNode { int val; ListNode next; ListNode(int v){val=v;} }
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}

Explanation: Iteratively change next pointers keeping previous node.

Complexity: Time: O(n), Space: O(1)

12. Detect Cycle in Linked List (Floyd)

Detect if cycle exists.

Java Solution:
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}

Explanation: Use slow and fast pointers; if they meet, there's a cycle.

Complexity: Time: O(n), Space: O(1)

13. Merge Two Sorted Linked Lists

Merge two sorted lists into one.

Java Solution:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}

Explanation: Classic merge similar to merging two sorted arrays.

Complexity: Time: O(n+m), Space: O(1)

14. Find Middle of Linked List

Return middle node (second middle for even length).

Java Solution:
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

Explanation: Fast moves twice as fast; when fast reaches end, slow is middle.

Complexity: Time: O(n), Space: O(1)

15. Remove Nth Node From End

Remove nth node from end in one pass.

Java Solution:
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0); dummy.next = head;
ListNode first = dummy, second = dummy;
for (int i = 0; i <= n; i++) first = first.next;
while (first != null) { first = first.next; second = second.next; }
second.next = second.next.next;
return dummy.next;
}

Explanation: Use two pointers with gap n to find predecessor of target node.

Complexity: Time: O(n), Space: O(1)

16. Valid Parentheses

Check if brackets are balanced.

Java Solution:
public boolean isValid(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c=='('||c=='{'||c=='[') st.push(c);
else {
if (st.isEmpty()) return false;
char t = st.pop();
if ((c==')'&&t!='(')||(c=='}'&&t!='{')||(c==']'&&t!='[')) return false;
}
}
return st.isEmpty();
}

Explanation: Use stack to match opening and closing brackets.

Complexity: Time: O(n), Space: O(n)

17. Min Stack

Design stack supporting getMin in O(1).

Java Solution:
class MinStack {
private Deque<Integer> stack = new ArrayDeque<>();
private Deque<Integer> mins = new ArrayDeque<>();
public void push(int x) {
stack.push(x);
if (mins.isEmpty() || x <= mins.peek()) mins.push(x);
}
public void pop() {
int x = stack.pop();
if (x == mins.peek()) mins.pop();
}
public int top() { return stack.peek(); }
public int getMin() { return mins.peek(); }
}

Explanation: Keep auxiliary stack of current mins; push/pop accordingly.

Complexity: Time: O(1), Space: O(n)

18. Next Greater Element (Array)

Find next greater element for each element.

Java Solution:
public int[] nextGreaterElements(int[] nums) {
int n = nums.length; int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < 2*n; i++) {
int num = nums[i % n];
while (!st.isEmpty() && nums[st.peek()] < num) res[st.pop()] = num;
if (i < n) st.push(i);
}
return res;
}

Explanation: Use monotonic stack; iterate twice for circular behavior.

Complexity: Time: O(n), Space: O(n)

19. Inorder Traversal (Iterative)

Iterative inorder traversal of binary tree.

Java Solution:
class TreeNode { int val; TreeNode left, right; TreeNode(int v){val=v;} }
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> st = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !st.isEmpty()) {
while (cur != null) { st.push(cur); cur = cur.left; }
cur = st.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
Explanation: Use stack to simulate recursion: go left deep, process, then go right.

Complexity: Time: O(n), Space: O(h)

20. Level Order Traversal (BFS)

Return level order (by level) of a binary tree.

Java Solution:
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>(); q.add(root);
while (!q.isEmpty()) {
int sz = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < sz; i++) {
TreeNode n = q.poll();
level.add(n.val);
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
res.add(level);
}
return res;
}

Explanation: Standard BFS using queue, iterate by current level size.

Complexity: Time: O(n), Space: O(n)

21. Height of Binary Tree

Return height (max depth) of tree.

Java Solution:
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Explanation: Recursive depth computation: 1 + max of children depths.

Complexity: Time: O(n), Space: O(h)

22. Check if Tree is Balanced

Balanced: heights of subtrees differ by at most 1.

Java Solution:
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode node) {
if (node == null) return 0;
int lh = height(node.left);
if (lh == -1) return -1;
int rh = height(node.right);
if (rh == -1) return -1;
if (Math.abs(lh - rh) > 1) return -1;
return 1 + Math.max(lh, rh);
}

Explanation: Return -1 on imbalance to short-circuit checks.

Complexity: Time: O(n), Space: O(h)

23. Lowest Common Ancestor (BST)

Find LCA in a BST given two nodes p and q.

Java Solution:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) root = root.left;
else if (p.val > root.val && q.val > root.val) root = root.right;
else return root;
}
return null;
}

Explanation: Use BST property to move left or right until split point.

Complexity: Time: O(h), Space: O(1)

24. Validate BST

Check if binary tree is a valid BST.

Java Solution:
public boolean isValidBST(TreeNode root) {
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean helper(TreeNode node, long low, long high) {
if (node == null) return true;
if (node.val <= low || node.val >= high) return false;
return helper(node.left, low, node.val) && helper(node.right, node.val, high);
}

Explanation: Pass down value bounds for each subtree.

Complexity: Time: O(n), Space: O(h)

25. Diameter of Binary Tree

Longest path between any two nodes (edges count).

Java Solution:
public int diameterOfBinaryTree(TreeNode root) {
int[] res = new int[1];
depth(root, res);
return res[0];
}
private int depth(TreeNode node, int[] res) {
if (node == null) return 0;
int L = depth(node.left, res);
int R = depth(node.right, res);
res[0] = Math.max(res[0], L + R);
return 1 + Math.max(L, R);
}

Explanation: At each node, diameter may pass through it = left depth + right depth.

Complexity: Time: O(n), Space: O(h)

26. Generate Power Set (Subsets)

Generate all subsets of an array.

Java Solution:
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, new ArrayList<>(), res);
return res;
}
private void backtrack(int idx, int[] nums, List<Integer> cur, List<List<Integer>>
res) {
if (idx == nums.length) { res.add(new ArrayList<>(cur)); return; }
// exclude
backtrack(idx+1, nums, cur, res);
// include
cur.add(nums[idx]);
backtrack(idx+1, nums, cur, res);
cur.remove(cur.size()-1);
}

Explanation: Backtracking: at each index choose include/exclude.

Complexity: Time: O(n * 2^n), Space: O(n)

27. Permutations
Generate all permutations of array.

Java Solution:
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
back(nums, 0, res);
return res;
}
private void back(int[] a, int i, List<List<Integer>> res) {
if (i == a.length) {
List<Integer> cur = new ArrayList<>();
for (int v : a) cur.add(v);
res.add(cur);
return;
}
for (int j = i; j < a.length; j++) {
swap(a, i, j);
back(a, i+1, res);
swap(a, i, j);
}
}
private void swap(int[] a, int i, int j){ int t=a[i]; a[i]=a[j]; a[j]=t; }

Explanation: Backtrack by swapping current index with each candidate.

Complexity: Time: O(n * n!), Space: O(n)

28. N-Queens
Place n queens so none attack each other.

Java Solution:
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
int[] cols = new int[n];
place(res, cols, 0, n);
return res;
}
private void place(List<List<String>> res, int[] cols, int row, int n) {
if (row == n) { res.add(build(cols)); return; }
for (int c = 0; c < n; c++) {
if (valid(cols, row, c)) {
cols[row] = c;
place(res, cols, row+1, n);
}
}
}
private boolean valid(int[] cols, int row, int col) {
for (int r = 0; r < row; r++) {
if (cols[r] == col || Math.abs(cols[r]-col) == row-r) return false;
}
return true;
}
private List<String> build(int[] cols) {
List<String> board = new ArrayList<>();
for (int r = 0; r < cols.length; r++) {
char[] row = new char[cols.length];
Arrays.fill(row, '.');
row[cols[r]] = 'Q';
board.add(new String(row));
}
return board;
}

Explanation: Backtracking with column and diagonal checks.

Complexity: Time: exponential, roughly O(n!)

29. Sudoku Solver

Solve 9x9 Sudoku using backtracking.

Java Solution:
public boolean solveSudoku(char[][] board) {
return solve(board);
}
private boolean solve(char[][] b) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (b[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(b, i, j, c)) {
b[i][j] = c;
if (solve(b)) return true;
b[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] b, int r, int c, char ch) {
for (int i = 0; i < 9; i++) {
if (b[r][i] == ch || b[i][c] == ch) return false;
if (b[(r/3)*3 + i/3][(c/3)*3 + i%3] == ch) return false;
}
return true;
}

Explanation: Backtracking trying digits 1-9 and checking row/col/box validity.

Complexity: Time: exponential, practical with pruning

30. Binary Search (Iterative)

Classic binary search in sorted array.

Java Solution:
public int binarySearch(int[] a, int target) {
int l = 0, r = a.length-1;
while (l <= r) {
int m = l + (r-l)/2;
if (a[m] == target) return m;
else if (a[m] < target) l = m+1;
else r = m-1;
}
return -1;
}

Explanation: Standard divide-and-conquer on indices.

Complexity: Time: O(log n), Space: O(1)

31. Merge Sort

Sort array using merge sort.

Java Solution:
public void mergeSort(int[] a) {
if (a.length < 2) return;
int mid = a.length/2;
int[] l = Arrays.copyOfRange(a,0,mid);
int[] r = Arrays.copyOfRange(a,mid,a.length);
mergeSort(l); mergeSort(r);
merge(a, l, r);
}
private void merge(int[] a, int[] l, int[] r) {
int i=0,j=0,k=0;
while (i<l.length && j<r.length) a[k++] = (l[i]<=r[j])?l[i++]:r[j++];
while (i<l.length) a[k++] = l[i++];
while (j<r.length) a[k++] = r[j++];
}

Explanation: Divide array, sort halves, merge sorted halves.

Complexity: Time: O(n log n), Space: O(n)

32. Quick Sort

Quick sort with partition.

Java Solution:
public void quickSort(int[] a) { quickSort(a,0,a.length-1); }
private void quickSort(int[] a, int l, int r) {
if (l >= r) return;
int p = partition(a, l, r);
quickSort(a, l, p-1);
quickSort(a, p+1, r);
}
private int partition(int[] a, int l, int r) {
int pivot = a[r], i = l;
for (int j = l; j < r; j++) {
if (a[j] < pivot) { int t=a[i]; a[i++]=a[j]; a[j]=t; }
}
int t=a[i]; a[i]=a[r]; a[r]=t;
return i;
}

Explanation: Partition around pivot then recursively sort partitions. Average O(n log n).

Complexity: Time: Avg O(n log n), Worst O(n^2), Space: O(log n)

33. Find Kth Largest Element (Heap)

Find kth largest using min-heap.

Java Solution:
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) {
pq.offer(n);
if (pq.size() > k) pq.poll();
}
return pq.peek();
}
Explanation: Maintain min-heap of size k; top is kth largest.

Complexity: Time: O(n log k), Space: O(k)

34. Search in Rotated Sorted Array

Search target in rotated sorted array.

Java Solution:
public int search(int[] a, int target) {
int l=0, r=a.length-1;
while (l<=r) {
int m=(l+r)/2;
if (a[m]==target) return m;
if (a[l] <= a[m]) {
if (target>=a[l] && target<a[m]) r=m-1;
else l=m+1;
} else {
if (target>a[m] && target<=a[r]) l=m+1;
else r=m-1;
}
}
return -1;
}

Explanation: Modified binary search checking which half is sorted.

Complexity: Time: O(log n), Space: O(1)

35. Longest Increasing Subsequence (LIS) - Patience

Length of LIS in O(n log n).

Java Solution:
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int i = Arrays.binarySearch(tails, 0, size, x);
if (i < 0) i = - (i+1);
tails[i] = x;
if (i == size) size++;
}
return size;
}

Explanation: Maintain tails of increasing subsequences; replace using binary search.

Complexity: Time: O(n log n), Space: O(n)

36. Longest Common Subsequence (LCS)

Length of LCS between two strings.

Java Solution:
public int lcs(String A, String B) {
int n=A.length(), m=B.length();
int[][] dp = new int[n+1][m+1];
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if (A.charAt(i-1)==B.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
return dp[n][m];
}

Explanation: DP on prefixes; dp[i][j] is LCS length for A[:i], B[:j].

Complexity: Time: O(n*m), Space: O(n*m)

37. Edit Distance (Levenshtein)

Minimum operations to convert A to B.

Java Solution:
public int minDistance(String A, String B) {
int n=A.length(), m=B.length();
int[][] dp = new int[n+1][m+1];
for (int i=0;i<=n;i++) dp[i][0]=i;
for (int j=0;j<=m;j++) dp[0][j]=j;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {
if (A.charAt(i-1)==B.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=1+Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
}
return dp[n][m];
}

Explanation: DP with insert/delete/replace operations.

Complexity: Time: O(n*m), Space: O(n*m)

38. Coin Change (Min coins)

Minimum coins to make amount.

Java Solution:
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount+1);
dp[0]=0;
for (int c : coins) for (int i=c; i<=amount; i++)
dp[i] = Math.min(dp[i], dp[i-c]+1);
return dp[amount] > amount ? -1 : dp[amount];
}

Explanation: Unbounded knapsack DP filling amounts using coin choices.

Complexity: Time: O(amount * coins), Space: O(amount)

39. Number of Islands

Count connected components of '1's in grid.

Java Solution:
public int numIslands(char[][] grid) {
int m=grid.length, n=grid[0].length; int count=0;
for (int i=0;i<m;i++) for (int j=0;j<n;j++) {
if (grid[i][j]=='1') { dfs(grid,i,j); count++; }
}
return count;
}
private void dfs(char[][] g, int i, int j) {
if (i<0 || j<0 || i>=g.length || j>=g[0].length || g[i][j]=='0') return;
g[i][j]='0';
dfs(g,i+1,j); dfs(g,i-1,j); dfs(g,i,j+1); dfs(g,i,j-1);
}

Explanation: DFS to mark visited land cells; increment count for new islands.

Complexity: Time: O(m*n), Space: O(m*n) recursion

40. Clone Graph

Clone an undirected graph given node reference.

Java Solution:
class Node { public int val; public List<Node> neighbors; Node(int v){val=v;
neighbors=new ArrayList<>();} }
public Node cloneGraph(Node node) {
if (node==null) return null;
Map<Node, Node> map = new HashMap<>();
Queue<Node> q = new LinkedList<>(); q.add(node);
map.put(node, new Node(node.val));
while (!q.isEmpty()) {
Node cur = q.poll();
for (Node nei : cur.neighbors) {
if (!map.containsKey(nei)) { map.put(nei, new Node(nei.val)); q.add(nei); }
map.get(cur).neighbors.add(map.get(nei));
}
}
return map.get(node);
}

Explanation: BFS cloning with mapping original→copy to avoid duplicates.

Complexity: Time: O(V+E), Space: O(V)

41. Topological Sort (Kahn)

Return topological order of DAG using Kahn's algorithm.

Java Solution:
public int[] topoSort(int n, int[][] edges) {
List<Integer>[] g = new List[n]; for (int i=0;i<n;i++) g[i]=new ArrayList<>();
int[] indeg = new int[n];
for (int[] e: edges) { g[e[0]].add(e[1]); indeg[e[1]]++; }
Queue<Integer> q = new LinkedList<>();
for (int i=0;i<n;i++) if (indeg[i]==0) q.add(i);
int[] res = new int[n]; int idx=0;
while (!q.isEmpty()) {
int u = q.poll(); res[idx++] = u;
for (int v: g[u]) if (--indeg[v]==0) q.add(v);
}
if (idx != n) return new int[]{}; // cycle
return res;
}

Explanation: Kahn's algorithm using indegree and queue.

Complexity: Time: O(V+E), Space: O(V+E)

42. Dijkstra's Algorithm

Shortest paths from source in weighted graph (non-negative).

Java Solution:
public int[] dijkstra(List<int[]>[] graph, int src) {
int n = graph.length;
int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE);
dist[src]=0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a->a[1]));
pq.add(new int[]{src,0});
while (!pq.isEmpty()) {
int[] cur = pq.poll(); int u=cur[0], d=cur[1];
if (d>dist[u]) continue;
for (int[] e: graph[u]) {
int v=e[0], w=e[1];
if (dist[v] > dist[u]+w) {
dist[v] = dist[u]+w;
pq.add(new int[]{v, dist[v]});
}
}
}
return dist;
}

Explanation: Use priority queue; relax edges when shorter paths found.

Complexity: Time: O((V+E) log V), Space: O(V)

43. Detect Cycle in Directed Graph (DFS)

Detect cycle using recursion stack.

Java Solution:
public boolean hasCycle(int n, List<Integer>[] g) {
int[] vis = new int[n]; // 0 unvisited, 1 visiting, 2 visited
for (int i=0;i<n;i++) if (vis[i]==0 && dfs(i,g,vis)) return true;
return false;
}
private boolean dfs(int u, List<Integer>[] g, int[] vis) {
vis[u]=1;
for (int v: g[u]) {
if (vis[v]==1) return true;
if (vis[v]==0 && dfs(v,g,vis)) return true;
}
vis[u]=2; return false;
}
Explanation: Use three-state visitation to detect back-edges indicating cycles.

Complexity: Time: O(V+E), Space: O(V)

44. Word Search (Matrix backtracking)

Check if word exists in board via sequential adjacent letters.

Java Solution:
public boolean exist(char[][] board, String word) {
int m=board.length, n=board[0].length;
for (int i=0;i<m;i++) for (int j=0;j<n;j++)
if (dfs(board, i, j, word, 0)) return true;
return false;
}
private boolean dfs(char[][] b, int i, int j, String w, int idx) {
if (idx == w.length()) return true;
if (i<0||j<0||i>=b.length||j>=b[0].length||b[i][j]!=w.charAt(idx)) return false;
char tmp=b[i][j]; b[i][j]='#';
boolean found = dfs(b,i+1,j,w,idx+1) || dfs(b,i-1,j,w,idx+1)
|| dfs(b,i,j+1,w,idx+1) || dfs(b,i,j-1,w,idx+1);
b[i][j]=tmp;
return found;
}

Explanation: Backtracking marking visited cells to avoid reuse.

Complexity: Time: O(m*n*4^L), Space: O(L) recursion

45. Sliding Window Maximum

Return max in each window of size k.

Java Solution:
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length==0) return new int[0];
Deque<Integer> dq = new ArrayDeque<>();
int[] res = new int[nums.length - k + 1]; int ri=0;
for (int i=0;i<nums.length;i++) {
while (!dq.isEmpty() && dq.peekFirst() < i-k+1) dq.pollFirst();
while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
dq.addLast(i);
if (i >= k-1) res[ri++] = nums[dq.peekFirst()];
}
return res;
}

Explanation: Use deque to maintain indices of useful elements in decreasing order.

Complexity: Time: O(n), Space: O(k)

46. Merge k Sorted Lists

Merge k sorted linked lists into one sorted list.

Java Solution:
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a->a.val));
for (ListNode ln: lists) if (ln!=null) pq.add(ln);
ListNode dummy=new ListNode(0), tail=dummy;
while (!pq.isEmpty()) {
ListNode n = pq.poll();
tail.next = n; tail = tail.next;
if (n.next!=null) pq.add(n.next);
}
return dummy.next;
}

Explanation: Use min-heap of current heads of lists; poll smallest and push next.

Complexity: Time: O(N log k) where N total nodes, Space: O(k)

47. Kth Smallest Element in BST

Return kth smallest element (inorder).

Java Solution:
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> st = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !st.isEmpty()) {
while (cur != null) { st.push(cur); cur = cur.left; }
cur = st.pop();
if (--k == 0) return cur.val;
cur = cur.right;
}
return -1;
}

Explanation: Inorder yields sorted order; iterate until kth element.

Complexity: Time: O(h + k), Space: O(h)

48. Serialize and Deserialize Binary Tree

Convert tree to string and back (preorder with null markers).

Java Solution:
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
build(root, sb);
return sb.toString();
}
private void build(TreeNode node, StringBuilder sb) {
if (node==null) { sb.append("#,"); return; }
sb.append(node.val).append(',');
build(node.left, sb); build(node.right, sb);
}
public TreeNode deserialize(String data) {
Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
return buildTree(q);
}
private TreeNode buildTree(Queue<String> q) {
String s = q.poll();
if (s.equals("#")) return null;
TreeNode node = new TreeNode(Integer.parseInt(s));
node.left = buildTree(q); node.right = buildTree(q);
return node;
}

Explanation: Preorder traversal with sentinel for nulls; rebuild recursively.

Complexity: Time: O(n), Space: O(n)

49. LRU Cache

Design LRU cache supporting get and put in O(1).

Java Solution:
class LRUCache {
private int cap; private Map<Integer,Integer> map; private
LinkedHashMap<Integer,Integer> cache;
public LRUCache(int capacity) {
this.cap = capacity;
cache = new LinkedHashMap<>(capacity, 0.75f, true);
}
public int get(int key) { return cache.getOrDefault(key, -1); }
public void put(int key, int value) {
cache.put(key, value);
if (cache.size() > cap) {
Iterator<Integer> it = cache.keySet().iterator(); it.next(); it.remove();
}
}
}

Explanation: Use LinkedHashMap with access-order to maintain LRU; evict oldest entry when over
capacity.

Complexity: Time: O(1) avg, Space: O(capacity)

50. Median of Two Sorted Arrays (outline)

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

Java Solution:
// Outline: binary search on partition in smaller array.
// Full implementation is longer; key idea: partition arrays so left halves contain
half elements.

Explanation: Binary search on partition index ensuring all left <= all right; compute median from
partition edges.

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

51. Sliding Window - Longest Repeating Character Replacement

Given string, replace up to k chars to get longest repeating char substring.

Java Solution:
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int maxCount = 0, start = 0, res = 0;
for (int end=0; end<s.length(); end++) {
maxCount = Math.max(maxCount, ++count[s.charAt(end)-'A']);
while (end - start + 1 - maxCount > k) {
count[s.charAt(start)-'A']--; start++;
}
res = Math.max(res, end - start + 1);
}
return res;
}

Explanation: Sliding window with tracking of most frequent char in window; shrink when more than
k replacements needed.

Complexity: Time: O(n), Space: O(1)

52. Maximum Product Subarray

Max product of contiguous subarray (handles negatives).

Java Solution:
public int maxProduct(int[] a) {
int imax = a[0], imin = a[0], ans = a[0];
for (int i=1;i<a.length;i++) {
if (a[i] < 0) { int t = imax; imax = imin; imin = t; }
imax = Math.max(a[i], imax * a[i]);
imin = Math.min(a[i], imin * a[i]);
ans = Math.max(ans, imax);
}
return ans;
}

Explanation: Track max and min products ending at current position because negative flips sign.

Complexity: Time: O(n), Space: O(1)