Asmi Jafar

I have one foot in my Brokenness and one foot in my Breakthrough.

gn

Remember why you started?! It was very hard to keep myself motivated to do all of it; still some percentage left, but yeah here we are 🥹

Q.175)Maximum Profit in Job Scheduling (Hard) 🔸 Weighted Job Scheduling 🔸 Pick non-overlapping jobs for max profit 🔸 Sort jobs by start time 🔸 Binary search next non-conflicting job 🔸 Memoize with DP: dp[i] = max(take, notTake) 🔸 Return dp[index] = Math.max(take, notTake)

Q.174) Palindrome Partitioning II 🔸 Min cuts to split s into palindromes 🔸 Try all k where s[i...k] is a palindrome 🔸 Use dp[i][j] to memoize subproblems: for(int k = i; k < j; k++) : if (isPalindrome(s, i, k)) 🔸int temp = 1 + partition(k + 1, j, s, dp); 🔸Return dp[i][j]=min

Q.173) Word Break Problem 🔸 String and dictionary of strings wordDict, return true if s can be segmented 🔸 boolean[] dp = new boolean[s.length()+1]; basecase: dp[0] = true; 🔸 Check all j < i : if(dp[j] && wordDict.contains(s.substring(j,i))){ dp[i] = true;

Q.172) Two Egg Drop MCM prob 🔸Drop from floor k, 2 outcomes:  - Egg breaks -> check below with 1 egg  - Egg survives -> check above with 2 eggs 🔸Take worst case (max), try all k:- for (int k=1; k<=floors; k++) (k-1,eggs-1,dp), (floors-k,eggs,dp) 🔸dp[f][e] = min attempts needed

Q.171) Min Cost to Cut a Stick DP 🔸 Interval DP strikes again! 🔸 Add 0 & n to cuts[], then sort 🔸 dp[i][j] = min cost to cut between cuts[i] & cuts[j] 🔸 Try all k between i & j 🔸dp[i][j] = min(dp[i][j], cuts[j] - cuts[i] + dp[i][k] + dp[k][j]) 🔸 Classic Gap Strategy

Q.170) Partition Equal Subset Sum 🔸Subset Sum DP Approach 🔸Goal: Check if array can be split into 2 subsets with equal sum 🔸Total sum must be even -Then solve: Subset Sum = totalSum/2 -t[i][j] = t[i-1][j] || t[i-1][j - a[i-1]] 🔸Returns true if subset with required sum exists

Q.169) Coin Change – Unbounded Knapsack 🔸Given coins[], find min coins to make amount 🔸dp[i][j] = min(dp[i-1][j], 1 + dp[i][j - coins[i-1]]) //taken 🔸dp[i][j] = dp[i-1][j] 🔸Base:  dp[i][0] = 0: 0 amount -> 0 coins  dp[0][j] = Integer.MAX_VALUE - 1: (impossible) 🔸TC: O(M*N)

Q.168)Minimum Path Sum 🔸From top-left to bottom-right in grid 🔸Only right/down moves allowed 🔸dp[i][j] = grid[i][j]+min(dp[i-1][j], dp[i][j-1]) 🔸Base: dp[i][j]=grid[0][0] - if(i>0): dp[i][0] = dp[i - 1][0]+grid[i][0] - if(j>0): dp[0][j] = dp[0][j - 1]+grid[0][j] 🔸TC:O(m×n)

Q.167) Matrix Chain Multiplication 🔸Minimize scalar multiplications 🔸Try all partitions k between i & j 🔸for(int k = i; k<= j-1; k++) : dp[i][j] = min(f(i,k) + f(k+1,j) + cost   cost = arr[i-1] * arr[k] * arr[j] 🔸Classic recursion + memoization 🔸TC: O(n³), SC:O(N^2+N)

Q.166) Max Sum of Increasing Subsequence 🔸Find increasing subsequence with max sum 🔸i=0;i->arr.length: dp[i] = arr[i] 🔸j=0;j<i : dp[i] = Math.max(dp[i], arr[i] + dp[j]); where j<i and arr[j]<arr[i] 🔸 ans = Math.max(ans, dp[i]); Return ans 🔸TC: O(n²), SC: O(n)

Q.165)Edit Distance 🔸Min operations to convert word1 to word2 🔸dp[i][j] = min edits to convert first i of word1 to first j of word2 🔸If match; dp[i][j] = dp[i-1][j-1] 🔸Else:  Replace-> dp[i-1][j-1]  Delete -> dp[i-1][j]  Insert -> dp[i][j-1]; Final Ans: dp[m][n] 🔸TC: O(m×n)

Q.164) 0/1 Knapsack DP prob 🔸 Max value with weight limit W 🔸 dp[i][j] -> max value using first i items with capacity j 🔸 If wt[i-1] ≤ j -> pick or skip 🔸 dp[i][j] = max(val + dp[i-1][j-wt], dp[i-1][j]) 🔸 Else -> skip; dp[i][j] = dp[i-1][j]; 🔸 TC: O(n×W), SC: O(n×W)

Q.163) Longest Common Subsequence (LCS) 🔸 Classic DP 🔸 Base if(i==0 || j==0) dp[i][j] = 0; 🔸 dp[i][j] = LCS of first i chars of text1 & first j of text2 🔸 If chars match -> 1 + dp[i-1][j-1] 🔸 Else -> max(dp[i-1][j], dp[i][j-1]) 🔸 TC: O(m × n), SC: O(m × n)

Q.162) Longest Increasing Subsequence (LIS) 🔸 DP approach, dp[n]; 🔸 Array.fills(dp,1) 🔸 For each i, check all j < i 🔸If nums[i] > nums[j] -> dp[i] = max(dp[i], dp[j]+1) 🔸 Track max length across dp[]; max = max(dp,len) 🔸 TC: O(n²), SC: O(n)

Q.161) Max Product Subarray (DP) 🔸 Handles negatives & zeroes 🔸 Traverse L -> R & R -> L  🔸prefix *= nums[i]  🔸suffix *= nums[n - 1 - i]  🔸reset prefix and suffix to 1 if zero 🔸 Track max of both ends each time 🔸 TC: O(n), SC: O(1)

Q.160) Floyd-Warshall Algorithm 🔸Solves All-Pairs Shortest Path 🔸Triple nested loops: for k, i, j dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 🔸Handles negative weights (not cycles) 🔸Input: Adjacency Matrix 🔸TC: O(V³), Great for dense graphs & small V (V≤500)

Q.159) Dijkstra’s Algorithm (Adj List + Min Heap) 🔸 Find shortest path from src to all nodes 🔸 Use PriorityQueue<[distance, node]> 🔸 Relax edges:  - If dist[v] > dist[u] + weight, update & push to pq 🔸 dist[] stores shortest dist from src 🔸 TC: O((V + E) log V), SC: O(V + E)

Q.158) Is Graph Bipartite? (DFS) 🔸Goal: 2-color the graph so no adjacent nodes share a color 🔸Track colors with int[] color 🔸DFS from unvisited nodes:  - Color current node  - Recurse with alternate color  - If neighbor has same color -> not bipartite 🔸TC: O(V + E), SC: O(V)