Infosys DSE — 50 Medium Leet Code-style Problems (java)

Created by SYNTAX ERROR | Abhishek Rathor

Each entry: Problem → Short approach/algorithm → Java solution → Time & Space
complexity.

1. Two Sum (if unsorted)

Problem: Given array nums and target, return indices of two numbers summing to
target.
Approach: HashMap for complement lookup.

public int[] twoSum(int[] nums, int target) {

Map<Integer,Integer> m = new HashMap<>();
for(int i=0;i<nums.length;i++){
int c = target - nums[i];
if(m.containsKey(c)) return new int[]{m.get(c), i};
m.put(nums[i], i);
}
return new int[]{-1,-1};
}

Time: O(n) Space: O(n)

2. Longest Substring Without Repeating Characters

Approach: Sliding window with last index array/map.

public int lengthOfLongestSubstring(String s) {

int[] last = new int[256]; Arrays.fill(last, -1);
int res=0, start=0;
for(int i=0;i<s.length();i++){
start = Math.max(start, last[s.charAt(i)] + 1);
res = Math.max(res, i-start+1);
last[s.charAt(i)] = i;
}
return res;
}

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

3. Add Two Numbers (linked list)

Approach: Simulate addition with carry.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode dummy=new ListNode(0), cur=dummy;
 int carry=0;
while(l1!=null || l2!=null || carry!=0){
int s = carry + (l1!=null?l1.val:0) + (l2!=null?l2.val:0);
carry = s/10;
cur.next = new ListNode(s%10);
cur = cur.next;
if(l1!=null) l1=l1.next;
if(l2!=null) l2=l2.next;
}
return dummy.next;
}

Time: O(max(n,m)) Space: O(max(n,m))

4. Longest Palindromic Substring (center expand)

Approach: Expand from each center.

public String longestPalindrome(String s) {

if(s==null||s.length()<1) return "";
int start=0,end=0;
for(int i=0;i<s.length();i++){
int l1 = expand(s,i,i);
int l2 = expand(s,i,i+1);
int len = Math.max(l1,l2);
if(len > end-start+1){
start = i - (len-1)/2;
end = i + len/2;
}
}
return s.substring(start,end+1);
}
private int expand(String s,int l,int r){
while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){ l--; r++; }
return r-l-1;
}

Time: O(n^2) Space: O(1)

5. Merge Intervals
Approach: Sort by start and merge adjacent intervals.

public int[][] merge(int[][] intervals) {

if(intervals.length<=1) return intervals;
Arrays.sort(intervals,(a,b)->a[0]-b[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()][]);
}

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

6. Search in Rotated Sorted Array

Approach: Modified binary search to choose half.

public int search(int[] nums, int target) {

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

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

7. Top K Frequent Elements

Approach: Frequency map + min-heap of size k.

public int[] topKFrequent(int[] nums, int k) {

Map<Integer,Integer> m=new HashMap<>();
for(int n:nums) m.put(n,m.getOrDefault(n,0)+1);
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->m.get(a)-
m.get(b));
for(int key: m.keySet()){
pq.offer(key);
if(pq.size()>k) pq.poll();
}
int[] res=new int[k];
for(int i=k-1;i>=0;i--) res[i]=pq.poll();
return res;
}

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

8. Kth Smallest Element in a BST

Approach: Inorder traversal (iterative or recursive).

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

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

9. Word Break
Approach: DP boolean reachable array.

public boolean wordBreak(String s, List<String> wordDict) {

Set<String> set=new HashSet<>(wordDict);
boolean[] dp=new boolean[s.length()+1];
dp[0]=true;
for(int i=1;i<=s.length();i++){
for(int j=0;j<i;j++){
if(dp[j] && set.contains(s.substring(j,i))){ dp[i]=true;
break;}
}
}
return dp[s.length()];
}

Time: O(n^2 * L) (L substring cost) Space: O(n)

10. Number of Islands

Approach: DFS/BFS to mark visited cells.

public int numIslands(char[][] grid) {

if(grid==null||grid.length==0) return 0;
int m=grid.length,n=grid[0].length, count=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1'){ count++; dfs(grid,i,j); }
}
}
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);
}

Time: O(mn) Space: O(mn) recursion

 11. Course Schedule (detect cycle in directed graph)
Approach: Topological sort / DFS cycle detection.

public boolean canFinish(int numCourses, int[][] prerequisites) {

List<Integer>[] g = new List[numCourses];
for(int i=0;i<numCourses;i++) g[i]=new ArrayList<>();
int[] indeg=new int[numCourses];
for(int[] p:prerequisites){ g[p[1]].add(p[0]); indeg[p[0]]++; }
Queue<Integer> q=new LinkedList<>();
for(int i=0;i<numCourses;i++) if(indeg[i]==0) q.offer(i);
int cnt=0;
while(!q.isEmpty()){
int u=q.poll(); cnt++;
for(int v:g[u]) if(--indeg[v]==0) q.offer(v);
}
return cnt==numCourses;
}

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

12. Course Schedule II (topological order)

Approach: Kahn’s algorithm output ordering.

public int[] findOrder(int numCourses, int[][] prerequisites) {

List<Integer>[] g = new List[numCourses];
for(int i=0;i<numCourses;i++) g[i]=new ArrayList<>();
int[] indeg = new int[numCourses];
for(int[] p:prerequisites){ g[p[1]].add(p[0]); indeg[p[0]]++; }
Queue<Integer> q = new LinkedList<>();
for(int i=0;i<numCourses;i++) if(indeg[i]==0) q.offer(i);
int idx=0; int[] res=new int[numCourses];
while(!q.isEmpty()){
int u=q.poll(); res[idx++]=u;
for(int v:g[u]) if(--indeg[v]==0) q.offer(v);
}
return idx==numCourses?res:new int[0];
}

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

13. Binary Tree Level Order Traversal

Approach: BFS using queue.

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> res=new ArrayList<>();
if(root==null) return res;
Queue<TreeNode> q=new LinkedList<>(); q.offer(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.offer(n.left);
if(n.right!=null) q.offer(n.right);
 }
res.add(level);
}
return res;
}

Time: O(n) Space: O(n)

14. Serialize and Deserialize Binary Tree

Approach: Preorder with null markers and queue during deserialization.

public String serialize(TreeNode root) {

StringBuilder sb=new StringBuilder();
build(root,sb);
return sb.toString();
}
private void build(TreeNode r,StringBuilder sb){
if(r==null){ sb.append("X,"); return; }
sb.append(r.val).append(",");
build(r.left,sb); build(r.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 v=q.poll();
if(v.equals("X")) return null;
TreeNode node=new TreeNode(Integer.parseInt(v));
node.left = buildTree(q); node.right = buildTree(q);
return node;
}

Time: O(n) Space: O(n)

15. LRU Cache

Approach: HashMap + Doubly linked list. (Compact single-class implementation)

class LRUCache {
private int cap;
private Map<Integer,Node> map;
private Node head, tail;
class Node{ int k,v; Node prev,next; Node(int k,int
v){this.k=k;this.v=v;} }
public LRUCache(int capacity){
this.cap=capacity; map=new HashMap<>();
head=new Node(0,0); tail=new Node(0,0);
head.next=tail; tail.prev=head;
}
public int get(int key){
if(!map.containsKey(key)) return -1;
Node n=map.get(key); remove(n); insertFront(n); return n.v;
}
 public void put(int key,int value){
if(map.containsKey(key)){ remove(map.get(key)); map.remove(key); }
if(map.size()==cap){ map.remove(tail.prev.k); remove(tail.prev); }
Node n=new Node(key,value); insertFront(n); map.put(key,n);
}
private void remove(Node n){ n.prev.next = n.next; n.next.prev =
n.prev; }
private void insertFront(Node n){ n.next=head.next; head.next.prev=n;
head.next=n; n.prev=head; }
}

Time: O(1) per op Space: O(capacity)

16. K Closest Points to Origin

Approach: Use max-heap of size k or Quickselect.

public int[][] kClosest(int[][] points, int k) {

PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)-
>(b[0]*b[0]+b[1]*b[1])-(a[0]*a[0]+a[1]*a[1]));
for(int[] p:points){
pq.offer(p);
if(pq.size()>k) pq.poll();
}
int[][] res=new int[k][2];
for(int i=k-1;i>=0;i--) res[i]=pq.poll();
return res;
}

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

17. Minimum Window Substring

Approach: Sliding window with counts for target; expand right until all matched,
shrink left to minimize.

public String minWindow(String s, String t) {

if(s.length()==0 || t.length()==0) return "";
int[] need=new int[128];
for(char c:t.toCharArray()) need[c]++;
int required=t.length(), l=0, minLen=Integer.MAX_VALUE, start=0;
for(int r=0;r<s.length();r++){
if(need[s.charAt(r)]-- > 0) required--;
while(required==0){
if(r-l+1 < minLen){ minLen = r-l+1; start=l; }
if(++need[s.charAt(l++)] > 0) required++;
}
}
return minLen==Integer.MAX_VALUE?"":s.substring(start,start+minLen);
}

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

 18. Word Ladder (shortest transformation length)
Approach: BFS on word graph with one-letter transformations; precompute generic
forms.

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

Set<String> dict = new HashSet<>(wordList);
if(!dict.contains(end)) return 0;
Queue<String> q=new LinkedList<>();
q.offer(begin);
Set<String> vis=new HashSet<>(); vis.add(begin);
int lvl=1;
while(!q.isEmpty()){
int sz=q.size();
for(int i=0;i<sz;i++){
String cur=q.poll();
char[] a=cur.toCharArray();
for(int j=0;j<a.length;j++){
char old=a[j];
for(char c='a';c<='z';c++){
a[j]=c; String nxt=new String(a);
if(nxt.equals(end)) return lvl+1;
if(dict.contains(nxt) && !vis.contains(nxt)){
vis.add(nxt); q.offer(nxt); }
}
a[j]=old;
}
}
lvl++;
}
return 0;
}

Time: O(M * 26 * L) (M words, L length) Space: O(M)

19. Trapping Rain Water

Approach: Two-pointer with leftMax/rightMax.

public int trap(int[] h) {

int l=0,r=h.length-1, leftMax=0,rightMax=0,res=0;
while(l<r){
if(h[l] < h[r]){
leftMax=Math.max(leftMax,h[l]);
res += leftMax - h[l++];
} else {
rightMax=Math.max(rightMax,h[r]);
res += rightMax - h[r--];
}
}
return res;
}

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

 20. Find Median from Data Stream
Approach: Two heaps (max-heap low, min-heap high).

class MedianFinder {
PriorityQueue<Integer> lo = new
PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> hi = new PriorityQueue<>();
public void addNum(int num) {
lo.offer(num);
hi.offer(lo.poll());
if(lo.size() < hi.size()) lo.offer(hi.poll());
}
public double findMedian() {
if(lo.size()>hi.size()) return lo.peek();
return (lo.peek()+hi.peek())/2.0;
}
}

Time: O(log n) per add Space: O(n)

21. Coin Change (min coins)

Approach: DP bottom-up for min coins.

public int coinChange(int[] coins, int amount) {

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

Time: O(amount * nCoins) Space: O(amount)

22. Subarray Sum Equals K

Approach: Prefix sum with hashmap counts.

public int subarraySum(int[] nums, int k) {

Map<Integer,Integer> m=new HashMap<>(); m.put(0,1);
int sum=0,res=0;
for(int n:nums){
sum+=n;
if(m.containsKey(sum-k)) res+=m.get(sum-k);
m.put(sum, m.getOrDefault(sum,0)+1);
}
return res;
}

Time: O(n) Space: O(n)

 23. Minimum Path Sum (grid)
Approach: DP in-place or 1D DP.

public int minPathSum(int[][] grid) {

int m=grid.length,n=grid[0].length;
for(int i=1;i<m;i++) grid[i][0]+=grid[i-1][0];
for(int j=1;j<n;j++) grid[0][j]+=grid[0][j-1];
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
grid[i][j]+=Math.min(grid[i-1][j], grid[i][j-1]);
return grid[m-1][n-1];
}

Time: O(mn) Space: O(1)

24. Unique Paths II (with obstacles)

Approach: DP with obstacle checks.

public int uniquePathsWithObstacles(int[][] obs) {

int m=obs.length,n=obs[0].length;
if(obs[0][0]==1) return 0;
obs[0][0]=1;
for(int i=1;i<m;i++) obs[i][0] = (obs[i][0]==0?obs[i-1][0]:0);
for(int j=1;j<n;j++) obs[0][j] = (obs[0][j]==0?obs[0][j-1]:0);
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
obs[i][j] = (obs[i][j]==0? obs[i-1][j]+obs[i][j-1] : 0);
return obs[m-1][n-1];
}

Time: O(mn) Space: O(1)

25. Maximum Product Subarray

Approach: Track max and min ending here because of negatives.

public int maxProduct(int[] nums) {

int res = nums[0], curMax = nums[0], curMin = nums[0];
for(int i=1;i<nums.length;i++){
if(nums[i]<0){
int t=curMax; curMax=curMin; curMin=t;
}
curMax = Math.max(nums[i], curMax*nums[i]);
curMin = Math.min(nums[i], curMin*nums[i]);
res = Math.max(res, curMax);
}
return res;
}

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

 26. Search a 2D Matrix II
Approach: Start from top-right and eliminate row/col each step.

public boolean searchMatrix(int[][] matrix, int target) {

int m=matrix.length, n=matrix[0].length;
int r=0,c=n-1;
while(r<m && c>=0){
if(matrix[r][c]==target) return true;
else if(matrix[r][c] > target) c--;
else r++;
}
return false;
}

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

27. Reverse Nodes in k-Group (linked list)

Approach: Iterative reversing in groups with dummy head.

public ListNode reverseKGroup(ListNode head, int k) {

ListNode dummy=new ListNode(0); dummy.next=head;
ListNode prev=dummy;
while(true){
ListNode kth = prev;
for(int i=0;i<k && kth!=null;i++) kth=kth.next;
if(kth==null) break;
ListNode nextGroup = kth.next;
// reverse [prev.next .. kth]
ListNode cur = prev.next, prevNode = nextGroup;
while(cur!=nextGroup){
ListNode tmp = cur.next;
cur.next = prevNode;
prevNode = cur;
cur = tmp;
}
ListNode tmp = prev.next;
prev.next = kth;
prev = tmp;
}
return dummy.next;
}

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

28. Clone Graph

Approach: BFS/DFS with hashmap of original->copy.

public Node cloneGraph(Node node) {

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

Time: O(N+E) Space: O(N)

29. Binary Tree Right Side View

Approach: BFS level order, take last element of each level.

public List<Integer> rightSideView(TreeNode root) {

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

Time: O(n) Space: O(n)

30. Find Peak Element

Approach: Binary search leveraging neighbor comparisons.

public int findPeakElement(int[] nums) {

int l=0,r=nums.length-1;
while(l<r){
int m=(l+r)/2;
if(nums[m] < nums[m+1]) l=m+1;
else r=m;
}
return l;
}

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

 31. House Robber II (circle)
Approach: Two runs of linear DP excluding first or last.

public int rob(int[] nums) {

if(nums.length==1) return nums[0];
return Math.max(robLinear(nums,0,nums.length-2),
robLinear(nums,1,nums.length-1));
}
private int robLinear(int[] a,int l,int r){
int incl=0, excl=0;
for(int i=l;i<=r;i++){
int n = Math.max(incl, excl+a[i]);
excl = incl;
incl = n;
}
return incl;
}

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

32. Binary Tree Zigzag Level Order Traversal

Approach: BFS with level parity flip or deque.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

List<List<Integer>> res=new ArrayList<>();
if(root==null) return res;
Queue<TreeNode> q=new LinkedList<>(); q.offer(root);
boolean leftToRight=true;
while(!q.isEmpty()){
int sz=q.size(); LinkedList<Integer> level=new LinkedList<>();
for(int i=0;i<sz;i++){
TreeNode n=q.poll();
if(leftToRight) level.addLast(n.val); else
level.addFirst(n.val);
if(n.left!=null) q.offer(n.left);
if(n.right!=null) q.offer(n.right);
}
res.add(level); leftToRight=!leftToRight;
}
return res;
}

Time: O(n) Space: O(n)

33. Minimum Height Trees

Approach: Topological trimming (peeling leaves).

public List<Integer> findMinHeightTrees(int n, int[][] edges) {

if(n==1) return Collections.singletonList(0);
List<Set<Integer>> g = new ArrayList<>();
for(int i=0;i<n;i++) g.add(new HashSet<>());
for(int[] e:edges){ g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
List<Integer> leaves=new ArrayList<>();
 for(int i=0;i<n;i++) if(g.get(i).size()==1) leaves.add(i);
int remaining = n;
while(remaining>2){
remaining -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for(int leaf: leaves){
int nei = g.get(leaf).iterator().next();
g.get(nei).remove(leaf);
if(g.get(nei).size()==1) newLeaves.add(nei);
}
leaves = newLeaves;
}
return leaves;
}

Time: O(n) Space: O(n)

34. Binary Tree Maximum Path Sum

Approach: DFS returning max gain, track global max.

int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private int dfs(TreeNode node){
if(node==null) return 0;
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, node.val + left + right);
return node.val + Math.max(left,right);
}

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

35. Count of Smaller Numbers After Self

Approach: Binary Indexed Tree (Fenwick) or merge sort with indices. (Use BIT)

public List<Integer> countSmaller(int[] nums) {

int n=nums.length;
int[] sorted = Arrays.copyOf(nums,n);
Arrays.sort(sorted);
Map<Integer,Integer> rank=new HashMap<>();
int r=1;
for(int v: sorted) if(!rank.containsKey(v)) rank.put(v, r++);
Fenwick bit = new Fenwick(r+1);
List<Integer> res = new ArrayList<>();
for(int i=n-1;i>=0;i--){
int rk = rank.get(nums[i]);
res.add(bit.query(rk-1));
bit.update(rk,1);
}
Collections.reverse(res);
 return res;
}
class Fenwick {
int[] f;
Fenwick(int n){ f=new int[n]; }
void update(int i,int delta){ for(;i<f.length;i+=i&-i) f[i]+=delta; }
int query(int i){ int s=0; for(;i>0;i-=i&-i) s+=f[i]; return s; }
}

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

36. Longest Consecutive Sequence

Approach: HashSet and expand from starts.

public int longestConsecutive(int[] nums) {

Set<Integer> s=new HashSet<>();
for(int n:nums) s.add(n);
int best=0;
for(int n:nums){
if(!s.contains(n-1)){
int cur=n,len=1;
while(s.contains(++cur)) len++;
best=Math.max(best,len);
}
}
return best;
}

Time: O(n) Space: O(n)

37. Subsets II (unique subsets with duplicates)

Approach: Sort and backtrack skipping duplicates.

public List<List<Integer>> subsetsWithDup(int[] nums) {

Arrays.sort(nums);
List<List<Integer>> res=new ArrayList<>();
backtrack(nums,0,new ArrayList<>(),res);
return res;
}
private void backtrack(int[] nums,int idx,List<Integer>
cur,List<List<Integer>> res){
res.add(new ArrayList<>(cur));
for(int i=idx;i<nums.length;i++){
if(i>idx && nums[i]==nums[i-1]) continue;
cur.add(nums[i]);
backtrack(nums,i+1,cur,res);
cur.remove(cur.size()-1);
}
}

Time: O(2^n) Space: O(n)

 38. Word Search (board)
Approach: Backtracking DFS with visited marking.

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,word,0,i,j)) return true;
return false;
}
private boolean dfs(char[][] b,String w,int idx,int i,int j){
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 c=b[i][j]; b[i][j]='#';
boolean found = dfs(b,w,idx+1,i+1,j) || dfs(b,w,idx+1,i-1,j) ||
dfs(b,w,idx+1,i,j+1) || dfs(b,w,idx+1,i,j-1);
b[i][j]=c;
return found;
}

Time: O(mn4^L) Space: O(L)

39. Letter Combinations of a Phone Number

Approach: Backtracking using digit-to-letters map.

public List<String> letterCombinations(String digits) {

List<String> res=new ArrayList<>();
if(digits.length()==0) return res;
String[] map = {"","",
"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
back(digits,0,new StringBuilder(),res,map);
return res;
}
private void back(String d,int idx,StringBuilder sb,List<String>
res,String[] map){
if(idx==d.length()){ res.add(sb.toString()); return; }
for(char c: map[d.charAt(idx)-'0'].toCharArray()){
sb.append(c);
back(d,idx+1,sb,res,map);
sb.deleteCharAt(sb.length()-1);
}
}

Time: O(4^L * L) Space: O(L)

40. Combination Sum (unique combos)

Approach: Backtracking with candidates sorted and reuse allowed.

public List<List<Integer>> combinationSum(int[] candidates, int target) {

List<List<Integer>> res=new ArrayList<>();
Arrays.sort(candidates);
back(candidates,0,target,new ArrayList<>(),res);
return res;
}
private void back(int[] c,int idx,int t,List<Integer>
cur,List<List<Integer>> res){
if(t==0){ res.add(new ArrayList<>(cur)); return; }
for(int i=idx;i<c.length && c[i]<=t;i++){
cur.add(c[i]);
back(c,i,t-c[i],cur,res);
cur.remove(cur.size()-1);
}
}

Time: Exponential Space: O(target/minCandidate)

41. Basic Calculator II ( + - * / )

Approach: Single pass with stack or tracking last number.

public int calculate(String s) {

if(s==null) return 0;
s = s.replaceAll(" ","") + "+";
int cur=0, last=0, res=0;
char op='+';
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(Character.isDigit(c)) cur = cur*10 + (c-'0');
else {
if(op=='+'){ res+=last; last=cur; }
else if(op=='-'){ res+=last; last=-cur; }
else if(op=='*'){ last = last * cur; }
else if(op=='/'){ last = last / cur; }
op = c; cur=0;
}
}
return res+last;
}

Time: O(n) Space: O(1) (ignoring string operations)

42. Binary Search Tree Iterator

Approach: Controlled inorder with stack.

class BSTIterator {
Deque<TreeNode> st = new ArrayDeque<>();
public BSTIterator(TreeNode root){
pushLeft(root);
}
private void pushLeft(TreeNode r){ while(r!=null){ st.push(r);
r=r.left; } }
public int next(){
TreeNode n=st.pop();
pushLeft(n.right);
return n.val;
}
public boolean hasNext(){ return !st.isEmpty(); }
}

Time: next amortized O(1) Space: O(h)

43. Find Kth Largest Element in an Array

Approach: Quickselect or min-heap. (Quickselect shown)

public int findKthLargest(int[] nums, int k) {

return quickSelect(nums, 0, nums.length-1, nums.length-k);
}
private int quickSelect(int[] a,int l,int r,int k){
if(l==r) return a[l];
int p = partition(a,l,r);
if(k==p) return a[k];
else if(k < p) return quickSelect(a,l,p-1,k);
else return quickSelect(a,p+1,r,k);
}
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){ swap(a,i,j); i++; }
}
swap(a,i,r);
return i;
}
private void swap(int[] a,int i,int j){ int t=a[i]; a[i]=a[j]; a[j]=t;}

Time: Average O(n) Space: O(1)

44. Maximal Rectangle (in binary matrix)

Approach: Treat each row as histogram and compute largest rectangle per row (stack).

public int maximalRectangle(char[][] matrix) {

if(matrix.length==0) return 0;
int m=matrix.length, n=matrix[0].length;
int[] h=new int[n];
int max=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++) h[j] = matrix[i][j]=='1' ? h[j]+1 : 0;
max = Math.max(max, largestRectangleArea(h));
}
return max;
}
private int largestRectangleArea(int[] h){
Deque<Integer> st=new ArrayDeque<>(); st.push(-1);
int max=0;
for(int i=0;i<h.length;i++){
while(st.peek()!=-1 && h[i] <= h[st.peek()]) max = Math.max(max,
h[st.pop()] * (i - st.peek() -1));
st.push(i);
}
while(st.peek()!=-1) max = Math.max(max, h[st.pop()] * (h.length -
st.peek() -1));
 return max;
}

Time: O(mn) Space: O(n)

45. Alien Dictionary (topological order of chars)

Approach: Build graph of precedence from adjacent words, topological sort, detect
cycle.

public String alienOrder(String[] words) {

Map<Character,Set<Character>> g=new HashMap<>();
Map<Character,Integer> indeg=new HashMap<>();
for(String w:words) for(char c:w.toCharArray()){ g.putIfAbsent(c,new
HashSet<>()); indeg.putIfAbsent(c,0); }
for(int i=0;i<words.length-1;i++){
String w1=words[i], w2=words[i+1];
int len = Math.min(w1.length(), w2.length()), j=0;
while(j<len && w1.charAt(j)==w2.charAt(j)) j++;
if(j<len){
char c1=w1.charAt(j), c2=w2.charAt(j);
if(!g.get(c1).contains(c2)){ g.get(c1).add(c2); indeg.put(c2,
indeg.get(c2)+1); }
} else if(w1.length() > w2.length()) return "";
}
Queue<Character> q=new LinkedList<>();
for(char c: indeg.keySet()) if(indeg.get(c)==0) q.offer(c);
StringBuilder sb=new StringBuilder();
while(!q.isEmpty()){
char c=q.poll(); sb.append(c);
for(char nei: g.get(c)){
indeg.put(nei, indeg.get(nei)-1);
if(indeg.get(nei)==0) q.offer(nei);
}
}
if(sb.length() != indeg.size()) return "";
return sb.toString();
}

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

46. Word Ladder II (all shortest sequences)

Approach: BFS to build graph of levels then backtrack from end to start (bidirectional
variant optional).
(Compact outline — implementation is long; here's a concise BFS + DFS
backtracking solution)

public List<List<String>> findLadders(String begin, String end,

List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
List<List<String>> res = new ArrayList<>();
if(!dict.contains(end)) return res;
Map<String,List<String>> tree = new HashMap<>();
Set<String> level = new HashSet<>(); level.add(begin);
 boolean found=false;
while(!level.isEmpty() && !found){
Set<String> next = new HashSet<>();
for(String s: level) dict.remove(s);
for(String s: level){
char[] arr=s.toCharArray();
for(int i=0;i<arr.length;i++){
char old = arr[i];
for(char c='a';c<='z';c++){
arr[i]=c; String ns = new String(arr);
if(!dict.contains(ns)) continue;
tree.computeIfAbsent(s, k-> new ArrayList<>()).add(ns);
if(ns.equals(end)) found=true;
next.add(ns);
}
arr[i]=old;
}
}
level = next;
}
if(found){
LinkedList<String> path=new LinkedList<>();
path.add(begin);
dfsBuild(begin, end, tree, path, res);
}
return res;
}
private void dfsBuild(String cur,String end, Map<String,List<String>> tree,
LinkedList<String> path, List<List<String>> res){
if(cur.equals(end)){ res.add(new ArrayList<>(path)); return; }
if(!tree.containsKey(cur)) return;
for(String nxt: tree.get(cur)){
path.add(nxt);
dfsBuild(nxt,end,tree,path,res);
path.removeLast();
}
}

Time: High — depends on branching; Space: O(N * L)

47. Find All Anagrams in a String

Approach: Sliding window frequency arrays.

public List<Integer> findAnagrams(String s, String p) {

List<Integer> res=new ArrayList<>();
if(s.length() < p.length()) return res;
int[] sCount=new int[26], pCount=new int[26];
for(int i=0;i<p.length();i++){ sCount[s.charAt(i)-'a']++;
pCount[p.charAt(i)-'a']++; }
if(Arrays.equals(sCount,pCount)) res.add(0);
for(int i=p.length(); i<s.length(); i++){
sCount[s.charAt(i)-'a']++;
sCount[s.charAt(i-p.length())-'a']--;
if(Arrays.equals(sCount,pCount)) res.add(i-p.length()+1);
}
return res;
}
Time: O(n*26) ~ O(n) Space: O(1)

48. Insert Interval

Approach: Add non-overlapping intervals, merge when overlapping.

public int[][] insert(int[][] intervals, int[] newInterval) {

List<int[]> res=new ArrayList<>();
int i=0;
while(i<intervals.length && intervals[i][1] < newInterval[0])
res.add(intervals[i++]);
while(i<intervals.length && intervals[i][0] <= newInterval[1]){
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
res.add(newInterval);
while(i<intervals.length) res.add(intervals[i++]);
return res.toArray(new int[res.size()][]);
}

Time: O(n) Space: O(n)

49. Binary Search Tree From Preorder

Approach: Reconstruct BST using bounds (index pointer).

int idx;
public TreeNode bstFromPreorder(int[] preorder) {
idx=0;
return helper(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode helper(int[] a, int lo, int hi){
if(idx==a.length) return null;
int val = a[idx];
if(val < lo || val > hi) return null;
idx++;
TreeNode root = new TreeNode(val);
root.left = helper(a, lo, val);
root.right = helper(a, val, hi);
return root;
}

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

50. Sliding Window Maximum

Approach: Deque storing indices of potential max in decreasing order.

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

if(nums==null||k<=0) return new int[0];
int n=nums.length; int[] res=new int[n-k+1];
Deque<Integer> dq = new ArrayDeque<>();
 for(int i=0;i<nums.length;i++){
while(!dq.isEmpty() && dq.peek() < i-k+1) dq.poll();
while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
dq.pollLast();
dq.offer(i);
if(i>=k-1) res[i-k+1] = nums[dq.peek()];
}
return res;
}

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

� About the Author

SYNTAX ERROR | Abhishek Rathor

Helping students crack their dream placements! �

Connect with me:

• � Instagram: @code.abhii07
• � YouTube: SYNTAX ERROR

� Youve Got This! All The Best! �

"Success is where preparation meets opportunity. You've prepared well - now go seize your
opportunity!"

Sure! Let’s continue adding more Infosys DSE-relevant medium-level LeetCode problems
with full Java solutions.