50 LeetCode-style Java Problems — Mixed Difficulty

Questions with brief explanations and Java solutions

Format: Problem title, Description, Explanation, Java solution

1. Two Sum
Description: Given an array nums and a target, return indices of the two numbers such that they
add up to target.
Explanation: Use a hashmap to store number->index; for each number check if target - num
exists.
Java Solution:
// O(n) time, O(n) space
class Solution {
public int[] twoSum(int[] nums, int target) {
[Link]<Integer,Integer> m = new [Link]<>();
for(int i=0;i<[Link];i++){
int need = target - nums[i];
if([Link](need)) return new int[]{[Link](need), i};
[Link](nums[i], i);
}
return new int[0];
}
}
--------------------------------------------------------------------------------

2. Add Two Numbers

Description: Add two numbers represented by linked lists (digits reversed). Return sum as list.
Explanation: Use carry, iterate both lists, create new nodes.
Java Solution:
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), cur = dummy;
int carry=0;
while(l1!=null || l2!=null || carry!=0){
if(l1!=null){ carry+=[Link]; l1=[Link]; }
if(l2!=null){ carry+=[Link]; l2=[Link]; }
[Link] = new ListNode(carry%10);
cur = [Link];
carry /= 10;
}
return [Link];
}
}
--------------------------------------------------------------------------------

3. Longest Substring Without Repeating Characters

Description: Given a string, find length of longest substring without repeating chars.
Explanation: Use sliding window with hashmap/array for last seen index.
Java Solution:
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] last = new int[256];
[Link](last, -1);
int res=0, start=0;
for(int i=0;i<[Link]();i++){
start = [Link](start, last[[Link](i)] + 1);
res = [Link](res, i - start + 1);
last[[Link](i)] = i;
}
return res;
}
}
--------------------------------------------------------------------------------

4. Median of Two Sorted Arrays (hard)

Description: Find median of two sorted arrays in O(log(min(m,n))).
Explanation: Use binary search on partition positions between arrays.
Java Solution:
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
if ([Link] > [Link]) return findMedianSortedArrays(B, A);
int m=[Link], n=[Link];
int imin=0, imax=m, half=(m+n+1)/2;
while(imin<=imax){
int i=(imin+imax)/2;
int j=half-i;
if(i<imax && B[j-1] > A[i]) imin = i+1;
else if(i>imin && A[i-1] > B[j]) imax = i-1;
else{
int maxLeft;
if(i==0) maxLeft=B[j-1];
else if(j==0) maxLeft=A[i-1];
else maxLeft = [Link](A[i-1], B[j-1]);
if((m+n)%2==1) return maxLeft;
int minRight;
if(i==m) minRight=B[j];
else if(j==n) minRight=A[i];
else minRight = [Link](A[i], B[j]);
return (maxLeft + minRight)/2.0;
}
}
return 0.0;
}
}
--------------------------------------------------------------------------------

5. Longest Palindromic Substring

Description: Return the longest palindromic substring.
Explanation: Expand around center for each center (2n-1 centers).
Java Solution:
class Solution {
public String longestPalindrome(String s) {
if(s==null || [Link]()<1) return "";
int start=0,end=0;
for(int i=0;i<[Link]();i++){
int len1 = expand(s,i,i);
int len2 = expand(s,i,i+1);
int len = [Link](len1,len2);
if(len > end-start+1){
start = i - (len-1)/2;
end = i + len/2;
}
}
return [Link](start,end+1);
}
private int expand(String s,int l,int r){
while(l>=0 && r<[Link]() && [Link](l)==[Link](r)){ l--; r++; }
return r-l-1;
}
}
--------------------------------------------------------------------------------

6. ZigZag Conversion
Description: Rearrange string in zigzag on given numRows then read line by line.
Explanation: Simulate rows with StringBuilder and iterate direction.
Java Solution:
class Solution {
public String convert(String s, int numRows) {
if(numRows==1) return s;
StringBuilder[] rows = new StringBuilder[numRows];
for(int i=0;i<numRows;i++) rows[i]=new StringBuilder();
int cur=0, dir=1;
 for(char c: [Link]()){
rows[cur].append(c);
if(cur==0) dir=1;
else if(cur==numRows-1) dir=-1;
cur += dir;
}
StringBuilder ans = new StringBuilder();
for(StringBuilder sb: rows) [Link](sb);
return [Link]();
}
}
--------------------------------------------------------------------------------

7. Reverse Integer
Description: Reverse digits of an integer, handle overflow.
Explanation: Use long or check overflow before multiplying by 10.
Java Solution:
class Solution {
public int reverse(int x) {
long rev=0;
while(x!=0){
rev = rev*10 + x%10;
x /= 10;
if(rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE) return 0;
}
return (int)rev;
}
}
--------------------------------------------------------------------------------

8. String to Integer (atoi)

Description: Implement atoi to convert string to int with handling spaces, signs, overflow.
Explanation: Parse carefully, clamp to int range.
Java Solution:
class Solution {
public int myAtoi(String s) {
s = [Link]();
if([Link]()==0) return 0;
int sign=1,i=0;
if([Link](0)=='+'||[Link](0)=='-'){
if([Link](0)=='-') sign=-1;
i++;
}
long num=0;
while(i<[Link]() && [Link]([Link](i))){
num = num*10 + ([Link](i)-'0');
if(sign*num > Integer.MAX_VALUE) return Integer.MAX_VALUE;
if(sign*num < Integer.MIN_VALUE) return Integer.MIN_VALUE;
i++;
}
return (int)(sign*num);
}
}
--------------------------------------------------------------------------------

9. Palindrome Number
Description: Determine if an integer is palindrome without extra space.
Explanation: Reverse half of the number and compare.
Java Solution:
class Solution {
public boolean isPalindrome(int x) {
if(x<0 || (x%10==0 && x!=0)) return false;
int rev=0;
while(x>rev){
rev = rev*10 + x%10;
x /= 10;
 }
return x==rev || x==rev/10;
}
}
--------------------------------------------------------------------------------

10. Container With Most Water

Description: Given heights, find max area formed by two lines.
Explanation: Two-pointer approach moving shorter pointer inward.
Java Solution:
class Solution {
public int maxArea(int[] h) {
int i=0,j=[Link]-1,ans=0;
while(i<j){
int area = [Link](h[i],h[j])*(j-i);
ans = [Link](ans, area);
if(h[i]<h[j]) i++; else j--;
}
return ans;
}
}
--------------------------------------------------------------------------------

11. Merge Two Sorted Lists

Description: Merge two sorted linked lists and return it as a sorted list.
Explanation: Iterative merge with dummy node.
Java Solution:
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy=new ListNode(0), cur=dummy;
while(l1!=null && l2!=null){
if([Link]<[Link]){ [Link]=l1; l1=[Link]; }
else { [Link]=l2; l2=[Link]; }
cur=[Link];
}
[Link] = (l1!=null)?l1:l2;
return [Link];
}
}
--------------------------------------------------------------------------------

12. Valid Parentheses

Description: Check if input string of brackets is valid.
Explanation: Use stack, push opening, match closing.
Java Solution:
class Solution {
public boolean isValid(String s) {
[Link]<Character> st = new [Link]<>();
for(char c: [Link]()){
if(c=='('||c=='{'||c=='[') [Link](c);
else {
if([Link]()) return false;
char t=[Link]();
if((c==')'&&t!='(')||(c==']'&&t!='[')||(c=='}'&&t!='{')) return false;
}
}
return [Link]();
}
}
--------------------------------------------------------------------------------

13. Generate Parentheses

Description: Generate all combinations of well-formed parentheses for n pairs.
Explanation: Backtracking, add '(' or ')' tracking counts.
Java Solution:
class Solution {
 public List<String> generateParenthesis(int n) {
List<String> res=new ArrayList<>();
backtrack(res, "", 0, 0, n);
return res;
}
private void backtrack(List<String> res, String cur, int open, int close, int n){
if([Link]()==2*n){ [Link](cur); return; }
if(open<n) backtrack(res, cur+"(", open+1, close, n);
if(close<open) backtrack(res, cur+")", open, close+1, n);
}
}
--------------------------------------------------------------------------------

14. Merge k Sorted Lists

Description: Merge k sorted linked lists into one sorted list.
Explanation: Use a min-heap (priority queue) of current nodes.
Java Solution:
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
[Link]<ListNode> pq = new
[Link]<>((a,b)->[Link]);
for(ListNode n: lists) if(n!=null) [Link](n);
ListNode dummy=new ListNode(0), cur=dummy;
while(![Link]()){
ListNode node = [Link]();
[Link] = node; cur = [Link];
if([Link]!=null) [Link]([Link]);
}
return [Link];
}
}
--------------------------------------------------------------------------------

15. Swap Nodes in Pairs

Description: Swap every two adjacent nodes in a linked list.
Explanation: Iterative pointer manipulation with dummy.
Java Solution:
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy=new ListNode(0); [Link]=head;
ListNode prev=dummy;
while([Link]!=null && [Link]!=null){
ListNode a=[Link], b=[Link];
[Link] = b; [Link] = [Link]; [Link] = a;
prev = a;
}
return [Link];
}
}
--------------------------------------------------------------------------------

16. Remove Nth Node From End

Description: Remove nth node from end of list.
Explanation: Two pointers with gap n, remove target node.
Java Solution:
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy=new ListNode(0); [Link]=head;
ListNode fast=dummy, slow=dummy;
for(int i=0;i<n;i++) fast=[Link];
while([Link]!=null){ fast=[Link]; slow=[Link]; }
[Link] = [Link];
return [Link];
}
}
--------------------------------------------------------------------------------
17. Valid Sudoku
Description: Check if a 9x9 board is valid.
Explanation: Use sets for rows, cols, boxes.
Java Solution:
class Solution {
public boolean isValidSudoku(char[][] b) {
for(int i=0;i<9;i++){
boolean[] r=new boolean[9], c=new boolean[9], box=new boolean[9];
for(int j=0;j<9;j++){
if(b[i][j]!='.' && (r[b[i][j]-'1'])) return false;
if(b[i][j]!='.') r[b[i][j]-'1']=true;
if(b[j][i]!='.' && (c[b[j][i]-'1'])) return false;
if(b[j][i]!='.') c[b[j][i]-'1']=true;
int row = 3*(i/3) + j/3;
int col = 3*(i%3) + j%3;
if(b[row][col]!='.' && (box[b[row][col]-'1'])) return false;
if(b[row][col]!='.') box[b[row][col]-'1']=true;
}
}
return true;
}
}
--------------------------------------------------------------------------------

18. Search in Rotated Sorted Array

Description: Search target in rotated sorted array in O(log n).
Explanation: Binary search with rotated check.
Java Solution:
class Solution {
public int search(int[] a, int t){
int l=0,r=[Link]-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]==t) return m;
if(a[l]<=a[m]){
if(a[l]<=t && t<a[m]) r=m-1; else l=m+1;
} else {
if(a[m]<t && t<=a[r]) l=m+1; else r=m-1;
}
}
return -1;
}
}
--------------------------------------------------------------------------------

19. Find First and Last Position of Element in Sorted Array

Description: Find start and end index of target using binary search.
Explanation: Find leftmost and rightmost via two binary searches.
Java Solution:
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[]{findBound(nums,target,true), findBound(nums,target,false)};
}
private int findBound(int[] nums, int t, boolean left){
int l=0,r=[Link]-1,ans=-1;
while(l<=r){
int m=(l+r)/2;
if(nums[m]==t){ ans=m; if(left) r=m-1; else l=m+1; }
else if(nums[m]<t) l=m+1; else r=m-1;
}
return ans;
}
}
--------------------------------------------------------------------------------
20. Combination Sum
Description: Return combinations that sum to target (unlimited use).
Explanation: Backtracking with start index to avoid duplicates.
Java Solution:
class Solution {
public List<List<Integer>> combinationSum(int[] cand, int target) {
List<List<Integer>> res=new ArrayList<>();
[Link](cand);
back(res, new ArrayList<>(), cand, target, 0);
return res;
}
private void back(List<List<Integer>> res, List<Integer> cur, int[] cand, int target, int
start){
if(target==0){ [Link](new ArrayList<>(cur)); return; }
if(target<0) return;
for(int i=start;i<[Link];i++){
[Link](cand[i]);
back(res, cur, cand, target-cand[i], i);
[Link]([Link]()-1);
}
}
}
--------------------------------------------------------------------------------

21. Subsets
Description: Return all subsets of a set.
Explanation: Backtracking or iterative bitmask generation.
Java Solution:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res=new ArrayList<>();
back(res, new ArrayList<>(), nums, 0);
return res;
}
private void back(List<List<Integer>> res, List<Integer> cur, int[] nums, int idx){
[Link](new ArrayList<>(cur));
for(int i=idx;i<[Link];i++){
[Link](nums[i]);
back(res, cur, nums, i+1);
[Link]([Link]()-1);
}
}
}
--------------------------------------------------------------------------------

22. Word Search

Description: Given board and word, check if word exists by adjacent letters without reuse.
Explanation: DFS with visited marking and backtracking.
Java Solution:
class Solution {
public boolean exist(char[][] b, String w) {
int m=[Link],n=b[0].length;
for(int i=0;i<m;i++) for(int j=0;j<n;j++)
if(dfs(b,w,i,j,0)) return true;
return false;
}
private boolean dfs(char[][] b, String w, int i, int j, int k){
if(k==[Link]()) return true;
if(i<0||j<0||i>=[Link]||j>=b[0].length||b[i][j]!=[Link](k)) return false;
char tmp = b[i][j]; b[i][j]='#';
boolean found =
dfs(b,w,i+1,j,k+1)||dfs(b,w,i-1,j,k+1)||dfs(b,w,i,j+1,k+1)||dfs(b,w,i,j-1,k+1);
b[i][j]=tmp;
return found;
}
}
--------------------------------------------------------------------------------

23. Number of Islands

Description: Count islands in grid of '1's and '0's.
Explanation: DFS/BFS to mark visited islands.
Java Solution:
class Solution {
public int numIslands(char[][] g) {
int m=[Link], n=g[0].length, cnt=0;
for(int i=0;i<m;i++) for(int j=0;j<n;j++)
if(g[i][j]=='1'){ cnt++; dfs(g,i,j); }
return cnt;
}
private void dfs(char[][] g,int i,int j){
if(i<0||j<0||i>=[Link]||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);
}
}
--------------------------------------------------------------------------------

24. Climbing Stairs

Description: Compute number of ways to reach n stairs (1 or 2 steps).
Explanation: Fibonacci DP or constant space.
Java Solution:
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;
}
}
--------------------------------------------------------------------------------

25. Best Time to Buy and Sell Stock

Description: Max profit from single transaction.
Explanation: Track min price and max profit.
Java Solution:
class Solution {
public int maxProfit(int[] p) {
int min=p[0], res=0;
for(int i=1;i<[Link];i++){ res=[Link](res, p[i]-min); min=[Link](min,p[i]); }
return res;
}
}
--------------------------------------------------------------------------------

26. Maximum Subarray

Description: Find contiguous subarray with largest sum (Kadane).
Explanation: Keep current sum and max.
Java Solution:
class Solution {
public int maxSubArray(int[] a) {
int cur=a[0], max=a[0];
for(int i=1;i<[Link];i++){ cur=[Link](a[i], cur+a[i]); max=[Link](max,cur); }
return max;
}
}
--------------------------------------------------------------------------------

27. Product of Array Except Self

Description: Return array where each element is product of all others without division.
Explanation: Prefix and suffix products in two passes.
Java Solution:
class Solution {
 public int[] productExceptSelf(int[] nums) {
int n=[Link];
int[] res=new int[n];
res[0]=1;
for(int i=1;i<n;i++) res[i]=res[i-1]*nums[i-1];
int r=1;
for(int i=n-1;i>=0;i--){ res[i]*=r; r*=nums[i]; }
return res;
}
}
--------------------------------------------------------------------------------

28. Find Minimum in Rotated Sorted Array

Description: Find minimum element in rotated sorted array.
Explanation: Binary search comparing mid to right.
Java Solution:
class Solution {
public int findMin(int[] a) {
int l=0,r=[Link]-1;
while(l<r){
int m=(l+r)/2;
if(a[m]>a[r]) l=m+1; else r=m;
}
return a[l];
}
}
--------------------------------------------------------------------------------

29. Search a 2D Matrix

Description: Search in matrix where rows and columns sorted sequentially.
Explanation: Map 2D to 1D index or binary search per row.
Java Solution:
class Solution {
public boolean searchMatrix(int[][] m, int t) {
if([Link]==0) return false;
int r=0,c=m[0].length-1;
while(r<[Link] && c>=0){
if(m[r][c]==t) return true;
if(m[r][c]>t) c--; else r++;
}
return false;
}
}
--------------------------------------------------------------------------------

30. Kth Largest Element in an Array

Description: Return kth largest element.
Explanation: Use quickselect or min-heap of size k.
Java Solution:
class Solution {
public int findKthLargest(int[] a, int k) {
[Link]<Integer> pq = new [Link]<>();
for(int x: a){
[Link](x);
if([Link]()>k) [Link]();
}
return [Link]();
}
}
--------------------------------------------------------------------------------

31. Top K Frequent Elements

Description: Return k most frequent elements.
Explanation: Use hashmap + bucket sort or heap.
Java Solution:
class Solution {
 public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> cnt=new HashMap<>();
for(int n:nums) [Link](n,[Link](n,0)+1);
List<Integer>[] buckets = new List[[Link]+1];
for(int key: [Link]()){
int f=[Link](key);
if(buckets[f]==null) buckets[f]=new ArrayList<>();
buckets[f].add(key);
}
int[] res=new int[k]; int idx=0;
for(int i=[Link]-1;i>=0 && idx<k;i--) if(buckets[i]!=null) {
for(int x: buckets[i]) { res[idx++]=x; if(idx==k) break; }
}
return res;
}
}
--------------------------------------------------------------------------------

32. Minimum Window Substring

Description: Find minimum window in s containing all chars of t.
Explanation: Use sliding window with counts and expand/contract, track matched counts.
Java Solution:
class Solution {
public String minWindow(String s, String t) {
if([Link]()==0 || [Link]()==0) return "";
int[] need=new int[128];
for(char c: [Link]()) need[c]++;
int left=0, count=0, minLen=Integer.MAX_VALUE, start=0;
for(int right=0; right<[Link](); right++){
char c = [Link](right);
if(need[c]-- > 0) count++;
while(count == [Link]()){
if(right-left+1 < minLen){ minLen = right-left+1; start = left; }
if(need[[Link](left)]++ == 0) count--;
left++;
}
}
return minLen==Integer.MAX_VALUE? "": [Link](start, start+minLen);
}
}
--------------------------------------------------------------------------------

33. Course Schedule (can finish)

Description: Given numCourses and prerequisites pairs, detect if possible to finish all.
Explanation: Use DFS cycle detection or Kahn's BFS (topological sort).
Java Solution:
class Solution {
public boolean canFinish(int n, int[][] pre) {
List<Integer>[] g = new List[n];
for(int i=0;i<n;i++) g[i]=new ArrayList<>();
int[] indeg = new int[n];
for(int[] p: pre){ g[p[1]].add(p[0]); indeg[p[0]]++; }
Queue<Integer> q = new ArrayDeque<>();
for(int i=0;i<n;i++) if(indeg[i]==0) [Link](i);
int cnt=0;
while(![Link]()){
int u=[Link](); cnt++;
for(int v: g[u]) if(--indeg[v]==0) [Link](v);
}
return cnt==n;
}
}
--------------------------------------------------------------------------------

34. Serialize and Deserialize Binary Tree

Description: Design codec to serialize and deserialize binary tree.
Explanation: Use preorder with null markers or BFS.
Java Solution:
public class Codec {
public String serialize(TreeNode root) {
StringBuilder sb=new StringBuilder();
build(root,sb);
return [Link]();
}
private void build(TreeNode r, StringBuilder sb){
if(r==null){ [Link]("null,"); return; }
[Link]([Link]).append(",");
build([Link],sb); build([Link],sb);
}
public TreeNode deserialize(String data) {
[Link]<String> q = new
[Link]<>([Link]([Link](",")));
return buildTree(q);
}
private TreeNode buildTree([Link]<String> q){
String s=[Link]();
if([Link]("null")) return null;
TreeNode node=new TreeNode([Link](s));
[Link] = buildTree(q); [Link] = buildTree(q);
return node;
}
}
--------------------------------------------------------------------------------

35. Binary Tree Level Order Traversal

Description: Return level order traversal of a binary tree.
Explanation: Use BFS with queue and size loop per level.
Java Solution:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
if(root==null) return res;
Queue<TreeNode> q=new ArrayDeque<>(); [Link](root);
while(![Link]()){
int sz=[Link]();
List<Integer> level=new ArrayList<>();
for(int i=0;i<sz;i++){
TreeNode n=[Link](); [Link]([Link]);
if([Link]!=null) [Link]([Link]);
if([Link]!=null) [Link]([Link]);
}
[Link](level);
}
return res;
}
}
--------------------------------------------------------------------------------

36. Maximum Depth of Binary Tree

Description: Return max depth (height) of binary tree.
Explanation: Simple DFS recursion.
Java Solution:
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
return 1 + [Link](maxDepth([Link]), maxDepth([Link]));
}
}
--------------------------------------------------------------------------------

37. Balanced Binary Tree

Description: Check if tree is height-balanced.
Explanation: Postorder DFS returning -1 for unbalanced, else height.
Java Solution:
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root)!=-1;
}
private int height(TreeNode r){
if(r==null) return 0;
int l=height([Link]); if(l==-1) return -1;
int rgh=height([Link]); if(rgh==-1) return -1;
if([Link](l-rgh)>1) return -1;
return 1+[Link](l,rgh);
}
}
--------------------------------------------------------------------------------

38. Path Sum

Description: Check if root-to-leaf path sums to target.
Explanation: DFS subtracting node values.
Java Solution:
class Solution {
public boolean hasPathSum(TreeNode root, int target) {
if(root==null) return false;
if([Link]==null && [Link]==null) return [Link]==target;
return hasPathSum([Link], [Link]) || hasPathSum([Link], target-
[Link]);
}
}
--------------------------------------------------------------------------------

39. Convert Sorted Array to BST

Description: Convert sorted array to height-balanced BST.
Explanation: Recurse on mid for root.
Java Solution:
class Solution {
public TreeNode sortedArrayToBST(int[] a) {
return build(a,0,[Link]-1);
}
private TreeNode build(int[] a,int l,int r){
if(l>r) return null;
int m=(l+r)/2;
TreeNode node=new TreeNode(a[m]);
[Link]=build(a,l,m-1); [Link]=build(a,m+1,r);
return node;
}
}
--------------------------------------------------------------------------------

40. Symmetric Tree

Description: Check if tree is mirror of itself.
Explanation: Compare left and right subtrees recursively.
Java Solution:
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return isMirror([Link], [Link]);
}
private boolean isMirror(TreeNode a, TreeNode b){
if(a==null||b==null) return a==b;
if([Link]!=[Link]) return false;
return isMirror([Link],[Link]) && isMirror([Link],[Link]);
}
}
--------------------------------------------------------------------------------

41. Binary Tree Zigzag Level Order

Description: Return zigzag level order traversal.
Explanation: BFS with level toggle or use deque to add accordingly.
Java Solution:
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
if(root==null) return res;
Queue<TreeNode> q=new ArrayDeque<>(); [Link](root);
boolean left=true;
while(![Link]()){
int sz=[Link](); LinkedList<Integer> level=new LinkedList<>();
for(int i=0;i<sz;i++){
TreeNode n=[Link]();
if(left) [Link]([Link]); else [Link]([Link]);
if([Link]!=null) [Link]([Link]); if([Link]!=null) [Link]([Link]);
}
[Link](level); left=!left;
}
return res;
}
}
--------------------------------------------------------------------------------

42. Word Break

Description: Given wordDict, determine if s can be segmented into words.
Explanation: DP boolean array using dictionary set.
Java Solution:
class Solution {
public boolean wordBreak(String s, List<String> dict) {
Set<String> set = new HashSet<>(dict);
boolean[] dp = new boolean[[Link]()+1];
dp[0]=true;
for(int i=1;i<=[Link]();i++){
for(int j=0;j<i;j++){
if(dp[j] && [Link]([Link](j,i))){ dp[i]=true; break; }
}
}
return dp[[Link]()];
}
}
--------------------------------------------------------------------------------

43. Longest Increasing Subsequence

Description: Length of LIS in O(n log n).
Explanation: Use patience sorting with tails array and binary search.
Java Solution:
class Solution {
public int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for(int x: nums){
int i = [Link](tails, x);
if(i<0) i = -i-1;
if(i==[Link]()) [Link](x); else [Link](i,x);
}
return [Link]();
}
}
--------------------------------------------------------------------------------

44. LRU Cache (design)

Description: Design LRU cache with get and put in O(1).
Explanation: Use LinkedHashMap or custom doubly-linked list + hashmap.
Java Solution:
class LRUCache extends LinkedHashMap<Integer,Integer> {
private int capacity;
public LRUCache(int capacity) {
 super(capacity, 0.75f, true);
[Link] = capacity;
}
public int get(int key) { return [Link](key, -1); }
public void put(int key, int value) { [Link](key, value); }
protected boolean removeEldestEntry([Link]<Integer,Integer> eldest){
return size() > capacity;
}
}
--------------------------------------------------------------------------------

45. Merge Intervals

Description: Given intervals, merge overlapping ones.
Explanation: Sort by start and merge iteratively.
Java Solution:
class Solution {
public int[][] merge(int[][] intervals) {
if([Link]==0) return new int[0][];
[Link](intervals, (a,b)->a[0]-b[0]);
List<int[]> res=new ArrayList<>();
int[] cur = intervals[0];
for(int i=1;i<[Link];i++){
if(intervals[i][0] <= cur[1]) cur[1] = [Link](cur[1], intervals[i][1]);
else { [Link](cur); cur = intervals[i]; }
}
[Link](cur);
return [Link](new int[[Link]()][]);
}
}
--------------------------------------------------------------------------------

46. Meeting Rooms II (min meeting rooms)

Description: Given intervals, find min number of conference rooms required.
Explanation: Use min-heap on end times or sweep-line.
Java Solution:
class Solution {
public int minMeetingRooms(int[][] intervals) {
if([Link]==0) return 0;
[Link](intervals, (a,b)->a[0]-b[0]);
PriorityQueue<Integer> pq=new PriorityQueue<>();
[Link](intervals[0][1]);
for(int i=1;i<[Link];i++){
if(intervals[i][0] >= [Link]()) [Link]();
[Link](intervals[i][1]);
}
return [Link]();
}
}
--------------------------------------------------------------------------------

47. Insert Interval

Description: Insert interval and merge overlaps.
Explanation: Add intervals before, merge overlapping, then after.
Java Solution:
class Solution {
public int[][] insert(int[][] intervals, int[] newInt) {
List<int[]> res=new ArrayList<>();
int i=0;
while(i<[Link] && intervals[i][1] < newInt[0]) [Link](intervals[i++]);
while(i<[Link] && intervals[i][0] <= newInt[1]){
newInt[0] = [Link](newInt[0], intervals[i][0]);
newInt[1] = [Link](newInt[1], intervals[i++][1]);
}
[Link](newInt);
while(i<[Link]) [Link](intervals[i++]);
return [Link](new int[[Link]()][]);
 }
}
--------------------------------------------------------------------------------

48. Gas Station

Description: Find start index if can complete circuit of gas stations.
Explanation: Check total gas >= total cost and simulate greedily tracking deficit.
Java Solution:
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total=0, sum=0, start=0;
for(int i=0;i<[Link];i++){
int diff = gas[i]-cost[i];
sum += diff; total += diff;
if(sum<0){ start = i+1; sum=0; }
}
return total<0 ? -1 : start;
}
}
--------------------------------------------------------------------------------

49. Trapping Rain Water

Description: Given elevation map, compute how much water can be trapped.
Explanation: Two-pointer approach keeping leftMax and rightMax.
Java Solution:
class Solution {
public int trap(int[] h) {
int l=0, r=[Link]-1, leftMax=0, rightMax=0, res=0;
while(l<r){
if(h[l]<h[r]){
leftMax = [Link](leftMax, h[l]);
res += leftMax - h[l];
l++;
} else {
rightMax = [Link](rightMax, h[r]);
res += rightMax - h[r];
r--;
}
}
return res;
}
}
--------------------------------------------------------------------------------

50. Word Ladder (shortest transformation)

Description: Given begin, end word and wordList, return length of shortest transformation.
Explanation: Use BFS on words changing one letter each step; use bidirectional BFS for speed.
Java Solution:
class Solution {
public int ladderLength(String begin, String end, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if() return 0;
Set<String> beginSet = new HashSet<>(), endSet = new HashSet<>(), visited = new
HashSet<>();
[Link](begin); [Link](end); int len=1;
while(![Link]() && ![Link]()){
if([Link]() > [Link]()) {
Set<String> tmp=beginSet; beginSet=endSet; endSet=tmp;
}
Set<String> next = new HashSet<>();
for(String w: beginSet){
char[] arr = [Link]();
for(int i=0;i<[Link];i++){
char old = arr[i];
for(char c='a'; c<='z'; c++){
arr[i]=c; String nw = new String(arr);
 if([Link](nw)) return len+1;
if( && [Link](nw)){
[Link](nw); [Link](nw);
}
}
arr[i]=old;
}
}
beginSet = next; len++;
}
return 0;
}
}
--------------------------------------------------------------------------------