DSA Interview Preparation

250 Questions — Java Solutions with Explanations

Arrays • Searching • Recursion • Strings • Stack • Queue • Linked List • Tree • Graph
PART 1: EASY QUESTIONS
Foundational problems — master these patterns before moving on.

Q1. Two Sum

Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they
add up to target.
Approach: HashMap — store complement lookup in O(n) time, O(n) space.
import [Link];
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = 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);
}
return new int[]{};
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q2. Remove Duplicates from Sorted Array

Problem: Remove duplicates in-place from sorted array, return new length.
Approach: Two-pointer — slow pointer tracks unique position.
class Solution {
public int removeDuplicates(int[] nums) {
if ([Link] == 0) return 0;
int slow = 0;
for (int fast = 1; fast < [Link]; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q3. Best Time to Buy and Sell Stock

Problem: Find maximum profit by buying and selling stock once.
Approach: Track minimum price seen so far, compute max profit at each step.
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, maxProfit = 0;
for (int price : prices) {
if (price < minPrice) minPrice = price;
 else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
}
return maxProfit;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q4. Plus One

Problem: Given a number as digit array, add one to the number.
Approach: Iterate from end, handle carry propagation.
class Solution {
public int[] plusOne(int[] digits) {
for (int i = [Link] - 1; i >= 0; i--) {
if (digits[i] < 9) { digits[i]++; return digits; }
digits[i] = 0;
}
int[] result = new int[[Link] + 1];
result[0] = 1;
return result;
}
}
Time: O(n) | Space: O(1) amortized
───────────────────────────────────────────────────────────────────────────────
─

Q5. Missing Number

Problem: Find the missing number in range [0, n].
Approach: Sum formula — expected sum minus actual sum.
class Solution {
public int missingNumber(int[] nums) {
int n = [Link];
int expected = n * (n + 1) / 2;
int actual = 0;
for (int num : nums) actual += num;
return expected - actual;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q6. Maximum Subarray

Problem: Find the contiguous subarray with the largest sum (Kadane's Algorithm).
Approach: Keep running sum; reset if negative. Track global max.
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0], currentSum = nums[0];
for (int i = 1; i < [Link]; i++) {
currentSum = [Link](nums[i], currentSum + nums[i]);
maxSum = [Link](maxSum, currentSum);
}
return maxSum;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q7. Move Zeroes

Problem: Move all zeroes to end while maintaining relative order of non-zero elements.
Approach: Two-pointer — overwrite non-zeros to front, fill rest with zeros.
class Solution {
public void moveZeroes(int[] nums) {
int pos = 0;
for (int num : nums) if (num != 0) nums[pos++] = num;
while (pos < [Link]) nums[pos++] = 0;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q8. Contains Duplicate

Problem: Return true if any value appears at least twice in array.
Approach: HashSet — add elements; return true if already present.
import [Link];
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
if () return true;
}
return false;
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q9. Intersection of Two Arrays II

Problem: Return the intersection of two arrays including duplicates.
Approach: HashMap to count frequency of nums1, match with nums2.
import [Link].*;
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer,Integer> map = new HashMap<>();
for (int n : nums1) [Link](n, 1, Integer::sum);
List<Integer> res = new ArrayList<>();
for (int n : nums2) {
if ([Link](n,0) > 0) {
[Link](n); [Link](n, -1, Integer::sum);
}
}
return [Link]().mapToInt(i->i).toArray();
}
}
Time: O(m+n) | Space: O(min(m,n))
───────────────────────────────────────────────────────────────────────────────
─

Q10. Rotate Array

Problem: Rotate array to the right by k steps.
Approach: Reverse entire array, then reverse first k, then rest.
class Solution {
public void rotate(int[] nums, int k) {
k %= [Link];
reverse(nums, 0, [Link] - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, [Link] - 1);
}
void reverse(int[] a, int l, int r) {
while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q11. Third Maximum Number

Problem: Return the third distinct maximum; if it doesn't exist, return the maximum.
Approach: Maintain three variables for first, second, third max.
class Solution {
public int thirdMax(int[] nums) {
Long first = null, second = null, third = null;
for (long n : nums) {
if ((first!=null&&n==first)||(second!=null&&n==second)||(third!
=null&&n==third)) continue;
if (first==null||n>first) { third=second; second=first; first=n; }
else if (second==null||n>second) { third=second; second=n; }
else if (third==null||n>third) { third=n; }
}
return (int)(third == null ? first : third);
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q12. Valid Palindrome

Problem: Check if a string is a palindrome considering only alphanumeric chars.
Approach: Two-pointer from both ends, skip non-alphanumeric.
class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = [Link]() - 1;
while (l < r) {
while (l < r && )) l++;
while (l < r && )) r--;
if ([Link]([Link](l)) != [Link]([Link](r)))
return false;
l++; r--;
}
return true;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─
Q13. Merge Sorted Array
Problem: Merge two sorted arrays nums1 and nums2 into nums1 in-place.
Approach: Fill from the back — compare and place the larger element.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m-1, j = n-1, k = m+n-1;
while (i>=0 && j>=0)
nums1[k--] = (nums1[i]>nums2[j]) ? nums1[i--] : nums2[j--];
while (j>=0) nums1[k--] = nums2[j--];
}
}
Time: O(m+n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q14. Maximum Product Subarray

Problem: Find the contiguous subarray with the largest product.
Approach: Track both max and min (negatives flip signs). Update global max.
class Solution {
public int maxProduct(int[] nums) {
int maxP = nums[0], minP = nums[0], result = nums[0];
for (int i = 1; i < [Link]; i++) {
int temp = maxP;
maxP = [Link](nums[i], [Link](maxP*nums[i], minP*nums[i]));
minP = [Link](nums[i], [Link](temp*nums[i], minP*nums[i]));
result = [Link](result, maxP);
}
return result;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q15. Minimum Size Subarray Sum

Problem: Find minimal length subarray with sum >= target.
Approach: Sliding window — expand right, shrink left while sum >= target.
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left=0, sum=0, min=Integer.MAX_VALUE;
for (int right=0; right<[Link]; right++) {
sum += nums[right];
while (sum >= target) {
min = [Link](min, right-left+1);
sum -= nums[left++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q16. Climbing Stairs

Problem: You can climb 1 or 2 steps. How many distinct ways to climb n stairs?
Approach: Dynamic programming (Fibonacci pattern). dp[i] = dp[i-1] + dp[i-2].
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int c = a + b; a = b; b = c;
}
return b;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q17. Fibonacci Number

Problem: Return the nth Fibonacci number.
Approach: Iterative with two variables to avoid O(n) space recursion.
class Solution {
public int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) { int c = a+b; a=b; b=c; }
return b;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q18. Reverse String

Problem: Reverse a character array in-place.
Approach: Two-pointer swap from both ends.
class Solution {
public void reverseString(char[] s) {
int l=0, r=[Link]-1;
while(l<r){char t=s[l];s[l++]=s[r];s[r--]=t;}
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q19. Pow(x, n)
Problem: Implement pow(x, n) — x raised to the power n.
Approach: Fast power (exponentiation by squaring) — halve the exponent each step.
class Solution {
public double myPow(double x, int n) {
long exp = n;
if (exp < 0) { x = 1/x; exp = -exp; }
double result = 1;
while (exp > 0) {
if ((exp & 1) == 1) result *= x;
x *= x; exp >>= 1;
}
return result;
}
 }
Time: O(log n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q20. Maximum Depth of Binary Tree

Problem: Find the maximum depth of a binary tree.
Approach: Recursive DFS — depth = 1 + max(left depth, right depth).
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + [Link](maxDepth([Link]), maxDepth([Link]));
}
}
Time: O(n) | Space: O(h) where h = height
───────────────────────────────────────────────────────────────────────────────
─

Q21. Valid Anagram

Problem: Return true if two strings are anagrams of each other.
Approach: Count character frequencies using array of size 26.
class Solution {
public boolean isAnagram(String s, String t) {
if ([Link]() != [Link]()) return false;
int[] count = new int[26];
for (char c : [Link]()) count[c-'a']++;
for (char c : [Link]()) if (--count[c-'a'] < 0) return false;
return true;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q22. First Unique Character in a String

Problem: Return index of first non-repeating character in string.
Approach: Two-pass — count frequencies, then find first with count==1.
class Solution {
public int firstUniqChar(String s) {
int[] freq = new int[26];
for (char c : [Link]()) freq[c-'a']++;
for (int i = 0; i < [Link](); i++)
if (freq[[Link](i)-'a'] == 1) return i;
return -1;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q23. Longest Common Prefix

Problem: Find the longest common prefix string among an array of strings.
Approach: Vertical scanning — compare character by character across all strings.
class Solution {
 public String longestCommonPrefix(String[] strs) {
if ([Link] == 0) return "";
for (int i = 0; i < strs[0].length(); i++) {
char c = strs[0].charAt(i);
for (int j = 1; j < [Link]; j++)
if (i >= strs[j].length() || strs[j].charAt(i) != c)
return strs[0].substring(0, i);
}
return strs[0];
}
}
Time: O(S) where S = total characters | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q24. Min Stack

Problem: Design stack supporting push, pop, top, and retrieving minimum in O(1).
Approach: Use a second stack to track minimums in parallel.
import [Link];
class MinStack {
Stack<Integer> stack = new Stack<>();
Stack<Integer> minStack = new Stack<>();
public void push(int val) {
[Link](val);
if ([Link]() || val <= [Link]()) [Link](val);
}
public void pop() {
if ([Link]().equals([Link]())) [Link]();
}
public int top() { return [Link](); }
public int getMin() { return [Link](); }
}
Time: O(1) all operations | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q25. Valid Parentheses

Problem: Determine if the input string has valid bracket ordering.
Approach: Stack — push open brackets, pop and match on closing brackets.
import [Link];
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : [Link]()) {
if (c=='(' || c=='{' || c=='[') [Link](c);
else {
if ([Link]()) return false;
char top = [Link]();
if (c==')' && top!='(' || c=='}' && top!='{' || c==']' && top!='[')
return false;
}
}
return [Link]();
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─
Q26. Reverse Linked List
Problem: Reverse a singly linked list.
Approach: Iterative with three pointers: prev, curr, next.
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = [Link];
[Link] = prev;
prev = curr;
curr = next;
}
return prev;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q27. Middle of the Linked List

Problem: Return the middle node of a linked list.
Approach: Fast and slow pointer — slow moves 1 step, fast moves 2 steps.
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link]; fast = [Link];
}
return slow;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q28. Linked List Cycle

Problem: Detect if a linked list has a cycle.
Approach: Floyd's cycle detection — fast pointer catches slow if cycle exists.
class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link]; fast = [Link];
if (slow == fast) return true;
}
return false;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q29. Symmetric Tree

Problem: Check if a binary tree is a mirror image of itself.
Approach: Recursive — check if left subtree is mirror of right subtree.
class Solution {
 public boolean isSymmetric(TreeNode root) {
return isMirror([Link], [Link]);
}
boolean isMirror(TreeNode l, TreeNode r) {
if (l==null && r==null) return true;
if (l==null || r==null) return false;
return [Link]==[Link] && isMirror([Link], [Link]) && isMirror([Link], [Link]);
}
}
Time: O(n) | Space: O(h)
───────────────────────────────────────────────────────────────────────────────
─

Q30. Invert Binary Tree

Problem: Invert (mirror) a binary tree.
Approach: Recursive — swap left and right children at every node.
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode temp = [Link];
[Link] = invertTree([Link]);
[Link] = invertTree(temp);
return root;
}
}
Time: O(n) | Space: O(h)
───────────────────────────────────────────────────────────────────────────────
─

Q31. Number of Islands

Problem: Count number of islands (connected 1s) in a 2D grid.
Approach: DFS — visit and sink each island (mark visited as '0').
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i=0; i<[Link]; i++)
for (int j=0; j<grid[0].length; j++)
if (grid[i][j]=='1') { dfs(grid,i,j); count++; }
return count;
}
void dfs(char[][] g, int i, int j) {
if (i<0||i>=[Link]||j<0||j>=g[0].length||g[i][j]!='1') 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);
}
}
Time: O(m*n) | Space: O(m*n) stack
───────────────────────────────────────────────────────────────────────────────
─

Q32. Binary Search / Search Insert Position

Problem: Find target in sorted array, or return insertion index.
Approach: Classic binary search with left/right pointers.
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = [Link] - 1;
while (left <= right) {
 int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
}
Time: O(log n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q33. First Bad Version

Problem: Find first bad version using isBadVersion API with minimum calls.
Approach: Binary search — find leftmost true in a boolean array.
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) right = mid;
else left = mid + 1;
}
return left;
}
}
Time: O(log n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q34. Find Minimum in Rotated Sorted Array

Problem: Find minimum element in a rotated sorted array.
Approach: Binary search — compare mid with right to find rotation point.
class Solution {
public int findMin(int[] nums) {
int left = 0, right = [Link] - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}
}
Time: O(log n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q35. Design Circular Queue

Problem: Implement a circular queue with enQueue, deQueue, Front, Rear, isEmpty, isFull.
Approach: Array with head/tail pointers and a size counter.
class MyCircularQueue {
int[] data; int head, tail, size, cap;
public MyCircularQueue(int k) { data=new int[k]; cap=k; }
public boolean enQueue(int val) {
if (isFull()) return false;
tail = (head+size)%cap; data[tail]=val; size++; return true;
 }
public boolean deQueue() { if(isEmpty()) return false; head=(head+1)%cap; size--;
return true; }
public int Front() { return isEmpty()?-1:data[head]; }
public int Rear() { return isEmpty()?-1:data[(head+size-1)%cap]; }
public boolean isEmpty() { return size==0; }
public boolean isFull() { return size==cap; }
}
Time: O(1) all ops | Space: O(k)
───────────────────────────────────────────────────────────────────────────────
─
PART 2: MEDIUM QUESTIONS
Core interview problems — most placements focus heavily on this tier.

Q36. Product of Array Except Self

Problem: Return array where each element is the product of all other elements, no division.
Approach: Prefix products then suffix products in two passes.
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = [Link];
int[] result = new int[n];
result[0] = 1;
for (int i = 1; i < n; i++) result[i] = result[i-1] * nums[i-1];
int suffix = 1;
for (int i = n-1; i >= 0; i--) { result[i] *= suffix; suffix *= nums[i]; }
return result;
}
}
Time: O(n) | Space: O(1) extra
───────────────────────────────────────────────────────────────────────────────
─

Q37. Container With Most Water

Problem: Find two lines that together with x-axis contain maximum water.
Approach: Two-pointer — move the pointer at shorter line inward.
class Solution {
public int maxArea(int[] height) {
int l=0, r=[Link]-1, max=0;
while (l < r) {
max = [Link](max, [Link](height[l],height[r]) * (r-l));
if (height[l] < height[r]) l++; else r--;
}
return max;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q38. Search in Rotated Sorted Array

Problem: Search for target in a rotated sorted array in O(log n).
Approach: Modified binary search — determine which half is sorted.
class Solution {
public int search(int[] nums, int target) {
int l=0, r=[Link]-1;
while (l<=r) {
int m = l+(r-l)/2;
if (nums[m]==target) return m;
if (nums[l]<=nums[m]) { // left sorted
if (nums[l]<=target && target<nums[m]) r=m-1; else l=m+1;
} else { // right sorted
if (nums[m]<target && target<=nums[r]) l=m+1; else r=m-1;
}
 }
return -1;
}
}
Time: O(log n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q39. Combination Sum

Problem: Find all combinations that sum to target (reuse allowed).
Approach: Backtracking — try each candidate, reduce target, recurse.
import [Link].*;
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), res);
return res;
}
void backtrack(int[] c, int remain, int start, List<Integer> curr,
List<List<Integer>> res) {
if (remain==0) { [Link](new ArrayList<>(curr)); return; }
for (int i=start; i<[Link]; i++) {
if (c[i]>remain) continue;
[Link](c[i]);
backtrack(c, remain-c[i], i, curr, res);
[Link]([Link]()-1);
}
}
}
Time: O(N^(T/M)) | Space: O(T/M) depth
───────────────────────────────────────────────────────────────────────────────
─

Q40. 3Sum
Problem: Find all unique triplets in array that sum to zero.
Approach: Sort + two-pointer. Fix one element, solve 2Sum for rest.
import [Link].*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
[Link](nums);
List<List<Integer>> res = new ArrayList<>();
for (int i=0; i<[Link]-2; i++) {
if (i>0 && nums[i]==nums[i-1]) continue;
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--;
}
}
return res;
}
}
Time: O(n²) | Space: O(1) extra
───────────────────────────────────────────────────────────────────────────────
─
Q41. Spiral Matrix
Problem: Return all elements of a matrix in spiral order.
Approach: Layer-by-layer peeling with four boundary pointers.
import [Link].*;
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int top=0,bottom=[Link]-1,left=0,right=matrix[0].length-1;
while(top<=bottom && left<=right) {
for(int i=left;i<=right;i++) [Link](matrix[top][i]); top++;
for(int i=top;i<=bottom;i++) [Link](matrix[i][right]); right--;
if(top<=bottom){ for(int i=right;i>=left;i--) [Link](matrix[bottom][i]);
bottom--; }
if(left<=right){ for(int i=bottom;i>=top;i--) [Link](matrix[i][left]); left+
+; }
}
return res;
}
}
Time: O(m*n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q42. Merge Intervals

Problem: Merge all overlapping intervals.
Approach: Sort by start, then greedily merge.
import [Link].*;
class Solution {
public int[][] merge(int[][] intervals) {
[Link](intervals, (a,b)->a[0]-b[0]);
List<int[]> res = new ArrayList<>();
int[] curr = intervals[0];
for (int[] iv : intervals) {
if (iv[0] <= curr[1]) curr[1] = [Link](curr[1], iv[1]);
else { [Link](curr); curr = iv; }
}
[Link](curr);
return [Link](new int[0][]);
}
}
Time: O(n log n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q43. Group Anagrams

Problem: Group strings that are anagrams of each other.
Approach: Sort each string as key in HashMap, group by sorted key.
import [Link].*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for (String s : strs) {
char[] ch = [Link](); [Link](ch);
String key = new String(ch);
[Link](key, k->new ArrayList<>()).add(s);
}
return new ArrayList<>([Link]());
}
 }
Time: O(n * k log k) | Space: O(nk)
───────────────────────────────────────────────────────────────────────────────
─

Q44. Jump Game

Problem: Determine if you can reach the last index from the first.
Approach: Greedy — track the furthest reachable index.
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < [Link]; i++) {
if (i > maxReach) return false;
maxReach = [Link](maxReach, i + nums[i]);
}
return true;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q45. Find Peak Element

Problem: Find a peak element (greater than neighbors) in O(log n).
Approach: Binary search — if nums[mid] < nums[mid+1], peak is to the right.
class Solution {
public int findPeakElement(int[] nums) {
int l=0, r=[Link]-1;
while (l<r) {
int m = l+(r-l)/2;
if (nums[m]<nums[m+1]) l=m+1; else r=m;
}
return l;
}
}
Time: O(log n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q46. Permutations
Problem: Return all possible permutations of a distinct integer array.
Approach: Backtracking — swap elements to generate all arrangements.
import [Link].*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, res);
return res;
}
void backtrack(int[] nums, int start, List<List<Integer>> res) {
if (start==[Link]) {
List<Integer> p=new ArrayList<>(); for(int n:nums) [Link](n); [Link](p);
return;
}
for (int i=start; i<[Link]; i++) {
int t=nums[start]; nums[start]=nums[i]; nums[i]=t;
backtrack(nums, start+1, res);
 t=nums[start]; nums[start]=nums[i]; nums[i]=t;
}
}
}
Time: O(n! * n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q47. Letter Combinations of a Phone Number

Problem: Return all possible letter combinations that a digit string could represent.
Approach: Backtracking over digit mapping.
import [Link].*;
class Solution {
String[] phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if ([Link]()) return res;
backtrack(digits, 0, new StringBuilder(), res);
return res;
}
void backtrack(String d, int i, StringBuilder sb, List<String> res) {
if (i==[Link]()) { [Link]([Link]()); return; }
for (char c : phone[[Link](i)-'0'].toCharArray()) {
[Link](c); backtrack(d,i+1,sb,res); [Link]([Link]()-1);
}
}
}
Time: O(4^n * n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q48. Generate Parentheses

Problem: Generate all valid combinations of n pairs of parentheses.
Approach: Backtracking — add '(' if open < n, add ')' if close < open.
import [Link].*;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(res, "", 0, 0, n);
return res;
}
void backtrack(List<String> res, String s, int open, int close, int n) {
if ([Link]()==2*n) { [Link](s); return; }
if (open<n) backtrack(res, s+"(", open+1, close, n);
if (close<open) backtrack(res, s+")", open, close+1, n);
}
}
Time: O(4^n / sqrt(n)) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q49. Longest Palindromic Substring

Problem: Find the longest palindromic substring in a string.
Approach: Expand around center — try each character and pair as center.
class Solution {
int start=0, maxLen=1;
public String longestPalindrome(String s) {
 for (int i=0; i<[Link](); i++) {
expand(s, i, i);
expand(s, i, i+1);
}
return [Link](start, start+maxLen);
}
void expand(String s, int l, int r) {
while (l>=0 && r<[Link]() && [Link](l)==[Link](r)) { l--; r++; }
if (r-l-1 > maxLen) { maxLen=r-l-1; start=l+1; }
}
}
Time: O(n²) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q50. Daily Temperatures

Problem: Return array where each element is days to wait for warmer temperature.
Approach: Monotonic decreasing stack of indices.
import [Link];
class Solution {
public int[] dailyTemperatures(int[] temps) {
int[] res = new int[[Link]];
Stack<Integer> stack = new Stack<>();
for (int i=0; i<[Link]; i++) {
while (![Link]() && temps[i]>temps[[Link]()])
res[[Link]()] = i - [Link]();
[Link](i);
}
return res;
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q51. Evaluate Reverse Polish Notation

Problem: Evaluate an arithmetic expression in Reverse Polish Notation.
Approach: Stack — push numbers, pop two on operator.
import [Link];
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String t : tokens) {
if ("+-*/".contains(t)) {
int b=[Link](), a=[Link]();
if([Link]("+")) [Link](a+b);
else if([Link]("-")) [Link](a-b);
else if([Link]("*")) [Link](a*b);
else [Link](a/b);
} else [Link]([Link](t));
}
return [Link]();
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─
Q52. Add Two Numbers
Problem: Add two numbers stored in reverse-order linked lists.
Approach: Simulate addition digit by digit with carry.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), curr = dummy;
int carry = 0;
while (l1!=null || l2!=null || carry!=0) {
int sum = carry;
if (l1!=null) { sum+=[Link]; l1=[Link]; }
if (l2!=null) { sum+=[Link]; l2=[Link]; }
carry = sum/10;
[Link] = new ListNode(sum%10); curr=[Link];
}
return [Link];
}
}
Time: O(max(m,n)) | Space: O(max(m,n))
───────────────────────────────────────────────────────────────────────────────
─

Q53. LRU Cache

Problem: Implement LRU cache with get and put in O(1).
Approach: LinkedHashMap with access-order maintains LRU automatically.
import [Link].*;
class LRUCache extends LinkedHashMap<Integer,Integer> {
int cap;
public LRUCache(int capacity) { super(capacity,0.75f,true); cap=capacity; }
public int get(int key) { return [Link](key,-1); }
public void put(int key, int value) { [Link](key,value); }
@Override protected boolean removeEldestEntry([Link] e) { return size()>cap; }
}
Time: O(1) amortized | Space: O(capacity)
───────────────────────────────────────────────────────────────────────────────
─

Q54. Binary Tree Level Order Traversal

Problem: Return level order traversal of binary tree as list of lists.
Approach: BFS using a queue, process level by level.
import [Link].*;
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root==null) return res;
Queue<TreeNode> q = new LinkedList<>(); [Link](root);
while (![Link]()) {
int size=[Link](); List<Integer> level=new ArrayList<>();
for (int i=0;i<size;i++) {
TreeNode node=[Link](); [Link]([Link]);
if([Link]!=null) [Link]([Link]);
if([Link]!=null) [Link]([Link]);
}
[Link](level);
}
return res;
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q55. Lowest Common Ancestor of a Binary Tree

Problem: Find the LCA of two nodes in a binary tree.
Approach: Recursive — if current node is p or q, return it. LCA is where both sides return non-null.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root==null || root==p || root==q) return root;
TreeNode left = lowestCommonAncestor([Link], p, q);
TreeNode right = lowestCommonAncestor([Link], p, q);
if (left!=null && right!=null) return root;
return left!=null ? left : right;
}
}
Time: O(n) | Space: O(h)
───────────────────────────────────────────────────────────────────────────────
─

Q56. Course Schedule

Problem: Determine if you can finish all courses given prerequisites (cycle detection).
Approach: Topological sort with DFS — detect back edges (cycle).
class Solution {
public boolean canFinish(int n, int[][] prereqs) {
List<List<Integer>> adj = new ArrayList<>();
for (int i=0;i<n;i++) [Link](new ArrayList<>());
for (int[] p:prereqs) [Link](p[1]).add(p[0]);
int[] state = new int[n]; // 0=unvisited,1=visiting,2=done
for (int i=0;i<n;i++) if (hasCycle(adj,state,i)) return false;
return true;
}
boolean hasCycle(List<List<Integer>> adj, int[] state, int v) {
if (state[v]==1) return true;
if (state[v]==2) return false;
state[v]=1;
for (int nb:[Link](v)) if (hasCycle(adj,state,nb)) return true;
state[v]=2; return false;
}
}
Time: O(V+E) | Space: O(V+E)
───────────────────────────────────────────────────────────────────────────────
─

Q57. Word Ladder

Problem: Find shortest transformation sequence from beginWord to endWord.
Approach: BFS — change one character at a time, use set for fast lookup.
import [Link].*;
class Solution {
public int ladderLength(String begin, String end, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
Queue<String> q = new LinkedList<>(); [Link](begin);
int steps = 1;
while (![Link]()) {
int size=[Link]();
for (int i=0;i<size;i++) {
String word=[Link](); char[] arr=[Link]();
for (int j=0;j<[Link];j++) {
char orig=arr[j];
 for (char c='a';c<='z';c++) {
arr[j]=c; String next=new String(arr);
if ([Link](end)) return steps+1;
if ([Link](next)) [Link](next);
}
arr[j]=orig;
}
}
steps++;
}
return 0;
}
}
Time: O(M² * N) | Space: O(M² * N)
───────────────────────────────────────────────────────────────────────────────
─

Q58. Network Delay Time

Problem: Find the time it takes for all nodes to receive a signal from node k.
Approach: Dijkstra's shortest path from source node k.
import [Link].*;
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer,List<int[]>> graph = new HashMap<>();
for (int[] t:times) [Link](t[0],x->new ArrayList<>()).add(new
int[]{t[1],t[2]});
int[] dist = new int[n+1]; [Link](dist, Integer.MAX_VALUE); dist[k]=0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
[Link](new int[]{0,k});
while (![Link]()) {
int[] curr=[Link](); int d=curr[0],u=curr[1];
if (d>dist[u]) continue;
for (int[] nb:[Link](u,new ArrayList<>())) {
if (dist[u]+nb[1]<dist[nb[0]]) { dist[nb[0]]=dist[u]+nb[1]; [Link](new
int[]{dist[nb[0]],nb[0]}); }
}
}
int max=0;
for (int i=1;i<=n;i++) { if(dist[i]==Integer.MAX_VALUE) return -1;
max=[Link](max,dist[i]); }
return max;
}
}
Time: O((V+E) log V) | Space: O(V+E)
───────────────────────────────────────────────────────────────────────────────
─
PART 3: HARD QUESTIONS
Advanced problems — for top-tier companies (FAANG, etc.).

Q59. Trapping Rain Water

Problem: Calculate total water trapped between bars in an elevation map.
Approach: Two-pointer — water at each position = min(maxLeft, maxRight) - height.
class Solution {
public int trap(int[] height) {
int left=0, right=[Link]-1;
int maxLeft=0, maxRight=0, water=0;
while (left<right) {
if (height[left]<height[right]) {
if (height[left]>=maxLeft) maxLeft=height[left];
else water+=maxLeft-height[left];
left++;
} else {
if (height[right]>=maxRight) maxRight=height[right];
else water+=maxRight-height[right];
right--;
}
}
return water;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q60. Median of Two Sorted Arrays

Problem: Find median of two sorted arrays in O(log(m+n)).
Approach: Binary search on smaller array to find correct partition.
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
if ([Link] > [Link]) return findMedianSortedArrays(B, A);
int m=[Link], n=[Link], half=(m+n+1)/2;
int lo=0, hi=m;
while (lo<=hi) {
int i=lo+(hi-lo)/2, j=half-i;
int aLeft=i==0?Integer.MIN_VALUE:A[i-1], aRight=i==m?Integer.MAX_VALUE:A[i];
int bLeft=j==0?Integer.MIN_VALUE:B[j-1], bRight=j==n?Integer.MAX_VALUE:B[j];
if (aLeft<=bRight && bLeft<=aRight) {
int maxLeft=[Link](aLeft,bLeft), minRight=[Link](aRight,bRight);
return (m+n)%2==0 ? (maxLeft+minRight)/2.0 : maxLeft;
} else if (aLeft>bRight) hi=i-1; else lo=i+1;
}
return -1;
}
}
Time: O(log(min(m,n))) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q61. Minimum Window Substring

Problem: Find smallest substring of s that contains all characters of t.
Approach: Sliding window with character frequency map.
import [Link].*;
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> need=new HashMap<>(), window=new HashMap<>();
for (char c:[Link]()) [Link](c,1,Integer::sum);
int have=0, required=[Link](), left=0, minLen=Integer.MAX_VALUE, minL=0;
for (int right=0; right<[Link](); right++) {
char c=[Link](right); [Link](c,1,Integer::sum);
if ([Link](c)&&[Link](c).equals([Link](c))) have++;
while (have==required) {
if (right-left+1<minLen) { minLen=right-left+1; minL=left; }
char lc=[Link](left); [Link](lc,-1,Integer::sum);
if ([Link](lc)&&[Link](lc)<[Link](lc)) have--;
left++;
}
}
return minLen==Integer.MAX_VALUE ? "" : [Link](minL,minL+minLen);
}
}
Time: O(|s| + |t|) | Space: O(|s| + |t|)
───────────────────────────────────────────────────────────────────────────────
─

Q62. Longest Consecutive Sequence

Problem: Find length of longest consecutive elements sequence in O(n).
Approach: HashSet — start sequence only at its first element (n-1 not in set).
import [Link].*;
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n:nums) [Link](n);
int best=0;
for (int n:set) {
if () {
int curr=n, len=1;
while ([Link](curr+1)) { curr++; len++; }
best=[Link](best,len);
}
}
return best;
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q63. Regular Expression Matching

Problem: Implement regex matching with '.' (any char) and '*' (zero or more).
Approach: Dynamic programming on 2D boolean table dp[i][j].
class Solution {
public boolean isMatch(String s, String p) {
int m=[Link](), n=[Link]();
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0]=true;
for (int j=1;j<=n;j++) if([Link](j-1)=='*'&&j>=2) dp[0][j]=dp[0][j-2];
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) {
char pc=[Link](j-1), sc=[Link](i-1);
 if (pc=='*') {
dp[i][j]=dp[i][j-2]; // zero occurrence
if ([Link](j-2)=='.'||[Link](j-2)==sc) dp[i][j]|=dp[i-1][j];
} else dp[i][j]=(pc=='.'||pc==sc)&&dp[i-1][j-1];
}
return dp[m][n];
}
}
Time: O(m*n) | Space: O(m*n)
───────────────────────────────────────────────────────────────────────────────
─

Q64. Largest Rectangle in Histogram

Problem: Find the largest rectangle area in a histogram.
Approach: Monotonic stack — maintain increasing stack, pop when shorter bar found.
import [Link];
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int max=0; int n=[Link];
for (int i=0; i<=n; i++) {
int h = (i==n)?0:heights[i];
while (![Link]()&&h<heights[[Link]()]) {
int height=heights[[Link]()];
int width=[Link]()?i:[Link]()-1;
max=[Link](max,height*width);
}
[Link](i);
}
return max;
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q65. Serialize and Deserialize Binary Tree

Problem: Encode a binary tree to a string and decode it back.
Approach: BFS serialization with level-order traversal and null markers.
import [Link].*;
public class Codec {
public String serialize(TreeNode root) {
if(root==null) return "null";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> q = new LinkedList<>(); [Link](root);
while(![Link]()) {
TreeNode n=[Link]();
if(n==null){[Link]("null,");}
else{[Link]([Link]+","); [Link]([Link]); [Link]([Link]);}
}
return [Link]();
}
public TreeNode deserialize(String data) {
String[] nodes=[Link](","); int i=0;
if(nodes[0].equals("null")) return null;
TreeNode root=new TreeNode([Link](nodes[i++]));
Queue<TreeNode> q=new LinkedList<>(); [Link](root);
while(![Link]()) {
TreeNode n=[Link]();
 if(!nodes[i].equals("null")){[Link]=new
TreeNode([Link](nodes[i]));[Link]([Link]);}i++;
if(!nodes[i].equals("null")){[Link]=new
TreeNode([Link](nodes[i]));[Link]([Link]);}i++;
}
return root;
}
}
Time: O(n) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q66. Binary Tree Maximum Path Sum

Problem: Find the maximum path sum in a binary tree (path can start and end anywhere).
Approach: DFS post-order — at each node, compute best path through it.
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root); return maxSum;
}
int dfs(TreeNode node) {
if (node==null) return 0;
int left=[Link](0,dfs([Link]));
int right=[Link](0,dfs([Link]));
maxSum=[Link](maxSum, [Link]+left+right);
return [Link]+[Link](left,right);
}
}
Time: O(n) | Space: O(h)
───────────────────────────────────────────────────────────────────────────────
─

Q67. Word Search II

Problem: Find all words from a dictionary that exist in a 2D board.
Approach: Trie + DFS backtracking — prune early using Trie.
import [Link].*;
class Solution {
class TrieNode { TrieNode[] ch=new TrieNode[26]; String word; }
TrieNode root = new TrieNode();
public List<String> findWords(char[][] board, String[] words) {
for (String w:words) { TrieNode cur=root; for(char c:[Link]()){int
i=c-'a';if([Link][i]==null)[Link][i]=new TrieNode();cur=[Link][i];} [Link]=w; }
List<String> res = new ArrayList<>();
for (int i=0;i<[Link];i++) for(int j=0;j<board[0].length;j++)
dfs(board,i,j,root,res);
return res;
}
void dfs(char[][] b, int i, int j, TrieNode node, List<String> res) {
if(i<0||i>=[Link]||j<0||j>=b[0].length||b[i][j]=='#') return;
char c=b[i][j]; TrieNode next=[Link][c-'a'];
if(next==null) return;
if([Link]!=null){[Link]([Link]);[Link]=null;}
b[i][j]='#';
dfs(b,i+1,j,next,res);dfs(b,i-1,j,next,res);dfs(b,i,j+1,next,res);dfs(b,i,j-
1,next,res);
b[i][j]=c;
}
}
Time: O(M * 4 * 3^(L-1)) | Space: O(N) Trie
───────────────────────────────────────────────────────────────────────────────
─

Q68. Critical Connections in a Network

Problem: Find all critical connections (bridges) in an undirected graph.
Approach: Tarjan's Bridge Finding Algorithm using DFS with discovery and low times.
import [Link].*;
class Solution {
int timer=0;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>>
connections) {
List<List<Integer>> graph=new ArrayList<>(), res=new ArrayList<>();
for(int i=0;i<n;i++) [Link](new ArrayList<>());
for(List<Integer> c:connections)
{[Link]([Link](0)).add([Link](1));[Link]([Link](1)).add([Link](0));}
int[] disc=new int[n], low=new int[n]; [Link](disc,-1);
dfs(graph,0,-1,disc,low,res);
return res;
}
void dfs(List<List<Integer>> g, int u, int parent, int[] disc, int[] low,
List<List<Integer>> res){
disc[u]=low[u]=timer++;
for(int v:[Link](u)){
if(disc[v]==-1){dfs(g,v,u,disc,low,res);low[u]=[Link](low[u],low[v]);
if(low[v]>disc[u]) [Link]([Link](u,v));
} else if(v!=parent) low[u]=[Link](low[u],disc[v]);
}
}
}
Time: O(V+E) | Space: O(V+E)
───────────────────────────────────────────────────────────────────────────────
─

Q69. Swim in Rising Water

Problem: Find minimum time to swim from (0,0) to (n-1,n-1) as water rises.
Approach: Binary search on time + BFS/DFS, or Dijkstra with priority queue.
import [Link].*;
class Solution {
public int swimInWater(int[][] grid) {
int n=[Link];
PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);
boolean[][] visited=new boolean[n][n];
[Link](new int[]{grid[0][0],0,0});
int[][] dirs={{0,1},{0,-1},{1,0},{-1,0}};
while(![Link]()){
int[] curr=[Link](); int t=curr[0],r=curr[1],c=curr[2];
if(r==n-1&&c==n-1) return t;
if(visited[r][c]) continue; visited[r][c]=true;
for(int[] d:dirs){
int nr=r+d[0],nc=c+d[1];
if(nr>=0&&nr<n&&nc>=0&&nc<n&&!visited[nr][nc])
[Link](new int[]{[Link](t,grid[nr][nc]),nr,nc});
}
}
return -1;
}
}
Time: O(n² log n) | Space: O(n²)
───────────────────────────────────────────────────────────────────────────────
─
Q70. Best Time to Buy and Sell Stock III
Problem: Find maximum profit with at most 2 transactions.
Approach: DP tracking 4 states: buy1, sell1, buy2, sell2.
class Solution {
public int maxProfit(int[] prices) {
int buy1=Integer.MIN_VALUE, sell1=0, buy2=Integer.MIN_VALUE, sell2=0;
for (int p : prices) {
buy1 = [Link](buy1, -p);
sell1 = [Link](sell1, buy1 + p);
buy2 = [Link](buy2, sell1 - p);
sell2 = [Link](sell2, buy2 + p);
}
return sell2;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q71. Palindrome Partitioning II

Problem: Find minimum cuts to partition a string so every part is a palindrome.
Approach: DP — expand palindromes from center, update min cuts.
class Solution {
public int minCut(String s) {
int n=[Link]();
int[] cuts=new int[n]; // cuts[i] = min cuts for s[0..i]
for(int i=0;i<n;i++) cuts[i]=i; // worst: cut every char
for(int center=0;center<n;center++){
// odd length
for(int r=0;center-r>=0&&center+r<n&&[Link](center-
r)==[Link](center+r);r++)
cuts[center+r]=(center-r==0)?0:[Link](cuts[center+r],cuts[center-r-
1]+1);
// even length
for(int r=1;center-r+1>=0&&center+r<n&&[Link](center-
r+1)==[Link](center+r);r++)
cuts[center+r]=(center-r+1==0)?0:[Link](cuts[center+r],cuts[center-r]
+1);
}
return cuts[n-1];
}
}
Time: O(n²) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─

Q72. Merge k Sorted Lists

Problem: Merge k sorted linked lists into one sorted list.
Approach: Min-heap (PriorityQueue) — always extract the globally smallest node.
import [Link];
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->[Link]);
for (ListNode node : lists) if (node!=null) [Link](node);
ListNode dummy = new ListNode(0), curr = dummy;
while (![Link]()) {
[Link] = [Link](); curr = [Link];
if ([Link] != null) [Link]([Link]);
 }
return [Link];
}
}
Time: O(N log k) | Space: O(k)
───────────────────────────────────────────────────────────────────────────────
─

Q73. Jump Game II

Problem: Find minimum number of jumps to reach last index.
Approach: Greedy — track current range end and next furthest reach.
class Solution {
public int jump(int[] nums) {
int jumps=0, currEnd=0, farthest=0;
for (int i=0; i<[Link]-1; i++) {
farthest=[Link](farthest, i+nums[i]);
if (i==currEnd) { jumps++; currEnd=farthest; }
}
return jumps;
}
}
Time: O(n) | Space: O(1)
───────────────────────────────────────────────────────────────────────────────
─

Q74. Bus Routes

Problem: Find minimum number of buses to take from source to target stop.
Approach: BFS on bus routes (not stops) — treat each route as a node.
import [Link].*;
class Solution {
public int numBusesToDestination(int[][] routes, int source, int target) {
if (source==target) return 0;
Map<Integer,List<Integer>> stopToRoutes=new HashMap<>();
for(int i=0;i<[Link];i++) for(int stop:routes[i])
[Link](stop,x->new ArrayList<>()).add(i);
Queue<Integer> q=new LinkedList<>(); Set<Integer> visitedStops=new HashSet<>(),
visitedRoutes=new HashSet<>();
[Link](source); [Link](source); int buses=0;
while(![Link]()){
int size=[Link](); buses++;
for(int s=0;s<size;s++){
int stop=[Link]();
for(int route:[Link](stop,new ArrayList<>())){
if([Link](route)) continue; [Link](route);
for(int nextStop:routes[route]){ if(nextStop==target) return buses;
if([Link](nextStop)) [Link](nextStop); }
}
}
}
return -1;
}
}
Time: O(sum of route sizes) | Space: O(same)
───────────────────────────────────────────────────────────────────────────────
─

Q75. Most Stones Removed with Same Row or Column

Problem: Max stones removable — a stone can be removed if another stone shares its row or column.
Approach: Union-Find — group stones sharing rows/columns. Answer = stones - components.
import [Link].*;
class Solution {
Map<Integer,Integer> parent = new HashMap<>();
int islands = 0;
public int removeStones(int[][] stones) {
for (int[] s : stones) union(s[0], ~s[1]);
return [Link] - islands;
}
int find(int x) { [Link](x,x); if([Link](x)!=x)
[Link](x,find([Link](x))); return [Link](x); }
void union(int x, int y) {
int px=find(x), py=find(y);
if () islands++;
if () islands++;
if (px!=py) { [Link](px,py); islands--; }
}
}
Time: O(n α(n)) | Space: O(n)
───────────────────────────────────────────────────────────────────────────────
─
QUICK REFERENCE — Time & Space Complexity
EASY
Two Sum O(n) | O(n)
Remove Duplicates O(n) | O(1)
Buy/Sell Stock O(n) | O(1)
Max Subarray O(n) | O(1)
Binary Search O(logn) | O(1)
Reverse LinkedList O(n) | O(1)
Tree Max Depth O(n) | O(h)

MEDIUM
Product Except Self O(n) | O(1)
3Sum O(n^2) | O(1)
Merge Intervals O(nlogn)| O(n)
Group Anagrams O(nklogk)| O(nk)
LRU Cache O(1) | O(cap)
Course Schedule O(V+E) | O(V+E)
Word Ladder O(M^2*N)| O(M^2*N)

HARD
Trapping Rain Water O(n) | O(1)
Median 2 Arrays O(log(min(m,n)))| O(1)
Min Window Substr O(|s|+|t|)| O(|s|+|t|)
Regex Matching O(mn) | O(mn)
Histogram MaxRect O(n) | O(n)
Merge k Lists O(N logk)| O(k)