DP · Q14–Q58

Phases 3–9 · Questions 14–58

Saat patterns.
Paintalees sawaal.
Ek hi soch.

Phase 3 se 9 tak — Knapsack, Strings, Stocks, LIS, Partition DP, Squares, aur Advanced. Har phase ka ek core recurrence hai, aur us phase ke saare sawaal usi ke variations hain.

Har phase ki shuruaat me uska core recurrence card diya hai. Wo yaad kar lo, baaki sirf knobs ghumane hain. Neeche Phase 3 wala template — sabse pehle yahi.

Phase 3 master template f(i, target):
    // base cases — knob 3

    notTake = f(i-1, target)

    take = <neutral>
    if (arr[i] <= target)
        take = f(i-1, target - arr[i])

    return COMBINE(take, notTake)  // knob 1
    // return type — knob 2

Phase 3 · Q14–Q24

DP on Subsequences — Knapsack

Har element pe ek hi sawaal: loon ya na loon? Aur state me ek doosra parameter (target / capacity) track hota hai. Poore Phase 3 me sirf teen cheezein badalti hain — combine operator, return type, aur take pe index i rehta hai ya i-1 ho jaata hai.

Q14

Subset Sum equals Target

Coding Ninjas / GFG · poore Phase 3 ki neev

Combine||
Returnboolean
Basetarget==0 → true

Problem

Array arr[] (positive integers) aur ek target diya hai. Batao kya koi subset exist karta hai jiska sum exactly target ho.

arr = [1, 2, 3, 4], target = 4 → true — kyunki {4} ya {1,3} dono kaam karte hain.

Soch

Ye teesra sawaal-type hai jo Phase 1–2 me nahi aaya tha:

SawaalCombineKahan dekha
kitne tareeke (count)+Q2, Q8, Q9
minimum / maximummin / maxQ3, Q5, Q10–Q13
kya possible hai?||ab

Take / Not-Take, ab do parameter ke saath

f(i, target) = "index 0 se i tak ke elements se kya target ban sakta hai?"

  • Take — arr[i] le lo, bacha target = target - arr[i]. Sirf tab jab arr[i] <= target, warna target negative ho jayega.
  • Not Take — chhod do, target waisa ka waisa.

Kisi ek se true mil gaya toh kaam ho gaya → || lagao.

Free optimization

Java me || short-circuit karta hai. notTake ne true de diya toh take calculate hoga hi nahi.

Base cases

  • if (target == 0) return true; — kuch aur lene ki zaroorat nahi. Empty selection bhi valid hai.
  • if (i == 0) return arr[0] == target; — sirf ek element bacha.
Order matters

target == 0 ka check i == 0 se pehle aana chahiye. Ulta likha aur arr = [5], target = 0 aaya, toh arr[0] == 0 → false milega. Galat — empty subset ka sum 0 hota hai.

Code

1Pure RecursionO(2ⁿ)
static boolean f(int i, int target, int[] arr) {
    // ✅ target ban gaya
    if (target == 0) return true;
    // pehla element
    if (i == 0)      return arr[0] == target;

    boolean notTake = f(i - 1, target, arr);

    boolean take = false;
    if (arr[i] <= target) {          // tabhi jab fit ho
        take = f(i - 1, target - arr[i], arr);
    }

    return take || notTake;
}

// call: f(n - 1, target, arr)
2MemoizationO(n × target)
static boolean f(int i, int target, int[] arr, int[][] dp) {
    if (target == 0) return true;
    if (i == 0)      return arr[0] == target;

    if (dp[i][target] != -1) return dp[i][target] == 1;

    boolean notTake = f(i - 1, target, arr, dp);

    boolean take = false;
    if (arr[i] <= target) {
        take = f(i - 1, target - arr[i], arr, dp);
    }

    boolean ans = take || notTake;
    dp[i][target] = ans ? 1 : 0;
    return ans;
}

// driver
int[][] dp = new int[n][target + 1];
for (int[] row : dp) Arrays.fill(row, -1);
System.out.println(f(n - 1, target, arr, dp));
Boolean DP ka twist

boolean array me -1 nahi rakh sakte. Toh int array use karo: -1 = compute nahi hua, 0 = false, 1 = true.

Complexity dhyaan se

Ye O(n × target) hai — O(n²) nahi. Target bada hua (10⁹) toh ye DP kaam nahi karega. Isko pseudo-polynomial kehte hain. Subset Sum NP-complete hai; ye DP sirf isliye chalta hai kyunki target chhota hota hai.

3TabulationO(n × target)
static boolean f(int n, int target, int[] arr) {
    boolean[][] dp = new boolean[n][target + 1];

    // base 1: target 0 hamesha possible (kuch mat lo)
    for (int i = 0; i < n; i++) dp[i][0] = true;

    // base 2: sirf arr[0] available
    if (arr[0] <= target) dp[0][arr[0]] = true;

    for (int i = 1; i < n; i++) {
        for (int t = 1; t <= target; t++) {

            boolean notTake = dp[i - 1][t];

            boolean take = false;
            if (arr[i] <= t) take = dp[i - 1][t - arr[i]];

            dp[i][t] = take || notTake;
        }
    }

    return dp[n - 1][target];
}
4Space OptimizedSC O(target)
static boolean f(int n, int target, int[] arr) {
    boolean[] prev = new boolean[target + 1];

    prev[0] = true;
    if (arr[0] <= target) prev[arr[0]] = true;

    for (int i = 1; i < n; i++) {
        boolean[] curr = new boolean[target + 1];
        curr[0] = true;              // ⚠️ har row me!

        for (int t = 1; t <= target; t++) {
            boolean notTake = prev[t];

            boolean take = false;
            if (arr[i] <= t) take = prev[t - arr[i]];

            curr[t] = take || notTake;
        }

        prev = curr;
    }

    return prev[target];
}
Sabse common bug

curr[0] = true bhoolna. Har naya curr Java me false se initialize hota hai — set nahi kiya toh agli iteration me prev[0] false hoga aur poora answer galat.

Dry Run

arr = [1, 2, 3, 4], target = 4

i \ t01234
0  arr=1TTFFF
1  arr=2TTTTF
2  arr=3TTTTT
3  arr=4TTTTT

Row 2 pe kya hua (yahi turning point hai)

tnotTake = dp[1][t]take (3 ≤ t?)dp[2][t]
1T3 > 1 ❌T
2T3 > 2 ❌T
3Tdp[1][0] = TT
4Fdp[1][1] = T ✅T

t = 4 pe true take se aaya: arr[2] = 3 liya, aur dp[1][1] = true (matlab {1} se 1 ban gaya). Toh {1, 3} = 4.

Table ko padho

  • Column 0 poora T — target 0 hamesha possible.
  • Row 0 me sirf t=0,1 T — sirf {1} available tha.
  • T kabhi F nahi banta. Neeche jaate hue sirf T badhta hai, kyunki notTake hamesha pichli row copy karta hai. Ye monotonicity boolean DP ki pehchaan hai.

Khud try karo

  1. arr = [5], target = 0 → true aana chahiye. Tumhara code deta hai?
  2. Actual subset print karo ({1,3}), sirf true nahi. Backtrack: dp[i-1][t] true hai toh element nahi liya (i--), warna liya (t -= arr[i]; i--).
  3. arr me 0 ho toh kya hoga? arr = [0,1], target = 1. Abhi bas soch ke rakho — Q17 me ye bada issue banega.
Q15

Partition Equal Subset Sum

LeetCode 416 · reduction ka pehla example

Combine||
Returnboolean
Tricktarget = S/2

Problem

Array ko do subsets me baanto jinka sum barabar ho. Possible hai ya nahi?

nums = [1, 5, 11, 5] → true: {1,5,5} = 11 aur {11} = 11.

Soch

Naya DP nahi hai. Do observations se poora sawaal Q14 ban jaata hai.

Observation 1 — odd sum = turant false

Total sum S ko do barabar hisson me baantna hai, toh har hissa S/2. Aur S/2 integer tabhi jab S even ho.

if (totalSum % 2 != 0) return false;   // ek line me khatam

[1,2,3,5] ka sum 11 (odd) → seedha false, DP chalane ki zaroorat hi nahi.

Observation 2 — ek subset kaafi hai

Key insight

Agar ek subset mil gaya jiska sum S/2 hai, toh bache hue elements apne aap doosra subset ban jaate hain — aur unka sum bhi automatically S - S/2 = S/2. Dono track karne ki zaroorat hi nahi.

Toh sawaal ban gaya: "kya koi subset hai jiska sum S/2 hai?" — ye toh bilkul Q14 hai.

Code

→Wrapper — Q14 reuse6 lines
static boolean canPartition(int[] nums) {
    int totalSum = 0;
    for (int x : nums) totalSum += x;

    if (totalSum % 2 != 0) return false;      // Observation 1

    return subsetSum(nums, totalSum / 2);     // Observation 2
}
*In-place 1D — interview versionSC O(S/2)
static boolean canPartition(int[] nums) {
    int totalSum = 0;
    for (int x : nums) totalSum += x;
    if (totalSum % 2 != 0) return false;

    int target = totalSum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int num : nums) {
        for (int t = target; t >= num; t--) {   // ⚠️ ULTA loop
            dp[t] = dp[t] || dp[t - num];
        }
    }

    return dp[target];
}
Ulta loop kyun — sabse zaroori detail

Seedha (t = num se target) chalate toh dp[t - num] isi iteration me already update ho chuka hota — matlab num ko do baar use kar liya. 0/1 knapsack me har item ek hi baar.

Ulta chalane se dp[t - num] abhi bhi pichli iteration ki value rakhta hai. ✅

Aur yaad rakho: Q22 (Coin Change II) me hum jaan-boojhke seedha loop chalayenge — kyunki wahan item baar-baar lena allowed hai. Same code, ek loop ki direction, poora meaning badal jaata hai.

Dry Run

nums = [1, 5, 11, 5] → sum 22 (even) → target = 11

i \ t01234567891011
0 (1)TTFFFFFFFFFF
1 (5)TTFFFTTFFFFF
2 (11)TTFFFTTFFFFT
3 (5)TTFFFTTFFFTT

Row 1 padho: {1}=1, {5}=5, {1,5}=6 — bilkul sahi.

Row 2 pe t=11 true ho gaya, {11} se.

Row 3 pe dp[3][11] do raston se true hai:

  • notTake: dp[2][11] = T → {11}, baaki {1,5,5} = 11 ✅
  • take: dp[2][6] = T → nums[3]=5 + {1,5}=6 → {1,5,5} ✅

Pattern Tag

Problem reduction

Naya sawaal → known pattern me convert karo. Interview me 60% questions "disguised" hote hain.

SawaalKis pattern me convert hua
Q6 House Robber II2 × House Robber I
Q15 Equal PartitionSubset Sum, target = S/2
Delete and EarnHouse Robber, frequency array pe
Cherry Pickup ICherry Pickup II (jaana+aana = 2 robots)

Khud try karo

  1. [1, 2, 5] → sum 8 (even!), target 4. Par 1+2=3, 5, 1+5=6… 4 banta hi nahi → false. Even sum se partition guarantee nahi hota.
  2. Ulta loop wale version me seedha loop chala ke dekho. nums = [1,2], target = 2 pe test karo — answer galat aayega?
  3. Dono subsets print karo: {1,5,5} aur {11}.
Q16

Minimum Subset Sum Difference

GFG · "Partition a set into two subsets such that difference of sums is minimum"

Combine||
Returnboolean row
Tricklast row scan

Problem

Array ko do subsets me baanto. Dono ke sums ka absolute difference minimum karo. Wo minimum difference return karo.

arr = [1, 2, 3, 4] → 0 ({1,4} aur {2,3}, dono 5)

arr = [1, 6, 11, 5] → 1 ({1,5,5}… nahi — {1,6,5} = 12 aur {11} = 11, diff 1)

Soch

Q15 tak hum sirf ek cell (dp[n-1][target]) dekh rahe the. Yahan pehli baar poori last row kaam aayegi.

Do subsets ko ek variable me kaise laayein

Maan lo total sum S hai, aur ek subset ka sum s1. Toh doosre ka sum apne aap S - s1 hai.

difference = |s1 - (S - s1)| = |S - 2*s1|

Toh mujhe bas ek variable s1 ke saare possible values chahiye, aur har ek pe ye formula chala ke minimum le lena hai.

Aur wo "saare possible values" kahan se aayenge?

Yahi poora sawaal hai

Q14 ki dp table ki last row me har cell dp[n-1][s] batata hai ki sum s achievable hai ya nahi. Toh last row ko s = 0 se S tak scan karo, jahan-jahan true mile, wahan |S - 2*s| nikaalo, sabka minimum lo.

Ek subset-sum DP chalao target = S ke saath (poora sum, S/2 nahi — kyunki ab hum sab kuch achievable dekhna chahte hain), phir ek linear scan. Bas.

Chhoti optimization

Sirf s = 0 se S/2 tak scan karna kaafi hai. Kyunki har partition do baar count hota hai (s1 aur S-s1 dono achievable honge), aur half tak scan karne se saare unique partitions cover ho jaate hain.

Code

→Tabulation + scanO(n × S)
static int minSubsetSumDifference(int[] arr, int n) {
    int totalSum = 0;
    for (int x : arr) totalSum += x;

    // ---- Q14 ka subset-sum, target = totalSum ----
    boolean[][] dp = new boolean[n][totalSum + 1];

    for (int i = 0; i < n; i++) dp[i][0] = true;
    if (arr[0] <= totalSum) dp[0][arr[0]] = true;

    for (int i = 1; i < n; i++) {
        for (int t = 1; t <= totalSum; t++) {
            boolean notTake = dp[i - 1][t];
            boolean take = false;
            if (arr[i] <= t) take = dp[i - 1][t - arr[i]];
            dp[i][t] = take || notTake;
        }
    }

    // ---- last row scan ----
    int mini = Integer.MAX_VALUE;
    for (int s1 = 0; s1 <= totalSum / 2; s1++) {
        if (dp[n - 1][s1]) {
            int s2 = totalSum - s1;
            mini = Math.min(mini, Math.abs(s2 - s1));
        }
    }

    return mini;
}
*Space OptimizedSC O(S)
static int minSubsetSumDifference(int[] arr, int n) {
    int totalSum = 0;
    for (int x : arr) totalSum += x;

    boolean[] dp = new boolean[totalSum + 1];
    dp[0] = true;

    for (int num : arr) {
        for (int t = totalSum; t >= num; t--) {   // ulta = 0/1
            dp[t] = dp[t] || dp[t - num];
        }
    }

    int mini = Integer.MAX_VALUE;
    for (int s1 = 0; s1 <= totalSum / 2; s1++) {
        if (dp[s1]) mini = Math.min(mini, totalSum - 2 * s1);
    }

    return mini;
}
Ek chhota simplification

s1 <= totalSum/2 hone ki wajah se totalSum - 2*s1 hamesha ≥ 0 hai. Toh Math.abs() ki zaroorat hi nahi.

Dry Run

arr = [1, 6, 11, 5], totalSum = 23

Step 1 — achievable sums (last row)

Subset sums jo ban sakte hain: 0, 1, 5, 6, 7, 11, 12, 16, 17, 18, 22, 23

s0156711121617182223
dpTTTTTTTTTTTT
subset{}{1}{5}{6}{1,6}{11}{1,11}{11,5}{1,11,5}{1,6,11}{6,11,5}all

Step 2 — scan s1 = 0 to 11

s1achievable?s2 = 23 - s1diff = s2 - s1
0T2323
1T2221
5T1813
6T1711
7T169
11T121 ✅

Answer = 1 — partition: {11} = 11 aur {1, 6, 5} = 12.

Table ko padho

Scan me s1 jitna S/2 = 11.5 ke paas jaata hai, diff utna chhota hota jaata hai. Sabse paas wala achievable value 11 tha, isliye wahi jeeta. Agar arr = [1,2,3,4] hota (sum 10), toh s1 = 5 achievable hai → diff 0.

Complexity

ApproachTimeSpace
TabulationO(n × S)O(n × S)
Space OptimizedO(n × S)O(S)

Scan sirf O(S) hai — dominate nahi karta.

Khud try karo

  1. [1,2,3,4] → answer 0. Verify karo ki s1 = 5 achievable hai.
  2. Dono subsets print karo, sirf diff nahi. Q14 wala backtracking, best s1 se shuru karke.
  3. Agar array me negative numbers hon toh? Ye DP kyun toot jaata hai? (Hint: dp ke indices non-negative hote hain.)
Q17

Count Subsets with Sum K

Coding Ninjas / GFG · zeros wala classic trap

Combine+
Returnint (count)
Basezeros ka jhol

Problem

Array arr[] aur target k. Batao kitne subsets ka sum exactly k hai.

arr = [1, 2, 2, 3], k = 3 → 3

Kaunse? {1,2} (pehla 2), {1,2} (doosra 2), {3}. Dono {1,2} alag count hote hain kyunki index alag hain, value same hone se farak nahi padta.

Soch

Q14 ka bilkul same recursion. Sirf ek knob ghooma:

Q14 Subset SumQ17 Count Subsets
Sawaalpossible hai?kitne tareeke?
Combine||+
Returnbooleanint
Success petrue1
Failure pefalse0

Yaad karo Q8 (Unique Paths) me bhi yahi tha: return 1 = ek valid tareeka mila, return 0 = raasta bekaar. Wahi ab yahan.

Zeros ka trap — ye sabse important hai

Ab tak humne base case aise likha tha:

// ye zeros ke saath GALAT hai
if (target == 0) return 1;
if (i == 0)      return arr[0] == target ? 1 : 0;
Kyun galat hai

arr = [0, 0, 1], k = 1. Sahi answer 4 hai:

{1}, {0₁, 1}, {0₂, 1}, {0₁, 0₂, 1} — har zero ko lena ya na lena, dono valid choices hain, aur sum nahi badalta.

Par upar wala code target == 0 hote hi 1 return kar deta hai aur baaki zeros ki choices explore hi nahi karta. Answer 1 aayega. ❌

Sahi base case

target == 0 wala early-return hata do, aur poora kaam i == 0 pe karo:

if (i == 0) {
    if (target == 0 && arr[0] == 0) return 2;   // take AND notTake, dono se 0
    if (target == 0 || arr[0] == target) return 1;
    return 0;
}

Teen line ka matlab:

  • return 2 — target 0 chahiye aur arr[0] bhi 0 hai. Toh {} aur {0} — do alag subsets, dono ka sum 0.
  • return 1 — ya toh target 0 hai (empty subset lo) ya arr[0] exactly target hai. Ek tareeka.
  • return 0 — kuch nahi ban sakta.
Yaad rakhne wali line

Counting problems me early return se bacho. Recursion ko poora neeche tak jaane do, taaki har element ki take/notTake choice count ho. Boolean problems me early return safe tha (Q14) kyunki wahan true ek hi baar count hota hai.

Code

1Recursion + MemoizationO(n × k)
static int f(int i, int target, int[] arr, int[][] dp) {
    if (i == 0) {
        if (target == 0 && arr[0] == 0) return 2;
        if (target == 0 || arr[0] == target) return 1;
        return 0;
    }

    if (dp[i][target] != -1) return dp[i][target];

    int notTake = f(i - 1, target, arr, dp);

    int take = 0;
    if (arr[i] <= target) {
        take = f(i - 1, target - arr[i], arr, dp);
    }

    return dp[i][target] = take + notTake;     // COMBINE = +
}

// driver
int[][] dp = new int[n][k + 1];
for (int[] row : dp) Arrays.fill(row, -1);
System.out.println(f(n - 1, k, arr, dp));
2TabulationO(n × k)
static int f(int n, int k, int[] arr) {
    int[][] dp = new int[n][k + 1];

    // base: i == 0
    if (arr[0] == 0) dp[0][0] = 2;      // {} aur {0}
    else             dp[0][0] = 1;      // sirf {}

    if (arr[0] != 0 && arr[0] <= k) dp[0][arr[0]] = 1;

    for (int i = 1; i < n; i++) {
        for (int t = 0; t <= k; t++) {

            int notTake = dp[i - 1][t];

            int take = 0;
            if (arr[i] <= t) take = dp[i - 1][t - arr[i]];

            dp[i][t] = take + notTake;
        }
    }

    return dp[n - 1][k];
}
Do chhote traps

1. t ka loop 0 se shuru hai, 1 se nahi. Q14 me 1 se chal jaata tha kyunki column 0 pehle hi bhar diya tha. Yahan zeros ki wajah se dp[i][0] bhi compute hona chahiye.

2. arr[0] != 0 ka check zaroori hai, warna arr[0] = 0 hone pe dp[0][0] ki 2 wali value 1 se overwrite ho jayegi.

3Space OptimizedSC O(k)
static int f(int n, int k, int[] arr) {
    int[] prev = new int[k + 1];

    if (arr[0] == 0) prev[0] = 2; else prev[0] = 1;
    if (arr[0] != 0 && arr[0] <= k) prev[arr[0]] = 1;

    for (int i = 1; i < n; i++) {
        int[] curr = new int[k + 1];

        for (int t = 0; t <= k; t++) {
            int notTake = prev[t];
            int take = 0;
            if (arr[i] <= t) take = prev[t - arr[i]];
            curr[t] = take + notTake;
        }

        prev = curr;
    }

    return prev[k];
}

Dry Run

arr = [1, 2, 2, 3], k = 3

Base: arr[0] = 1 (non-zero) → dp[0][0] = 1, dp[0][1] = 1

i \ t0123
0  arr=11100
1  arr=21111
2  arr=21122
3  arr=31123

Cell by cell — row 2 (doosra 2)

tnotTake = dp[1][t]take (2 ≤ t?)dp[2][t]
01❌1
11❌1
21dp[1][0] = 12
31dp[1][1] = 12

Final cell — dp[3][3]

  • notTake = dp[2][3] = 2 → {1,2₁} aur {1,2₂}
  • take = dp[2][0] = 1 → {3}
  • Total = 3 ✅

Table ko padho

Column t=2 dekho: row 1 pe 1, row 2 pe 2. Jaise hi doosra 2 array me aaya, sum 2 banane ke tareeke double ho gaye. Yahi + operator ka kaam hai — || hota toh dono baar true hi rehta aur farak dikhta hi nahi.

Khud try karo

  1. arr = [0, 0, 1], k = 1 → answer 4. Purana (galat) base case laga ke dekho — kya 1 aata hai?
  2. arr = [0, 0, 0], k = 0 → answer 8 (har zero ki 2 choices, 2³). Verify karo.
  3. Bade arrays me count overflow ho sakta hai. LeetCode aksar mod 1e9+7 maangta hai — code me kahan-kahan % MOD lagega?
Q18

Count Partitions with Given Difference

Coding Ninjas / GFG · algebra + Q17

Combine+
Returnint (count)
Tricktarget = (S−D)/2

Problem

Array ko do subsets S1 aur S2 me baanto (har element exactly ek subset me) taaki sum(S1) - sum(S2) = D. Kitne tareeke hain?

arr = [5, 2, 6, 4], D = 3 → 1 — sirf ek partition kaam karta hai: S1 = {6,4} = 10 aur S2 = {5,2} = 7, diff 10 − 7 = 3 ✅

Soch — do equations, do unknowns

Pehle algebra, phir Q17. Diye hue hain:

S1 + S2 = totalSum     // dono milke poora array
S1 - S2 = D            // diya hua condition

Doosre ko pehle se ghatao:

2 * S2 = totalSum - D
S2 = (totalSum - D) / 2
Poora sawaal ek line me

Ab S2 ek fixed number hai. Toh sawaal ban gaya: "kitne subsets ka sum (totalSum - D)/2 hai?" — ye Q17 hai.

Aur dobara wahi observation jo Q15 me tha: ek subset chun liya, toh doosra apne aap ban gaya. Sirf ek count karo.

Do edge cases — dono zaroori

  • (totalSum - D) < 0 → return 0. Negative sum wala subset exist nahi karta.
  • (totalSum - D) % 2 != 0 → return 0. S2 integer hi nahi banega.
Interview me ye pehle bolna

Ye do checks bina DP chalaye answer de dete hain. Q15 ke totalSum % 2 != 0 wale check ka hi bada version hai.

Code

→Wrapper + Q17 reuseO(n × S)
static final int MOD = 1000000007;

static int countPartitions(int n, int D, int[] arr) {
    int totalSum = 0;
    for (int x : arr) totalSum += x;

    // edge cases
    if (totalSum - D < 0)          return 0;
    if ((totalSum - D) % 2 != 0)   return 0;

    int target = (totalSum - D) / 2;

    return countSubsets(n, target, arr);   // Q17 ka function
}

static int countSubsets(int n, int k, int[] arr) {
    int[] prev = new int[k + 1];

    if (arr[0] == 0) prev[0] = 2; else prev[0] = 1;
    if (arr[0] != 0 && arr[0] <= k) prev[arr[0]] = 1;

    for (int i = 1; i < n; i++) {
        int[] curr = new int[k + 1];

        for (int t = 0; t <= k; t++) {
            int notTake = prev[t];
            int take = 0;
            if (arr[i] <= t) take = prev[t - arr[i]];
            curr[t] = (take + notTake) % MOD;
        }

        prev = curr;
    }

    return prev[k];
}
Zeros yahan bhi zaroori hain

Q17 ka zero-handling base case yahan bina badle use karna hai. Is problem me arrays me zeros aksar hote hain aur test cases specifically unko target karte hain.

Dry Run

arr = [5, 2, 6, 4], D = 3

totalSum = 5+2+6+4 = 17

17 - 3 = 14, even ✅ → target = 7

Ab: kitne subsets ka sum 7 hai?

i \ t01234567
0 (5)10000100
1 (2)10100101
2 (6)10100111
3 (4)10101111

Row 1 pe kya hua

dp[1][7]: notTake = dp[0][7] = 0, take = dp[0][5] = 1 → total 1. Matlab {5, 2} = 7 ✅

Final answer

dp[3][7] = 1 → 1 tareeka

Verify: S2 = {5,2} = 7, toh S1 = {6,4} = 10. Diff = 10 - 7 = 3 ✅

Complexity

ApproachTimeSpace
MemoizationO(n × target)O(n × target) + O(n)
TabulationO(n × target)O(n × target)
Space OptimizedO(n × target)O(target)

Khud try karo

  1. D = 17 daalo (= totalSum). Answer? (target = 0 → sirf empty subset → 1.)
  2. D = 18 daalo. 17 - 18 = -1 < 0 → 0. Edge case ne bacha liya.
  3. D = 4 daalo. 17 - 4 = 13, odd → 0. Verify karo ki koi partition sach me diff 4 nahi de sakta. (Hint: S1 - S2 aur S1 + S2 ki parity hamesha same hoti hai.)
  4. Q21 (Target Sum) pehle khud try karo — wo bilkul yahi sawaal hai, sirf shabd badle hue.
Q19

0/1 Knapsack

Coding Ninjas / GFG · poore Phase 3 ka naam isi pe hai

Combinemax
Returnint (value)
Take pevalue[i] jodo

Problem

Ek chor ke paas W capacity ka bag hai. n items hain, har item ka wt[i] aur val[i]. Har item ya toh poora lo, ya bilkul mat lo (isliye "0/1"). Maximum value nikalo.

wt = [1, 2, 4, 5], val = [5, 4, 8, 6], W = 5 → 13

Kaise? Item 0 (wt 1, val 5) + item 2 (wt 4, val 8) = weight 5, value 13 ✅

Soch

Ab tak target "banana tha". Ab W "bachana hai". Structure bilkul same — bas naam badla.

f(i, W) = "item 0 se i tak, capacity W me maximum kitni value bhar sakta hoon"

  • Take — val[i] + f(i-1, W - wt[i]), sirf jab wt[i] <= W
  • Not Take — 0 + f(i-1, W)

Maximum chahiye → Math.max()

Naya element: value jodna

Q14–Q18 me "take" karne pe sirf target ghatta tha, kuch milta nahi tha. Yahan take karne pe val[i] milta bhi hai. Ye Q5 (House Robber) jaisa hai — wahan bhi nums[i] milta tha. Bas ab ek doosra parameter (W) bhi track ho raha hai.

Base case

if (i == 0) {
    if (wt[0] <= W) return val[0];   // fit hota hai, le lo
    return 0;                        // nahi fit, kuch nahi milega
}

Ek line me: return (wt[0] <= W) ? val[0] : 0;

Yahan W == 0 ka alag check kyun nahi

Kyunki base case khud handle kar leta hai: W = 0 hone pe wt[0] <= 0 false hoga (weights positive hain), toh 0 return ho jayega. Q14 me target == 0 ka alag check chahiye tha kyunki wahan wo success tha; yahan wo bas "kuch nahi mila" hai.

Code

1Pure RecursionO(2ⁿ)
static int f(int i, int W, int[] wt, int[] val) {
    if (i == 0) return (wt[0] <= W) ? val[0] : 0;

    int notTake = 0 + f(i - 1, W, wt, val);

    int take = Integer.MIN_VALUE;
    if (wt[i] <= W) {
        take = val[i] + f(i - 1, W - wt[i], wt, val);
    }

    return Math.max(take, notTake);
}

// call: f(n - 1, W, wt, val)
Invalid pe kya return karein

take ko Integer.MIN_VALUE se initialize kiya hai, 0 se nahi. Kyunki 0 ek valid answer ho sakta hai, aur hum chahte hain ki "item fit hi nahi hua" wala case max me kabhi na jeete. Q10 wala hi rule, ulta: min ke liye 1e9, max ke liye MIN_VALUE. (Yahan values non-negative hain toh 0 bhi chal jaata, par aadat sahi rakho.)

2MemoizationO(n × W)
static int f(int i, int W, int[] wt, int[] val, int[][] dp) {
    if (i == 0) return (wt[0] <= W) ? val[0] : 0;

    if (dp[i][W] != -1) return dp[i][W];

    int notTake = 0 + f(i - 1, W, wt, val, dp);

    int take = Integer.MIN_VALUE;
    if (wt[i] <= W) {
        take = val[i] + f(i - 1, W - wt[i], wt, val, dp);
    }

    return dp[i][W] = Math.max(take, notTake);
}

// driver
int[][] dp = new int[n][W + 1];
for (int[] row : dp) Arrays.fill(row, -1);
System.out.println(f(n - 1, W, wt, val, dp));
3TabulationO(n × W)
static int f(int n, int W, int[] wt, int[] val) {
    int[][] dp = new int[n][W + 1];

    // base: sirf item 0 available
    for (int c = wt[0]; c <= W; c++) {
        dp[0][c] = val[0];
    }

    for (int i = 1; i < n; i++) {
        for (int c = 0; c <= W; c++) {

            int notTake = 0 + dp[i - 1][c];

            int take = Integer.MIN_VALUE;
            if (wt[i] <= c) take = val[i] + dp[i - 1][c - wt[i]];

            dp[i][c] = Math.max(take, notTake);
        }
    }

    return dp[n - 1][W];
}

Base case ka loop wt[0] se shuru hota hai — usse chhoti capacity me item 0 fit hi nahi hota, aur Java me wo cells default 0 hi rehte hain. ✅

4Space Optimized — single arraySC O(W)
static int f(int n, int W, int[] wt, int[] val) {
    int[] dp = new int[W + 1];

    for (int c = wt[0]; c <= W; c++) dp[c] = val[0];

    for (int i = 1; i < n; i++) {
        for (int c = W; c >= 0; c--) {        // ⚠️ ULTA loop

            int notTake = dp[c];              // abhi bhi purani row

            int take = Integer.MIN_VALUE;
            if (wt[i] <= c) take = val[i] + dp[c - wt[i]];

            dp[c] = Math.max(take, notTake);
        }
    }

    return dp[W];
}
Ulta loop — wahi baat, teesri baar

dp[c - wt[i]] humesha chhota index hai. Ulta chalne se wo abhi tak update nahi hua — matlab pichli row ki value hai, jo humein chahiye. Seedha chalate toh item i do baar use ho jaata (aur wo Q23 Unbounded Knapsack ban jaata — jo actually ek alag sawaal hai, galti nahi 😄).

Dry Run

wt = [1, 2, 4, 5], val = [5, 4, 8, 6], W = 5

Base row: wt[0] = 1, toh c = 1 se aage sab 5.

i \ c012345
0  wt1 v5055555
1  wt2 v4055999
2  wt4 v80559913
3  wt5 v60559913

Row 1 — item (wt 2, val 4)

cnotTake = dp[0][c]take (2 ≤ c?)dp[1][c]
254 + dp[0][0] = 45
354 + dp[0][1] = 9 ✅9
554 + dp[0][3] = 9 ✅9

c = 2 pe interesting hai: item 1 lene se sirf 4 milta, par item 0 akela 5 deta hai. notTake jeeta.

Row 2 — item (wt 4, val 8) — yahan answer banta hai

dp[2][5]:

  • notTake = dp[1][5] = 9
  • take = 8 + dp[1][1] = 8 + 5 = 13 ✅
  • max(13, 9) = 13

Matlab item 2 (wt 4) liya, aur bachi hui 1 capacity me item 0 (wt 1, val 5) fit ho gaya. {item 0, item 2} → weight 5, value 13 ✅

Row 3 — item (wt 5, val 6)

dp[3][5]: notTake = 13, take = 6 + dp[2][0] = 6. max(13, 6) = 13. Bhaari item liya hi nahi — poori bag khaa jaata aur sirf 6 deta.

Table ko padho

Har row ka matlab: "item 0..i available hain". Neeche jaate hue values kabhi ghatti nahi — kyunki naya item milne se options sirf badhte hain, ghatte nahi. Ye monotonicity knapsack tables ki pehchaan hai (Q14 ki boolean monotonicity ka numeric version).

Complexity

ApproachTimeSpace
RecursionO(2ⁿ)O(n) stack
MemoizationO(n × W)O(n × W) + O(n)
TabulationO(n × W)O(n × W)
Space OptimizedO(n × W)O(W)

Khud try karo

  1. Kaunse items liye, wo print karo. Backtrack: dp[i][c] == dp[i-1][c] hai toh item i nahi liya; warna liya (c -= wt[i]).
  2. Single-array version me seedha loop chala ke dekho. wt=[1], val=[5], W=3 pe kya aata hai? (15 — item teen baar le liya!) Yahi Q23 ban jaata hai.
  3. Fractional Knapsack (GFG) — item ka tukda bhi le sakte ho. Ye DP nahi hai, greedy hai (value/weight ratio se sort). Socho ki 0/1 me greedy kyun fail hota hai.
Q20

Minimum Coins

LeetCode 322 · Coin Change I · pehla unbounded sawaal

Combinemin
Returnint (count)
Take pef(i, ...) — i same!

Problem

Coins ke denominations coins[] diye hain (infinite supply har coin ka). Amount T banane ke liye minimum kitne coins chahiye? Na ban sake toh -1.

coins = [1, 2, 5], T = 11 → 3 (5 + 5 + 1)

Soch — Unbounded ka janm

Ab tak har item ek hi baar le sakte the, isliye take karne pe f(i-1, ...) jaate the — "is item se kaam khatam, aage badho".

Yahan coin baar-baar le sakte ho. Toh take karne pe index wahi rehta hai:

notTake = 0 + f(i - 1, T)              // is coin ko chhod diya, ab kabhi nahi
take    = 1 + f(i,     T - coins[i])   // ⚠️ i, i-1 NAHI
Poore unbounded family ka ek line ka sach

Take pe i rakho, i-1 nahi. Bas. Q20, Q22, Q23, Q24 — chaaron isi ek badlaav pe khade hain. Baaki sab 0/1 jaisa hi hai.

take me 1 + kyun? Kyunki humein coins ki ginti minimize karni hai. Ek coin uthaya, ginti ek badhi. (Q19 me val[i] + tha kyunki wahan value maximize karni thi.)

Base case — yahan naya twist hai

if (i == 0) {
    if (T % coins[0] == 0) return T / coins[0];
    return (int) 1e9;                 // possible hi nahi
}

Sirf ek coin bacha. Agar T us coin se poora divide ho jaata hai, toh T / coins[0] coins lagenge. Warna ye raasta bekaar hai.

1e9 kyun, 0 nahi

Minimization me invalid ko bada banana hota hai (Q10 wali table). 0 return karte toh min usko turant chun leta aur answer 0 aa jaata. Aur Integer.MAX_VALUE mat use karna — uspe 1 + lagte hi overflow ho jayega.

Final answer par ek check

int ans = f(n - 1, T, coins, dp);
return (ans >= (int) 1e9) ? -1 : ans;

Agar answer abhi bhi 1e9 ke aaspaas hai, matlab koi valid combination mila hi nahi.

Code

1Pure Recursionexponential
static int f(int i, int T, int[] coins) {
    if (i == 0) {
        if (T % coins[0] == 0) return T / coins[0];
        return (int) 1e9;
    }

    int notTake = 0 + f(i - 1, T, coins);

    int take = (int) 1e9;
    if (coins[i] <= T) {
        take = 1 + f(i, T - coins[i], coins);   // i same!
    }

    return Math.min(take, notTake);
}
2MemoizationO(n × T)
static int coinChange(int[] coins, int T) {
    int n = coins.length;
    int[][] dp = new int[n][T + 1];
    for (int[] row : dp) Arrays.fill(row, -1);

    int ans = f(n - 1, T, coins, dp);
    return (ans >= (int) 1e9) ? -1 : ans;
}

static int f(int i, int T, int[] coins, int[][] dp) {
    if (i == 0) {
        if (T % coins[0] == 0) return T / coins[0];
        return (int) 1e9;
    }

    if (dp[i][T] != -1) return dp[i][T];

    int notTake = 0 + f(i - 1, T, coins, dp);

    int take = (int) 1e9;
    if (coins[i] <= T) take = 1 + f(i, T - coins[i], coins, dp);

    return dp[i][T] = Math.min(take, notTake);
}
Complexity kyun exponential nahi

Recursion tree me depth T / min(coins) tak ja sakti hai (ek hi coin baar-baar), toh dekhne me dar lagta hai. Par states sirf n × T hain, isliye memoization ke baad O(n × T). Har state ek hi baar compute hoti hai, chahe kitni baar bhi call ho.

3TabulationO(n × T)
static int f(int n, int T, int[] coins) {
    int[][] dp = new int[n][T + 1];

    // base: sirf coins[0]
    for (int t = 0; t <= T; t++) {
        if (t % coins[0] == 0) dp[0][t] = t / coins[0];
        else                   dp[0][t] = (int) 1e9;
    }

    for (int i = 1; i < n; i++) {
        for (int t = 0; t <= T; t++) {

            int notTake = 0 + dp[i - 1][t];

            int take = (int) 1e9;
            if (coins[i] <= t) take = 1 + dp[i][t - coins[i]];  // dp[i], dp[i-1] nahi

            dp[i][t] = Math.min(take, notTake);
        }
    }

    int ans = dp[n - 1][T];
    return (ans >= (int) 1e9) ? -1 : ans;
}
Tabulation me unbounded kaise dikhta hai

take me dp[i][t - coins[i]] hai — usi row ka pichla cell, pichli row ka nahi. Aur kyunki t ka loop seedha (badhta hua) chal raha hai, wo cell isi iteration me already bhar chuka hai — matlab coin dobara use ho sakta hai. Exactly wahi cheez jo Q15/Q19 me hum ulta loop laga ke rok rahe the. 🔁

4Space OptimizedSC O(T)
static int f(int n, int T, int[] coins) {
    int[] prev = new int[T + 1];

    for (int t = 0; t <= T; t++) {
        prev[t] = (t % coins[0] == 0) ? t / coins[0] : (int) 1e9;
    }

    for (int i = 1; i < n; i++) {
        int[] curr = new int[T + 1];

        for (int t = 0; t <= T; t++) {
            int notTake = prev[t];

            int take = (int) 1e9;
            if (coins[i] <= t) take = 1 + curr[t - coins[i]];  // curr!

            curr[t] = Math.min(take, notTake);
        }

        prev = curr;
    }

    int ans = prev[T];
    return (ans >= (int) 1e9) ? -1 : ans;
}
Yahan sabse zyada log fasste hain

take me curr[t - coins[i]] hai, prev[...] nahi. Ye unbounded ki pehchaan hai. 0/1 me hamesha prev se lete the (Q14, Q17, Q19). Ek akshar ka farak, poora sawaal alag.

Dry Run

coins = [1, 2, 5], T = 11

Base row (coins[0] = 1): har t ke liye t/1 = t coins.

i \ t01234567891011
0 (1)01234567891011
1 (2)011223344556
2 (5)011221223323

Row 1 — coin 2 add hua

tnotTake = dp[0][t]take = 1 + dp[1][t-2]dp[1][t]
221 + dp[1][0] = 1 ✅1
441 + dp[1][2] = 1+1 = 2 ✅2
551 + dp[1][3] = 1+2 = 3 ✅3

t = 4 pe dekho: dp[1][2] use hua — jo abhi isi row me bharaa tha. Matlab coin 2 do baar lag gaya (2 + 2 = 4). Unbounded live in action. 🔁

Row 2 — coin 5 add hua — final

dp[2][11]:

  • notTake = dp[1][11] = 6 (2×5 + 1 — chhe coins)
  • take = 1 + dp[2][6] = 1 + 2 = 3 ✅
  • min(3, 6) = 3

Aur dp[2][6] = 2 khud 1 + dp[2][1] = 1 + 1 se aaya. Toh poora chain: 5 + 5 + 1 → 3 coins ✅

Table ko padho

Row 2 me t = 5 pe value 3 se girkar 1 ho gayi, aur t = 10 pe 5 se 2. Jahan-jahan naya coin exactly fit hota hai, wahan bada jump aata hai. Row 1 ki values kabhi badhti nahi row 0 se — naya coin milne se options sirf sudhar sakte hain.

Complexity

ApproachTimeSpace
MemoizationO(n × T)O(n × T) + O(T) stack
TabulationO(n × T)O(n × T)
Space OptimizedO(n × T)O(T)

Stack depth O(T) hai (na ki O(n)), kyunki ek hi coin baar-baar lene se recursion gehri jaati hai.

Khud try karo

  1. coins = [2], T = 3 → -1. Base case 1e9 return karta hai, aur final check use -1 banata hai. Trace karo.
  2. Kaunse coins liye wo print karo: [5, 5, 1].
  3. Greedy try karo: hamesha sabse bada coin lo. coins = [1, 3, 4], T = 6 pe greedy 4+1+1 = 3 coins deta hai, par sahi answer 3+3 = 2 hai. Isiliye DP chahiye.
Q21

Target Sum

LeetCode 494 · Q18 hi hai, naye kapde me

Combine+
Returnint (count)
Trick= Q18, D = target

Problem

Array nums[] hai. Har element ke aage + ya - lagana hai. Kitne tareeke hain jisse final sum target ban jaye?

nums = [1, 1, 1, 1, 1], target = 3 → 5

Ek 1 ko minus, baaki chaar ko plus: -1+1+1+1+1 = 3. Kaunsa wala minus hoga — 5 choices. ✅

Soch — ek reframe, aur sawaal khatam

Har element do dabbo me ja raha hai: plus wala dabba aur minus wala dabba. Toh actually ye ek partition hi hai!

  • S1 = plus wale elements ka sum
  • S2 = minus wale elements ka sum

Condition: S1 - S2 = target

Ye bilkul Q18 hai

"Count partitions where sum(S1) - sum(S2) = D" — wahi sawaal, bas D ka naam yahan target hai. Naya code likhna hi nahi hai.

Toh wahi algebra:

S1 + S2 = totalSum
S1 - S2 = target
------------------------
S2 = (totalSum - target) / 2

Aur count karo kitne subsets ka sum S2 hai.

Edge cases — Q18 wale hi

  • totalSum - target < 0 → 0
  • (totalSum - target) % 2 != 0 → 0
LeetCode ka trap

LeetCode 494 me target negative ho sakta hai. Tab totalSum - target aur bada ho jaata hai — aur agar wo totalSum se bada nikla, toh koi subset nahi banega aur DP khud 0 de dega. Par safety ke liye Math.abs(target) > totalSum ka check bhi laga sakte ho.

Code

→Wrapper — Q18 / Q17 reuseO(n × S)
static int findTargetSumWays(int[] nums, int target) {
    int totalSum = 0;
    for (int x : nums) totalSum += x;

    if (totalSum - target < 0)        return 0;
    if ((totalSum - target) % 2 != 0) return 0;

    int s2 = (totalSum - target) / 2;

    return countSubsets(nums.length, s2, nums);   // Q17 ka function
}

static int countSubsets(int n, int k, int[] arr) {
    int[] prev = new int[k + 1];

    if (arr[0] == 0) prev[0] = 2; else prev[0] = 1;
    if (arr[0] != 0 && arr[0] <= k) prev[arr[0]] = 1;

    for (int i = 1; i < n; i++) {
        int[] curr = new int[k + 1];

        for (int t = 0; t <= k; t++) {
            int notTake = prev[t];
            int take = 0;
            if (arr[i] <= t) take = prev[t - arr[i]];
            curr[t] = take + notTake;
        }

        prev = curr;
    }

    return prev[k];
}
Zeros yahan bhi

LeetCode 494 ke constraints me nums[i] 0 ho sakta hai. Q17 ka zero-handling base case bina badle rakho, warna kai test cases fail honge.

Dry Run

nums = [1, 1, 1, 1, 1], target = 3

totalSum = 5. 5 - 3 = 2, even ✅ → s2 = 1

Ab: kitne subsets ka sum 1 hai? Paanch 1s me se koi ek chuno → 5 tareeke.

i \ t01
011
112
213
314
415

Har row me t = 1 ki value ek badh rahi hai: notTake (pichli row) + take (dp[i-1][0] = 1). Naya 1 milne se ek naya tareeka.

Verify karo

s2 = 1 matlab minus wale dabbe me sum 1 — ek akela 1. Baaki chaar plus me.

S1 = 4, S2 = 1 → 4 - 1 = 3 ✅ Bilkul target.

Pattern Tag

Teen sawaal, ek code

Q17, Q18, aur Q21 — teeno ka core countSubsets() ek hi hai. Sirf wrapper ka algebra badalta hai. Interview me agar ye reduction turant dikh jaye, toh 15 minute ka sawaal 3 minute me khatam.

SawaalKya poochhaTarget kya banta hai
Q17subsets with sum kk (seedha)
Q18partitions with diff D(S − D) / 2
Q21+/− signs for target(S − target) / 2

Khud try karo

  1. nums = [1], target = 1 → 1. Aur target = 2? (1 - 2 = -1 < 0 → 0.)
  2. nums = [1,0], target = 1 → answer 2 (+1+0 aur +1-0). Zero-handling base case bina ye 1 dega. Test karo.
  3. Doosri algebra try karo: S1 = (totalSum + target) / 2 nikaal ke S1 count karo. Same answer aayega? (Haan — symmetric hai.)
Q22

Coin Change II

LeetCode 518 · unbounded + counting

Combine+
Returnint (count)
Take pef(i, ...) — i same

Problem

Coins ke denominations diye hain (infinite supply). Amount T banane ke kitne tareeke hain?

coins = [1, 2, 5], T = 5 → 4

5 · 2+2+1 · 2+1+1+1 · 1+1+1+1+1

Order matter nahi karta

2+2+1 aur 1+2+2 ek hi tareeka hai — combination, permutation nahi. Aur DP ka structure ye automatically handle karta hai, kyunki hum coins ko index order me process karte hain (coin 0 ke saare decisions, phir coin 1 ke, ...). Ek hi multiset do baar ginne ka mauka hi nahi milta.

Soch

Do knobs ek saath ghoom rahe hain, dono pehle dekh chuke ho:

Q20 Min CoinsQ22 Coin Change II
Sawaalminimum kitnekitne tareeke
Combinemin+
Take pe1 + (coin ginti)kuch nahi jodo
Indexf(i, ...)f(i, ...) — same
notTake = f(i - 1, T)
take    = f(i,     T - coins[i])    // i same (unbounded), aur kuch jodna nahi

return take + notTake               // COMBINE = +

Base case

if (i == 0) {
    return (T % coins[0] == 0) ? 1 : 0;
}

Sirf ek coin bacha. Agar T us se divide ho jaata hai, toh exactly ek tareeka hai (utne saare coins lo). Warna zero tareeke.

Q20 se compare karo

Q20 me yahi base case T / coins[0] return karta tha — kitne coins. Yahan 1 return karta hai — kitne tareeke. Ek hi condition, do alag matlab. Yahi knob 2 (return type) hai.

Code

1MemoizationO(n × T)
static int f(int i, int T, int[] coins, long[][] dp) {
    if (i == 0) return (T % coins[0] == 0) ? 1 : 0;

    if (dp[i][T] != -1) return (int) dp[i][T];

    int notTake = f(i - 1, T, coins, dp);

    int take = 0;
    if (coins[i] <= T) {
        take = f(i, T - coins[i], coins, dp);    // i same
    }

    dp[i][T] = take + notTake;
    return (int) dp[i][T];
}

// driver
long[][] dp = new long[n][T + 1];
for (long[] row : dp) Arrays.fill(row, -1);
System.out.println(f(n - 1, T, coins, dp));
2TabulationO(n × T)
static long f(int n, int T, int[] coins) {
    long[][] dp = new long[n][T + 1];

    // base: sirf coins[0]
    for (int t = 0; t <= T; t++) {
        dp[0][t] = (t % coins[0] == 0) ? 1 : 0;
    }

    for (int i = 1; i < n; i++) {
        for (int t = 0; t <= T; t++) {

            long notTake = dp[i - 1][t];

            long take = 0;
            if (coins[i] <= t) take = dp[i][t - coins[i]];   // dp[i]!

            dp[i][t] = take + notTake;
        }
    }

    return dp[n - 1][T];
}
3Space Optimized — single arraySC O(T)
static long f(int n, int T, int[] coins) {
    long[] dp = new long[T + 1];
    dp[0] = 1;                            // amount 0: ek tareeka (kuch mat lo)

    for (int coin : coins) {
        for (int t = coin; t <= T; t++) { // ⚠️ SEEDHA loop
            dp[t] += dp[t - coin];
        }
    }

    return dp[T];
}
Ye chaar line poore Phase 3 ka nichod hai

Q15 me humne ulta loop chalaya tha taaki item dobara use na ho. Yahan seedha chala rahe hain taaki item dobara use ho sake.

dp[t - coin] seedhe loop me isi iteration me already update ho chuka hota hai — matlab wahi coin phir se count ho gaya. Bilkul wahi jo unbounded me chahiye.

0/1 knapsack → ulta loop. Unbounded → seedha loop. Ek line ka farak, do alag problem families.

Dry Run

coins = [1, 2, 5], T = 5

Base row (coins[0] = 1): har amount ek hi tareeke se banega (saare 1s) → sab 1.

i \ t012345
0 (1)111111
1 (2)112233
2 (5)112234

Row 1 — coin 2 add hua

tnotTake = dp[0][t]take = dp[1][t-2]dp[1][t]Kya matlab
21dp[1][0] = 12{1,1} · {2}
31dp[1][1] = 12{1,1,1} · {2,1}
41dp[1][2] = 23{1×4} · {2,1,1} · {2,2}
51dp[1][3] = 23{1×5} · {2,1,1,1} · {2,2,1}

t = 4 pe dp[1][2] use hua — jo isi row me abhi bhara tha aur khud me coin 2 shaamil karta hai. Isliye {2,2} count ho gaya. Unbounded. 🔁

Row 2 — coin 5, final

dp[2][5] = notTake dp[1][5] = 3 + take dp[2][0] = 1 = 4 ✅

Wo teen: {1×5}, {2,1,1,1}, {2,2,1}. Aur chautha: {5}. ✅

Table ko padho

dp[i][0] = 1 har row me — amount 0 banane ka hamesha exactly ek tareeka hai: kuch mat lo. Yahi wo dp[0] = 1 hai jo single-array version me seed karte hain. Aur values kabhi ghatti nahi — naya coin sirf naye tareeke jodta hai.

Complexity

ApproachTimeSpace
MemoizationO(n × T)O(n × T) + O(T) stack
TabulationO(n × T)O(n × T)
Space OptimizedO(n × T)O(T)

long use kiya hai kyunki counts tezi se badhte hain aur int overflow ho sakta hai.

Khud try karo

  1. Single-array version me loops swap karke dekho — bahar t, andar coin. Answer 8 aayega (5 ke liye), 4 nahi. Kyunki ab {2,1,2} aur {2,2,1} alag count ho rahe hain — ye permutations gin raha hai. Yahi LeetCode 377 (Combination Sum IV) hai! 🤯
  2. coins = [2], T = 3 → 0. Base case trace karo.
  3. Q15 ka in-place code aur Q22 ka in-place code side-by-side rakho. Sirf loop ki direction aur || vs += ka farak hai. Ye do file ek saath dekhna sabse bada "aha" moment hai.
Q23

Unbounded Knapsack

Coding Ninjas / GFG · Q19 + unbounded

Combinemax
Returnint (value)
Take pef(i, ...) — i same

Problem

Bilkul Q19 wala knapsack, bas har item ka infinite stock hai. Ek item jitni baar chaaho utni baar le sakte ho (jab tak capacity hai).

wt = [2, 4, 6], val = [5, 11, 13], W = 10 → 27

Kaise? Item 1 (wt 4, val 11) do baar + item 0 (wt 2, val 5) ek baar = weight 4+4+2 = 10, value 11+11+5 = 27 ✅

Soch

Q19 se exactly ek akshar ka farak:

// Q19 (0/1)
take = val[i] + f(i - 1, W - wt[i]);

// Q23 (unbounded)
take = val[i] + f(i,     W - wt[i]);   // i-1 hataya

Bas. Baaki poora code same.

Base case — yahan naya hai

if (i == 0) {
    return (W / wt[0]) * val[0];
}
Integer division ka kamaal

Sirf item 0 bacha, aur uska infinite stock hai. Toh jitne fit ho sakte hain utne bhar do: W / wt[0] copies, har ek val[0] ki.

Q19 me ye (wt[0] <= W) ? val[0] : 0 tha — sirf ek copy. Yahan W/wt[0] copies. Aur agar wt[0] > W ho toh integer division khud 0 de deta hai — alag check ki zaroorat nahi. 👌

Code

1MemoizationO(n × W)
static int f(int i, int W, int[] wt, int[] val, int[][] dp) {
    if (i == 0) return (W / wt[0]) * val[0];

    if (dp[i][W] != -1) return dp[i][W];

    int notTake = 0 + f(i - 1, W, wt, val, dp);

    int take = Integer.MIN_VALUE;
    if (wt[i] <= W) {
        take = val[i] + f(i, W - wt[i], wt, val, dp);   // i same
    }

    return dp[i][W] = Math.max(take, notTake);
}
2TabulationO(n × W)
static int f(int n, int W, int[] wt, int[] val) {
    int[][] dp = new int[n][W + 1];

    for (int c = 0; c <= W; c++) {
        dp[0][c] = (c / wt[0]) * val[0];
    }

    for (int i = 1; i < n; i++) {
        for (int c = 0; c <= W; c++) {

            int notTake = 0 + dp[i - 1][c];

            int take = Integer.MIN_VALUE;
            if (wt[i] <= c) take = val[i] + dp[i][c - wt[i]];   // dp[i]

            dp[i][c] = Math.max(take, notTake);
        }
    }

    return dp[n - 1][W];
}
3Space Optimized — single arraySC O(W)
static int f(int n, int W, int[] wt, int[] val) {
    int[] dp = new int[W + 1];

    for (int c = 0; c <= W; c++) dp[c] = (c / wt[0]) * val[0];

    for (int i = 1; i < n; i++) {
        for (int c = 0; c <= W; c++) {     // ⚠️ SEEDHA loop

            int notTake = dp[c];

            int take = Integer.MIN_VALUE;
            if (wt[i] <= c) take = val[i] + dp[c - wt[i]];

            dp[c] = Math.max(take, notTake);
        }
    }

    return dp[W];
}
Q19 vs Q23 — side by side

Dono ka single-array code bilkul identical hai, sirf c ka loop ulta/seedha hai. Ye do code ek saath dekhna Phase 3 ka sabse valuable 30 second hai.

Dry Run

wt = [2, 4, 6], val = [5, 11, 13], W = 10

Base row (wt[0]=2, val[0]=5): dp[0][c] = (c/2) * 5

i \ c012345678910
0  wt2 v5005510101515202025
1  wt4 v11005511111616222227
2  wt6 v13005511111616222227

Row 1 — item (wt 4, val 11)

cnotTake = dp[0][c]take = 11 + dp[1][c-4]dp[1][c]
41011 + dp[1][0] = 11 ✅11
82011 + dp[1][4] = 11+11 = 22 ✅22
102511 + dp[1][6] = 11+16 = 27 ✅27

c = 8 pe dp[1][4] use hua — jisme item 1 already ek baar hai. Toh item 1 do baar lag gaya. Yahi unbounded hai. 🔁

c = 10 pe: 11 + dp[1][6], aur dp[1][6] = 16 khud 11 + dp[1][2] = 11 + 5 se aaya. Chain: item1 + item1 + item0 = 11 + 11 + 5 = 27 ✅

Row 2 — item (wt 6, val 13)

dp[2][10]: notTake = 27, take = 13 + dp[2][4] = 13 + 11 = 24. max(27, 24) = 27. Bhaari item liya hi nahi — ratio kharab hai (13/6 ≈ 2.17 vs 11/4 = 2.75).

Par greedy phir bhi galat hai

Ratio dekh ke lagta hai "sabse acha ratio wala item bharte jao". Yahan wo kaam kar gaya, par hamesha nahi karta — kyunki bacha hua space waste ho sakta hai. Example: wt=[5,4], val=[10,7], W=8. Ratio se item 0 (2.0) behtar hai, par {0} = 10 aur {1,1} = 14. DP hi sahi jawaab deta hai.

Khud try karo

  1. Q19 aur Q23 ka single-array code likh ke sirf loop direction badlo, aur same input pe dono chalao. wt=[1], val=[5], W=3: 0/1 se 5, unbounded se 15.
  2. Kaunse items kitni baar liye, wo print karo: item1 × 2, item0 × 1.
  3. Q20 (Min Coins) aur Q23 me kya common hai? (Dono unbounded. Bas min vs max, aur 1 + vs val[i] +.)
Q24

Rod Cutting

GFG · Phase 3 ka aakhri — aur ye Q23 hi hai

Combinemax
Returnint (value)
Trickwt = length

Problem

N length ka ek rod hai. price[] array diya hai jahan price[i] = length (i+1) ke tukde ki keemat. Rod ko tukdon me kaato taaki total keemat maximum ho.

price = [2, 5, 7, 8, 10], N = 5 → 12

Kaise? Length 2 ka tukda (5) + length 2 ka tukda (5) + length 1 ka tukda (2) = 5+5+2 = 12 ✅ (Poora rod ek saath bechte toh sirf 10 milta.)

Soch — naam badla, sawaal wahi

Ek line ka mapping

Ye Unbounded Knapsack hai. Bas:

  • weight = tukde ki length = i + 1
  • value = price[i]
  • capacity = N (rod ki poori length)

Aur "unbounded" kyun? Kyunki ek hi length ke tukde kitne bhi kaat sakte ho — length 2 ke do tukde, teen tukde, jitne fit ho jaayein.

Toh recursion wahi Q23 wala:

notTake = 0 + f(i - 1, N)
take    = price[i] + f(i, N - (i + 1))    // i same, length = i+1

return max(take, notTake)

Base case

if (i == 0) {
    return N * price[0];    // length-1 ke tukde, N tukde bante hain
}

Sirf length-1 wale tukde available hain. Rod length N hai, toh exactly N tukde banenge. Q23 ka (W / wt[0]) * val[0] yahan (N / 1) * price[0] = N * price[0] ban gaya. ✅

Code

1MemoizationO(N²)
static int f(int i, int N, int[] price, int[][] dp) {
    if (i == 0) return N * price[0];

    if (dp[i][N] != -1) return dp[i][N];

    int notTake = 0 + f(i - 1, N, price, dp);

    int take = Integer.MIN_VALUE;
    int rodLength = i + 1;
    if (rodLength <= N) {
        take = price[i] + f(i, N - rodLength, price, dp);   // i same
    }

    return dp[i][N] = Math.max(take, notTake);
}

// driver: n = price.length (= N)
int[][] dp = new int[n][N + 1];
for (int[] row : dp) Arrays.fill(row, -1);
System.out.println(f(n - 1, N, price, dp));
2TabulationO(N²)
static int f(int n, int[] price) {
    int N = n;
    int[][] dp = new int[n][N + 1];

    for (int len = 0; len <= N; len++) {
        dp[0][len] = len * price[0];
    }

    for (int i = 1; i < n; i++) {
        for (int len = 0; len <= N; len++) {

            int notTake = 0 + dp[i - 1][len];

            int take = Integer.MIN_VALUE;
            int rodLength = i + 1;
            if (rodLength <= len) take = price[i] + dp[i][len - rodLength];

            dp[i][len] = Math.max(take, notTake);
        }
    }

    return dp[n - 1][N];
}
3Space OptimizedSC O(N)
static int f(int n, int[] price) {
    int N = n;
    int[] dp = new int[N + 1];

    for (int len = 0; len <= N; len++) dp[len] = len * price[0];

    for (int i = 1; i < n; i++) {
        for (int len = 0; len <= N; len++) {    // SEEDHA (unbounded)

            int notTake = dp[len];

            int take = Integer.MIN_VALUE;
            int rodLength = i + 1;
            if (rodLength <= len) take = price[i] + dp[len - rodLength];

            dp[len] = Math.max(take, notTake);
        }
    }

    return dp[N];
}

Dry Run

price = [2, 5, 7, 8, 10], N = 5

Base row (price[0] = 2, length 1): dp[0][len] = len * 2

i \ len012345
0  len1 ₹20246810
1  len2 ₹502571012
2  len3 ₹702571012
3  len4 ₹802571012
4  len5 ₹1002571012

Row 1 — length-2 tukde available hue

lennotTake = dp[0][len]take = 5 + dp[1][len−2]dp[1][len]
245 + dp[1][0] = 5 ✅5
365 + dp[1][1] = 5+2 = 7 ✅7
485 + dp[1][2] = 5+5 = 10 ✅10
5105 + dp[1][3] = 5+7 = 12 ✅12

len = 4 pe dp[1][2] = 5 use hua — jisme ek length-2 tukda already hai. Toh do length-2 tukde. Unbounded. 🔁

len = 5 pe: 5 + dp[1][3], aur dp[1][3] = 7 khud 5 + 2 se aaya. Chain: 2 + 2 + 1 lengths → 5 + 5 + 2 = ₹12 ✅

Rows 2, 3, 4 — kuch nahi badla

Length 3 (₹7), 4 (₹8), 5 (₹10) — teeno ka per-unit rate length-2 (₹2.5/unit) se kam hai. Toh DP unko kabhi chunta hi nahi. Table bilkul freeze ho gayi.

Ye acchi sanity check hai: agar tumhari table aakhri rows me badal rahi hai jabki wo items clearly kharab hain, toh take ke index me bug hai.

Complexity

ApproachTimeSpace
MemoizationO(N²)O(N²) + O(N) stack
TabulationO(N²)O(N²)
Space OptimizedO(N²)O(N)

n = N hai (price array ki length = rod length), isliye O(n × W) yahan O(N²) ban jaata hai.

Khud try karo

  1. Kaunse tukde kaate, wo print karo: [2, 2, 1].
  2. price = [3, 5, 8, 9, 10], N = 5 pe chalao. Ab length-1 ka rate ₹3/unit hai — sabse acha. Answer 15 aana chahiye (paanch length-1 tukde).
  3. Q23 ka code lo aur wt[i] = i + 1 bhar ke Q24 chalao. Bilkul same answer aana chahiye — kyunki ye ek hi sawaal hai.

Phase 4 · Q25–Q34

DP on Strings

Do strings, do pointers. Har step pe ek hi sawaal: aakhri characters match kar rahe hain ya nahi? Match hua toh dono pointer peeche; nahi hua toh ek-ek karke dono possibilities try karo. Poora Phase 4 isi ek if-else pe khada hai.

Phase 4 core recurrence f(i, j):
    // i = s1 ka index, j = s2 ka index

    if (s1[i] == s2[j])
        return MATCH_VALUE + f(i-1, j-1)

    return COMBINE( f(i-1, j), f(i, j-1) )
    // base: i < 0 || j < 0 → string khatam
Q25

Longest Common Subsequence

LeetCode 1143 · Phase 4 ki neev — agle 9 sawaal isi pe khade hain

Statei, j
Match pe1 + f(i-1, j-1)
No matchmax(↓, →)

Problem

Do strings s1 aur s2 diye hain. Sabse lambi common subsequence ki length nikalo.

Subsequence = characters ka order same rahe, par beech ke characters chhod sakte ho. (Substring me continuous hona zaroori hai — wo Q27 me.)

s1 = "abcde", s2 = "ace" → 3 ("ace")

Soch — do index kyun chahiye

Phase 3 me state tha (index, target). Yahan do alag strings hain, aur dono me alag-alag jagah pe khade ho sakte ho. Toh state = do index.

f(i, j) = "s1[0..i] aur s2[0..j] ki LCS length"

Har step pe do case

Case 1 — s1[i] == s2[j]

Ye character zaroor LCS me hoga. Toh 1 gino aur dono pointer ek-ek peeche kar do.

return 1 + f(i - 1, j - 1);
Yahan "notTake" kyun nahi socha

Agar dono characters same hain, toh unko match karke chhodna kabhi behtar nahi ho sakta. Skip karoge toh answer sirf barabar ya kam hoga, zyada kabhi nahi. Isliye yahan koi choice hi nahi — seedha match kar lo. Ye ek greedy step hai jo DP ke andar safe hai.

Case 2 — s1[i] != s2[j]

Ab dono ko ek saath match nahi kar sakte. Toh ek-ek karke chhodo aur best lo:

return Math.max( f(i - 1, j),    // s1 ka character chhoda
                 f(i, j - 1) );  // s2 ka character chhoda

Dono ko ek saath chhodne ki zaroorat nahi — wo case in dono ke andar already cover ho jaata hai.

Base case

if (i < 0 || j < 0) return 0;

Koi ek string khatam ho gayi → aage common kuch nahi mil sakta.

Shifted Index — tabulation ka sabse zaroori trick

Problem

Recursion me base case i < 0 hai — matlab dp[-1][...]. Par arrays me negative index hota hi nahi. Java crash kar dega.

Solution: poori table ko ek se right shift kar do.

RecursionTabulation
ii + 1
i = -1 (khatam)i = 0 (row of zeros)
dp[n-1][m-1] = answerdp[n][m] = answer
table size n × mtable size (n+1) × (m+1)

Ab pehli row aur pehla column poore zeros hain — wahi humara "string khatam" wala base case hai, aur Java me arrays default 0 se bhare hi hote hain. Free base case. 👌

Ye trick poore Phase 4 me lagegi

Har string DP problem me shifted index use hoga. Ek baar samajh gaye toh Q26 se Q34 tak mechanical hai. Bas yaad rakhna: table me i ka matlab hai "string ka pehla i characters", aur character access karte waqt s1.charAt(i - 1) likhna padega.

Code

1Pure RecursionO(2^(n+m))
static int f(int i, int j, String s1, String s2) {
    if (i < 0 || j < 0) return 0;

    if (s1.charAt(i) == s2.charAt(j)) {
        return 1 + f(i - 1, j - 1, s1, s2);
    }

    return Math.max(f(i - 1, j, s1, s2),
                    f(i, j - 1, s1, s2));
}

// call: f(n - 1, m - 1, s1, s2)
2MemoizationO(n × m)
static int f(int i, int j, String s1, String s2, int[][] dp) {
    if (i < 0 || j < 0) return 0;

    if (dp[i][j] != -1) return dp[i][j];

    if (s1.charAt(i) == s2.charAt(j)) {
        return dp[i][j] = 1 + f(i - 1, j - 1, s1, s2, dp);
    }

    return dp[i][j] = Math.max(f(i - 1, j, s1, s2, dp),
                               f(i, j - 1, s1, s2, dp));
}

// driver
int[][] dp = new int[n][m];
for (int[] row : dp) Arrays.fill(row, -1);
System.out.println(f(n - 1, m - 1, s1, s2, dp));
3Tabulation — shifted indexO(n × m)
static int lcs(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    int[][] dp = new int[n + 1][m + 1];   // ⚠️ +1 dono me

    // base case free hai: row 0 aur column 0 already 0 hain

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            // ⚠️ charAt me -1
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][m];
}
4Space OptimizedSC O(m)
static int lcs(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    int[] prev = new int[m + 1];

    for (int i = 1; i <= n; i++) {
        int[] curr = new int[m + 1];

        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                curr[j] = 1 + prev[j - 1];        // diagonal
            } else {
                curr[j] = Math.max(prev[j],       // up
                                   curr[j - 1]);  // left
            }
        }

        prev = curr;
    }

    return prev[m];
}
Grid DP wali mapping wapas

Q8 me jo mapping seekhi thi, wahi yahan bhi: dp[i-1][j-1] → prev[j-1] (diagonal), dp[i-1][j] → prev[j] (up), dp[i][j-1] → curr[j-1] (left). Phase 2 ka gyaan yahan bina badle kaam aa raha hai.

Dry Run

s1 = "abcde" (n=5), s2 = "ace" (m=3)

 ∅ace
∅0000
a0111
b0111
c0122
d0122
e0123

Cell by cell — kuch important wale

Cells1 chars2 charMatch?CalculationValue
dp[1][1]aa✅1 + dp[0][0] = 1+01
dp[2][1]ba❌max(dp[1][1], dp[2][0]) = max(1,0)1
dp[3][2]cc✅1 + dp[2][1] = 1+12
dp[4][3]de❌max(dp[3][3], dp[4][2]) = max(2,2)2
dp[5][3]ee✅1 + dp[4][2] = 1+23

Table ko padho

  • Match wale cells hamesha diagonal se value lete hain aur +1 karte hain. Table me dekho: (a,a), (c,c), (e,e) — teen diagonal jumps, teen ki LCS.
  • No-match cells apne upar ya left se value copy karte hain — kuch naya add nahi hota.
  • Values kabhi ghatti nahi, na neeche jaate hue na right jaate hue. Aur adjacent cells me farak 0 ya 1 hi ho sakta hai — ek character se zyada ka jump possible hi nahi.

Complexity

ApproachTimeSpace
RecursionO(2^(n+m))O(n+m) stack
MemoizationO(n × m)O(n × m) + O(n+m)
TabulationO(n × m)O(n × m)
Space OptimizedO(n × m)O(m)

prev ke liye chhoti string chuno — O(min(n,m)) space. Interview me ye mention karna.

Khud try karo

  1. s1 = "abc", s2 = "xyz" → 0. Table poori zeros se bharegi.
  2. s1 = s2 = "abcde" → 5. Poori diagonal bharegi.
  3. Space-optimized me curr[j-1] ki jagah galti se prev[j-1] likh do — kaunsa case tootega? (No-match wala. Aur answer chhota aayega.)
Q26

Print the LCS

GFG · backtracking on the dp table

InputQ25 ki dp table
Directiondp[n][m] → upar
TimeO(n + m)

Problem

Sirf LCS ki length nahi, actual string print karo.

s1 = "abcde", s2 = "ace" → "ace"

Soch — naya DP nahi, table padhna hai

Q25 ki table pehle se hi poora answer rakhti hai. Bas usko ulta chalna hai — dp[n][m] se shuru karke dp[0][0] tak.

Har cell pe ek hi sawaal: "ye value kahan se aayi thi?"

ConditionMatlabKya karo
s1[i-1] == s2[j-1]ye character LCS me haicharacter add karo, i--, j--
dp[i-1][j] > dp[i][j-1]upar se aayi thii--
warnaleft se aayi thij--
Ulta kyun chalte hain

Kyunki dp[n][m] hi wo cell hai jisme poora answer hai. Aage se peeche chalne se hum us exact raste pe chalte hain jisse ye value bani thi. Aur isliye string ulti banti hai — end me reverse karna padta hai (ya StringBuilder me aage se bharo).

Code

1DP table + backtrackO(n×m) + O(n+m)
static String printLCS(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    // ---- Step 1: Q25 wali table bana lo ----
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // ---- Step 2: peeche se chalo ----
    StringBuilder sb = new StringBuilder();

    int i = n, j = m;
    while (i > 0 && j > 0) {

        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            sb.append(s1.charAt(i - 1));   // LCS ka hissa
            i--; j--;                       // diagonal
        }
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;                            // upar se aaya
        }
        else {
            j--;                            // left se aaya
        }
    }

    return sb.reverse().toString();         // ulta bana tha
}
Space optimization yahan nahi hoti

Backtracking ke liye poori table chahiye, sirf ek row se kaam nahi chalega. Ye ek general rule hai: "path print karna hai" = poori dp table rakho. Q3, Q10, Q11 me bhi yahi baat thi.

Dry Run

Q25 wali table (s1 = "abcde", s2 = "ace"). i = 5, j = 3 se shuru.

Stepi, js1[i-1]s2[j-1]Match?Actionsb
15, 3ee✅add 'e', i→4, j→2"e"
24, 2dc❌dp[3][2]=2 > dp[4][1]=1 → i→3"e"
33, 2cc✅add 'c', i→2, j→1"ec"
42, 1ba❌dp[1][1]=1, dp[2][0]=0 → i→1"ec"
51, 1aa✅add 'a', i→0, j→0"eca"
60, 0loop khatam (i == 0)"eca"

sb.reverse() → "ace" ✅

Path ko table pe dekho

Backtrack ne exactly teen diagonal jumps liye — (5,3), (3,2), (1,1). Aur wahi teen cells the jinme Q25 ki dry run me match hua tha. Table ke andar chhupa hua path ab dikh gaya.

Khud try karo

  1. Tie hone pe (dp[i-1][j] == dp[i][j-1]) code j-- chunta hai. i-- kar do — kya LCS badal jaayegi? (Length wahi rahegi, par kaunsi LCS mili wo badal sakti hai, agar multiple LCS hain.)
  2. s1 = "abcbdab", s2 = "bdcaba" — yahan teen alag LCS hain length 4 ki. Kaunsi milti hai?
  3. Saari LCS print karne ka code likho (recursion + set). Bahut zyada ho sakti hain, isliye chhoti strings pe test karna.
Q27

Longest Common Substring

GFG · ek shabd badla, poora recurrence badal gaya

Match pe1 + dp[i-1][j-1]
No match0 — reset!
Answermax of ALL cells

Problem

Sabse lambi common substring ki length. Substring = continuous characters, gap allowed nahi.

s1 = "abcjklp", s2 = "acjkp" → 3 ("cjk")

LCS hoti toh "acjkp" = 5 aati. Par continuous nahi hai, isliye substring me nahi chalega.

Soch — do bade badlaav

1 · No-match pe reset karo

Yahi poora sawaal hai

LCS me mismatch pe hum max(up, left) lete the — matlab "purana progress bacha ke rakho, aage dekho".

Substring me mismatch ka matlab hai chain toot gayi. Purana progress ab bekaar hai. Toh dp[i][j] = 0.

2 · Answer last cell me nahi hota

LCS me answer dp[n][m] tha. Yahan nahi — kyunki dp[i][j] ab matlab rakhta hai "i aur j pe khatam hone wali common substring ki length".

Sabse lambi substring kahin beech me khatam ho sakti hai. Toh poori table ka maximum track karo.

// LCS (Q25)
if (match) dp[i][j] = 1 + dp[i-1][j-1];
else       dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
answer = dp[n][m];

// Longest Common Substring (Q27)
if (match) dp[i][j] = 1 + dp[i-1][j-1];
else       dp[i][j] = 0;                    // ⚠️ reset
answer = max over ALL cells;                // ⚠️ scan
Recursion kyun nahi likhte

Is problem me recursion natural nahi baithti, kyunki "yahan khatam hone wali chain" wala matlab top-down me express karna ganda ho jaata hai. Ye un chhote se problems me se hai jahan seedha tabulation likhna hi sahi hai. Interview me bhi yahi expected hai.

Code

1TabulationO(n × m)
static int longestCommonSubstring(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    int[][] dp = new int[n + 1][m + 1];
    int ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
                ans = Math.max(ans, dp[i][j]);   // har cell pe check
            } else {
                dp[i][j] = 0;                     // chain toot gayi
            }
        }
    }

    return ans;
}
2Space OptimizedSC O(m)
static int longestCommonSubstring(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    int[] prev = new int[m + 1];
    int ans = 0;

    for (int i = 1; i <= n; i++) {
        int[] curr = new int[m + 1];

        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                curr[j] = 1 + prev[j - 1];
                ans = Math.max(ans, curr[j]);
            }
            // else: curr[j] already 0 (fresh array)
        }

        prev = curr;
    }

    return ans;
}
Yahan space optimization aur bhi saaf hai

No-match pe kuch likhna hi nahi — curr ek fresh array hai jo Java me 0 se bhare hue aata hai. Reset apne aap ho jaata hai. Aur sirf prev[j-1] (diagonal) chahiye, curr[j-1] kabhi nahi — isliye order ki tension bhi nahi.

Dry Run

s1 = "abcjklp", s2 = "acjkp"

 ∅acjkp
∅000000
a010000
b000000
c001000
j000200
k000030
l000000
p000001

Diagonal chain ko dekho

CellcharsMatch?ValueChain
dp[3][2]c, c✅1 + dp[2][1] = 1+0 = 1"c"
dp[4][3]j, j✅1 + dp[3][2] = 1+1 = 2"cj"
dp[5][4]k, k✅1 + dp[4][3] = 1+2 = 3"cjk"
dp[6][5]l, p❌0 — resettoot gayi
dp[7][5]p, p✅1 + dp[6][4] = 1+0 = 1"p" (nayi chain)

Answer = 3 ✅ — aur wo dp[7][5] pe nahi, dp[5][4] pe mila. Isiliye poori table scan karni padti hai.

Table ko padho

LCS ki table bhari hui dikhti hai (values phailti hain). Substring ki table khaali dikhti hai, sirf chhote-chhote diagonal streaks ke saath. Har streak ek common substring hai. Sabse lambi streak = answer. Ye visual farak dono problems ko yaad rakhne ka sabse aasan tareeka hai.

Khud try karo

  1. Actual substring print karo, sirf length nahi. Hint: max value ka cell (i, j) yaad rakho, phir s1.substring(i - ans, i).
  2. s1 = "abcd", s2 = "abcd" → 4. Poori diagonal 1,2,3,4 bharegi.
  3. Q25 ka code lo aur sirf else wali line badal do. Dono answers same input pe compare karo — ek line ka farak kitna bada hai, wo mehsoos hoga.
Q28

Longest Palindromic Subsequence

LeetCode 516 · ek line ka reduction

ReductionLCS(s, reverse(s))
Naya codezero lines
TimeO(n²)

Problem

String s ki sabse lambi palindromic subsequence ki length.

s = "bbbab" → 4 ("bbbb")

s = "cbbd" → 2 ("bb")

Soch — palindrome ka matlab kya hai

Palindrome wo hota hai jo ulta likhne pe bhi wahi rehta hai.

Toh agar s ki koi subsequence palindrome hai, toh wo reverse(s) me bhi subsequence hogi — kyunki palindrome ulta karne pe badalta hi nahi.

Poora sawaal ek line me

LPS(s) = LCS(s, reverse(s))

Kyunki jo cheez dono me common subsequence hai aur ek doosre ka reverse hai — wo palindrome hi ho sakti hai.

Ek chhota sa doubt: kya LCS koi non-palindrome de sakta hai?

Ye sawaal thoda subtle hai. Formal proof lamba hai, par intuition ye hai: s aur reverse(s) me common subsequence banane ka matlab hai ki characters ka wahi order dono taraf se padha ja sakta hai — jo palindrome ki definition hi hai. Interview me itna bolna kaafi hai; formal proof shayad hi maanga jaaye.

Code

→Q25 reuseO(n²) / SC O(n)
static int longestPalindromeSubseq(String s) {
    String rev = new StringBuilder(s).reverse().toString();

    return lcs(s, rev);        // Q25 ka function, jaisa ka waisa
}

static int lcs(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    int[] prev = new int[m + 1];

    for (int i = 1; i <= n; i++) {
        int[] curr = new int[m + 1];

        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
                curr[j] = 1 + prev[j - 1];
            else
                curr[j] = Math.max(prev[j], curr[j - 1]);
        }

        prev = curr;
    }

    return prev[m];
}

Dry Run

s = "bbbab", rev = "babbb"

 ∅babbb
∅000000
b011111
b011222
b011233
a012233
b012334

Answer = dp[5][5] = 4 ✅ → "bbbb"

Verify karo

s = "bbbab" me b chaar baar hai (index 0,1,2,4). Un chaaron ko lo → "bbbb" — palindrome ✅. a ko shaamil karte toh "bbabb"… par s me a ke baad sirf ek b hai, toh wo subsequence banti hi nahi. LCS ne sahi pakda.

Doosra tareeka bhi hai

Interval DP se bhi hota hai: f(i, j) = "s[i..j] ki LPS". Match pe 2 + f(i+1, j-1), warna max(f(i+1, j), f(i, j-1)). Complexity wahi O(n²). Par LCS reduction likhna 3 line ka kaam hai, aur Q29–Q31 me bhi kaam aata hai — isliye yahi seekho.

Khud try karo

  1. s = "abcde" → 1 (koi bhi single character palindrome hai).
  2. Actual palindrome print karo — Q26 ka backtracking laga do.
  3. Interval DP wala version khud likho (f(i,j) wala). Dono ke answers match hone chahiye.
Q29

Minimum Insertions to Make Palindrome

LeetCode 1312 · Q28 se ek subtraction

Formulan − LPS(s)
Naya codezero lines
TimeO(n²)

Problem

String s me kahin bhi characters insert kar sakte ho. Minimum kitne insertions se s palindrome ban jaayegi?

s = "abcaa" → 2

s = "mbadm" → 2 ("mdbabdm" ya "mbdadbm")

Soch — ulta karke socho

Seedha sochne me confusion hoti hai: "kahan-kahan insert karun?" Isliye ulta socho.

Key insight

String ka jo hissa already palindrome hai, usko chhedne ki zaroorat nahi. Baaki har character ke liye ek mirror partner insert karna padega.

Sabse bada "already palindrome" hissa = LPS (Q28).

Toh: answer = n - LPS(s)

Har wo character jo LPS me nahi hai, uska jodidaar insert karna padega — exactly ek insertion per character.

Code

→Q28 reuseO(n²) / SC O(n)
static int minInsertions(String s) {
    int n = s.length();

    String rev = new StringBuilder(s).reverse().toString();
    int lps = lcs(s, rev);          // Q28 = Q25 pe reverse

    return n - lps;
}

Dry Run

s = "mbadm", n = 5

rev = "mdabm"

LCS("mbadm", "mdabm") = 3 → "mbm" ya "mam" ya "mdm"

answer = 5 - 3 = 2 ✅

Verify karo — kaunse 2 insertions

LPS = "mbm" (indices 0, 1, 4). Bache hue: a (index 2), d (index 3).

Dono ke mirror insert karo:

StepStringPalindrome?
originalm b a d m❌
+ 'd'm b d a d m❌
+ 'a'm b d a d b m✅

Ruko — "mbdadbm" me maine ek b bhi add kar diya, toh 3 insertions ho gaye. Sahi answer 2 hai, toh alag jagah insert karna hoga: "mbadabm"? Ye bhi palindrome nahi.

Sahi: LPS "mam" lo (indices 0, 2, 4). Bache: b, d. Result: "mbdadbm" — hmm ye 7 characters hai, matlab 2 insertions ✅ (5 → 7). Aur ye palindrome hai: m-b-d-a-d-b-m ✅

Sabak

Formula bharosemand hai, par kahan insert karna hai wo formula nahi batata. Interview me answer n - LPS hi maanga jaata hai; actual string banane ke liye Q31 (Shortest Common Supersequence) ka backtracking chahiye hoga.

Khud try karo

  1. s = "abcd" → LPS = 1, answer 3. ("abcdcba" banana padega.)
  2. s = "aaa" → LPS = 3, answer 0. Already palindrome.
  3. Minimum deletions to make palindrome — wo bhi n - LPS hi hai! Socho kyun. (Hint: LPS ke bahar wale characters ya toh insert karo ya delete karo — ginti same.)
Q30

Minimum Insertions & Deletions to Convert A to B

GFG · LCS ka teesra reduction

Deletionsn − LCS
Insertionsm − LCS
Totaln + m − 2·LCS

Problem

String s1 ko s2 banana hai. Sirf do operations allowed: insert aur delete (replace nahi!). Minimum operations?

s1 = "abcd", s2 = "anc" → 3

Soch

Dono strings me jo common hai, usko chhedne ki zaroorat hi nahi. Wo LCS hai.

StepKya karoKitne operations
1s1 se wo sab delete karo jo LCS me nahi hain − LCS
2ab sirf LCS bachi — usme wo sab insert karo jo s2 me haim − LCS
total = (n - LCS) + (m - LCS)
      = n + m - 2 * LCS
Beech ka padav

LCS wo "sabse chhota common ground" hai jahan dono strings mil sakti hain. Pehle wahan pahuncho (deletions), phir wahan se target tak jao (insertions). Ye do-step wali soch kai string problems me kaam aati hai.

Code

→Q25 reuseO(n × m)
static int minOperations(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    int lcsLen = lcs(s1, s2);          // Q25

    int deletions  = n - lcsLen;
    int insertions = m - lcsLen;

    return deletions + insertions;     // = n + m - 2*lcsLen
}

Dry Run

s1 = "abcd" (n=4), s2 = "anc" (m=3)

 ∅anc
∅0000
a0111
b0111
c0112
d0112

LCS = 2 ("ac")

  • Deletions = 4 - 2 = 2 → b aur d hataao
  • Insertions = 3 - 2 = 1 → n daalo
  • Total = 3 ✅

Step by step verify

OperationString
starta b c d
delete 'b'a c d
delete 'd'a c  ← ye LCS hai
insert 'n'a n c ✅

Khud try karo

  1. s1 = "abc", s2 = "abc" → LCS = 3, answer 0.
  2. s1 = "abc", s2 = "xyz" → LCS = 0, answer 6 (3 delete + 3 insert).
  3. Agar replace bhi allowed ho toh? Wo Q33 (Edit Distance) hai — aur answer aksar chhota aayega. Dono compare karke dekho.
Q31

Shortest Common Supersequence

LeetCode 1092 · LCS + backtracking

Lengthn + m − LCS
Stringbacktrack, 3 cases
TimeO(n × m)

Problem

Sabse chhoti string dhoondo jisme s1 aur s2 dono subsequence ke roop me maujood hon.

s1 = "brute", s2 = "groot" → "bgrouote" (length 8)

Soch — length pehle

Seedha jodo toh n + m characters lagenge. Par jo characters common hain, unhe ek hi baar likhna kaafi hai.

Sabse zyada kitne share kar sakte hain? LCS jitne.

length = n + m - LCS(s1, s2)

"brute" (5) + "groot" (5), LCS = "rot" (2? ya 3?) — dry run me exact nikalenge.

String banana — teen cases wala backtrack

Q26 me backtrack karke sirf match wale characters uthaate the. Yahan saare uthane hain — bas common wale ek hi baar.

ConditionKya karoKyun
s1[i-1] == s2[j-1]character add, i--, j--common — ek baar likho
dp[i-1][j] > dp[i][j-1]s1[i-1] add, i--sirf s1 ka, isko bhi chahiye
warnas2[j-1] add, j--sirf s2 ka
Loop khatam hone ke baad ruko mat

Jab i ya j me se ek 0 ho jaata hai, doosri string ke bache hue characters abhi bhi add karne hain. Do extra while loops lagenge. Ye bhoolna sabse common bug hai — answer chhota aa jaata hai.

Code

→DP table + 3-case backtrackO(n × m)
static String shortestCommonSupersequence(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    // ---- Step 1: LCS table ----
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // ---- Step 2: backtrack, saare characters ----
    StringBuilder sb = new StringBuilder();
    int i = n, j = m;

    while (i > 0 && j > 0) {

        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            sb.append(s1.charAt(i - 1));    // common: ek baar
            i--; j--;
        }
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            sb.append(s1.charAt(i - 1));    // sirf s1 ka
            i--;
        }
        else {
            sb.append(s2.charAt(j - 1));    // sirf s2 ka
            j--;
        }
    }

    // ---- Step 3: bache hue characters ----
    while (i > 0) { sb.append(s1.charAt(i - 1)); i--; }
    while (j > 0) { sb.append(s2.charAt(j - 1)); j--; }

    return sb.reverse().toString();
}

Dry Run

s1 = "brute", s2 = "groot"

 ∅groot
∅000000
b000000
r001111
u001111
t001112
e001112

LCS = 2 ("rt")

length = 5 + 5 - 2 = 8 ✅

Backtrack trace — i=5, j=5 se

i, js1[i-1]s2[j-1]CaseAddsb
5, 5etdp[4][5]=2 > dp[5][4]=1 → s1ee
4, 5ttmatchtet
3, 4uodp[2][4]=1, dp[3][3]=1 → s2oeto
3, 3uodp[2][3]=1, dp[3][2]=1 → s2oetoo
3, 2urdp[2][2]=1 > dp[3][1]=0 → s1uetoou
2, 2rrmatchretoour
1, 1bgdp[0][1]=0, dp[1][0]=0 → s2getoourg
1, 0loop khatam (j == 0)—etoourg
tailwhile (i > 0) → s1 ka 'b' bachabetoourgb

sb.reverse() → "bgruoote" — length 8 ✅

Verify karo

StringResult me kahan
b g r u o o t e—
bruteb g r u o o t e ✅
grootb g r u o o t e ✅

Dono subsequence hain, aur length 8 — minimum possible. ✅

Multiple valid answers ho sakte hain ("bgrouote" bhi sahi hai). LeetCode koi bhi valid answer accept karta hai.

Khud try karo

  1. s1 = "abc", s2 = "abc" → "abc", length 3.
  2. s1 = "abc", s2 = "xyz" → length 6, LCS = 0.
  3. Do tail loops hata do — kya galat aata hai? s1 = "abc", s2 = "c" pe test karo.
Q32

Distinct Subsequences

LeetCode 115 (hard) · counting, aur match pe DO options

Combine+
Match pef(i-1,j-1) + f(i-1,j)
No matchf(i-1, j) only

Problem

s1 me s2 kitni baar subsequence ke roop me aati hai? Count karo.

s1 = "babgbag", s2 = "bag" → 5

s1 = "rabbbit", s2 = "rabbit" → 3 (teen alag b chun sakte ho)

Soch — yahan match pe choice HAI

Q25 se sabse bada farak

LCS me match hone pe humne kaha tha "match kar lo, choice hi nahi". Yahan wo galat hai.

Kyunki hum count kar rahe hain, aur ek hi character se banne wale alag-alag ways ko alag ginna hai.

f(i, j) = "s1[0..i] me s2[0..j] kitni baar subsequence hai"

Case 1 — s1[i] == s2[j]: do options

option A: is character ko match karo   → f(i-1, j-1)
option B: is character ko chhod do,
          aage kahin aur match dhoondo  → f(i-1, j)

return A + B;

Case 2 — mismatch: ek hi option

return f(i - 1, j);    // s1 ka character bekaar, chhod do
Yahan f(i, j-1) kyun nahi

Kyunki s2 ka har character match hona hi hai — hum s2 ko poora dhoondh rahe hain, uska hissa chhod nahi sakte. LCS me dono strings barabar the; yahan s2 "target" hai. Isliye sirf s1 ka pointer ghoomta hai.

Base cases — order zaroori

if (j < 0) return 1;   // s2 poori mil gayi ✅ ek tareeka
if (i < 0) return 0;   // s1 khatam, s2 baaki ❌

j < 0 ka check pehle. Agar dono khatam hue toh wo success hai, failure nahi.

Code

1MemoizationO(n × m)
static int f(int i, int j, String s1, String s2, int[][] dp) {
    if (j < 0) return 1;
    if (i < 0) return 0;

    if (dp[i][j] != -1) return dp[i][j];

    if (s1.charAt(i) == s2.charAt(j)) {
        return dp[i][j] = f(i - 1, j - 1, s1, s2, dp)    // match
                        + f(i - 1, j,     s1, s2, dp);   // skip
    }

    return dp[i][j] = f(i - 1, j, s1, s2, dp);
}
2Tabulation — shifted indexO(n × m)
static int numDistinct(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    double[][] dp = new double[n + 1][m + 1];   // overflow se bachne ko

    // base: s2 khaali → 1 tareeka (kuch mat lo)
    for (int i = 0; i <= n; i++) dp[i][0] = 1;

    // base: s1 khaali, s2 nahi → 0 (already 0)

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return (int) dp[n][m];
}
Overflow — LeetCode ka asli trap

Counts exponentially badhte hain. LeetCode 115 guarantee karta hai ki answer int me fit hoga, par beech ke cells overflow kar sakte hain. Isliye double ya long use karo. Ye ek famous "sahi logic, galat answer" bug hai.

3Space Optimized — single arraySC O(m)
static int numDistinct(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    double[] dp = new double[m + 1];
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {       // ⚠️ ULTA loop
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[j] = dp[j - 1] + dp[j];
            }
            // else: dp[j] waisa hi rehta hai (= dp[i-1][j])
        }
    }

    return (int) dp[m];
}
Ulta loop, phir se

dp[j-1] ko pichli row ki value chahiye. Ulta chalne se wo abhi tak update nahi hui. Bilkul wahi trick jo Q15 aur Q19 me 0/1 knapsack ke liye lagayi thi — alag problem, same mechanic.

Dry Run

s1 = "babgbag", s2 = "bag"

 ∅bag
∅1000
b1100
a1110
b1210
g1211
b1311
a1341
g1345

Kuch important cells

CellcharsMatch?CalculationValue
dp[3][1]b, b✅dp[2][0] + dp[2][1] = 1 + 12
dp[5][1]b, b✅dp[4][0] + dp[4][1] = 1 + 23
dp[6][2]a, a✅dp[5][1] + dp[5][2] = 3 + 14
dp[7][3]g, g✅dp[6][2] + dp[6][3] = 4 + 15

Table ko padho

Column 0 poora 1 — khaali s2 banane ka hamesha ek hi tareeka: kuch mat lo. (Q22 ke dp[0] = 1 jaisa hi.)

Column b me values 1 → 2 → 3 badhti hain — s1 me har naya b ek naya tareeka jodta hai. Yahi + dp[i-1][j] wala "skip" term kar raha hai.

Aur diagonal ke upar sab zeros hain — s1 ka chhota prefix s2 ka bada prefix bana hi nahi sakta.

Paanch tareeke — verify

s1 = "b a b g b a g" (indices 0-6). b at 0,2,4 · a at 1,5 · g at 3,6

#bag
1013
2016
3056
4256
5456

5 ✅

Khud try karo

  1. double ki jagah int daal ke LeetCode 115 pe submit karo — kuch test cases fail honge. Wahi overflow hai.
  2. s1 = "abc", s2 = "abcd" → 0. Table me diagonal ke upar wale zeros isko handle karte hain.
  3. Match wale case me sirf dp[i-1][j-1] rakho (skip term hata do) — kya milta hai? (Sirf ek specific matching, count nahi.)
Q33

Edit Distance

LeetCode 72 (hard) · Phase 4 ka sabse famous sawaal

Combinemin
Match pe0 + f(i-1, j-1)
No match1 + min(3 ops)

Problem

s1 ko s2 banana hai. Teen operations allowed, har ek ka cost 1:

  • Insert — koi character daalo
  • Delete — koi character hataao
  • Replace — koi character badlo

Minimum operations?

s1 = "horse", s2 = "ros" → 3

Soch

Q30 me sirf insert/delete the. Ab replace bhi hai — aur wo aksar do operations (delete + insert) ki jagah ek me kaam kar deta hai.

f(i, j) = "s1[0..i] ko s2[0..j] banane ka minimum cost"

Case 1 — s1[i] == s2[j]

Kuch karne ki zaroorat hi nahi. Cost 0, dono pointer peeche:

return 0 + f(i - 1, j - 1);

Case 2 — mismatch: teeno operations try karo

OperationKya hota haiRecursive call
Inserts2[j] ko s1 me daal diya — wo match ho gayaf(i, j-1)
Deletes1[i] hata diyaf(i-1, j)
Replaces1[i] ko s2[j] bana diya — dono matchf(i-1, j-1)
return 1 + min( f(i, j - 1),        // insert
                f(i - 1, j),        // delete
                f(i - 1, j - 1) );  // replace
Insert me i kyun nahi ghata

Ye sabse confusing part hai. Socho aise: humne s1 me ek naya character daala jo s2[j] se match karta hai.

Toh s2 ka wo character ho gaya (j--), par s1 ka original character s1[i] abhi bhi pending hai — use aage handle karna hai. Isliye i waisa ka waisa.

Delete me ulta: s1[i] khatam (i--), par s2[j] ab bhi chahiye.

Base cases

if (i < 0) return j + 1;   // s1 khatam → s2 ke bache chars insert karo
if (j < 0) return i + 1;   // s2 khatam → s1 ke bache chars delete karo

j + 1 kyunki index 0..j me j+1 characters hote hain.

Code

1MemoizationO(n × m)
static int f(int i, int j, String s1, String s2, int[][] dp) {
    if (i < 0) return j + 1;
    if (j < 0) return i + 1;

    if (dp[i][j] != -1) return dp[i][j];

    if (s1.charAt(i) == s2.charAt(j)) {
        return dp[i][j] = 0 + f(i - 1, j - 1, s1, s2, dp);
    }

    int insert  = f(i,     j - 1, s1, s2, dp);
    int delete  = f(i - 1, j,     s1, s2, dp);
    int replace = f(i - 1, j - 1, s1, s2, dp);

    return dp[i][j] = 1 + Math.min(insert,
                          Math.min(delete, replace));
}
2Tabulation — shifted indexO(n × m)
static int minDistance(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    int[][] dp = new int[n + 1][m + 1];

    // base: s2 khaali → s1 ke saare chars delete
    for (int i = 0; i <= n; i++) dp[i][0] = i;

    // base: s1 khaali → s2 ke saare chars insert
    for (int j = 0; j <= m; j++) dp[0][j] = j;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i][j - 1],          // insert
                             Math.min(dp[i - 1][j],            // delete
                                      dp[i - 1][j - 1]));      // replace
            }
        }
    }

    return dp[n][m];
}
Base case ab free nahi hai

Q25 me pehli row/column zeros the aur Java ne khud bhar diye the. Yahan wo 0, 1, 2, 3... hain — do explicit loops chahiye. Ye bhoolna common bug hai; answer chhota aayega.

3Space OptimizedSC O(m)
static int minDistance(String s1, String s2) {
    int n = s1.length(), m = s2.length();

    int[] prev = new int[m + 1];
    for (int j = 0; j <= m; j++) prev[j] = j;

    for (int i = 1; i <= n; i++) {
        int[] curr = new int[m + 1];
        curr[0] = i;                          // ⚠️ har row me set karo

        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                curr[j] = prev[j - 1];
            } else {
                curr[j] = 1 + Math.min(curr[j - 1],
                          Math.min(prev[j], prev[j - 1]));
            }
        }

        prev = curr;
    }

    return prev[m];
}

Dry Run

s1 = "horse", s2 = "ros"

 ∅ros
∅0123
h1123
o2212
r3222
s4332
e5443

Kuch important cells

CellcharsMatch?CalculationValue
dp[1][1]h, r❌1 + min(dp[1][0]=1, dp[0][1]=1, dp[0][0]=0) = 1+01
dp[2][2]o, o✅dp[1][1] = 1 — free1
dp[3][1]r, r✅dp[2][0] = 2 — free2
dp[4][3]s, s✅dp[3][2] = 2 — free2
dp[5][3]e, s❌1 + min(dp[5][2]=4, dp[4][3]=2, dp[4][2]=3) = 1+23

Teen operations — verify

StepStringOperation
0h o r s estart
1r o r s ereplace 'h' → 'r'
2r o s edelete 'r' (index 2)
3r o sdelete 'e' ✅

Table ko padho

  • Pehli row = 0,1,2,3 — khaali s1 se "ros" banane ke liye 3 inserts.
  • Pehla column = 0,1,2,3,4,5 — "horse" ko khaali banane ke liye 5 deletes.
  • Match wale cells diagonal se seedha copy karte hain (+1 nahi) — free operation. Table me wo o-o, r-r, s-s pe dikh raha hai.
  • Adjacent cells me farak hamesha 0 ya 1 hi hota hai.
Q30 se compare karo

Same input pe Q30 (sirf insert/delete) deta: n + m - 2×LCS = 5 + 3 - 2×2 = 4. Edit Distance deta 3. Replace ne ek operation bacha liya.

Khud try karo

  1. s1 = "intention", s2 = "execution" → 5. Poori table banao.
  2. Operations print karo, sirf count nahi. Backtrack karke dekho ki har cell kis case se aayi.
  3. Agar replace ka cost 2 ho (insert/delete ka 1) toh? Code me kya badlega? Aur kya answer Q30 ke barabar aa jaayega? (Haan — kyunki replace tab delete+insert se sasta nahi rahega.)
Q34

Wildcard Matching

LeetCode 44 (hard) · Phase 4 ka finale

Combine||
'?' pef(i-1, j-1)
'*' pef(i-1,j) || f(i,j-1)

Problem

Pattern p aur string s diye hain. Kya p poori s ko match karta hai?

  • ? — exactly ek character match karta hai
  • * — koi bhi sequence (khaali bhi) match karta hai
spResult
"aa""a"false
"aa""*"true
"cb""?a"false
"adceb""*a*b"true

Soch — teen cases

f(i, j) = "kya p[0..j], s[0..i] ko match karta hai?" (i string ka, j pattern ka)

Case 1 — direct match ya ?

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')
    return f(i - 1, j - 1);

? ek character kha jaata hai — bilkul normal match jaisa.

Case 2 — *: do options

if (p.charAt(j) == '*')
    return f(i - 1, j)      // * ne s[i] ko kha liya, aur bhi kha sakta hai
        || f(i,     j - 1); // * ne khaali match kiya, aage badho
Ye do line poora sawaal hai

f(i-1, j) — * ne ek aur character nigal liya, par * abhi bhi zinda hai (j nahi ghata). Isse * jitne chahe utne characters kha sakta hai.

f(i, j-1) — * ne zero characters match kiye, ab pattern me aage badho.

Dono me se koi bhi true de de toh kaam ho gaya → ||.

Case 3 — mismatch

return false;

Base cases — yahan sabse zyada log fasste hain

if (i < 0 && j < 0) return true;    // dono khatam ✅

if (j < 0) return false;            // pattern khatam, string baaki ❌

if (i < 0) {                        // string khatam, pattern baaki
    for (int k = 0; k <= j; k++)
        if (p.charAt(k) != '*') return false;
    return true;                    // sab '*' hain → khaali match ✅
}
Teesra base case

String khatam ho gayi par pattern bacha hai — ye tabhi true hai jab bache hue saare characters * hon (kyunki * khaali match kar sakta hai). Ek bhi normal character ya ? bacha toh false. Ye check bhoolna sabse common bug hai.

Code

1MemoizationO(n × m)
static boolean isAllStars(String p, int j) {
    for (int k = 0; k <= j; k++)
        if (p.charAt(k) != '*') return false;
    return true;
}

static boolean f(int i, int j, String s, String p, int[][] dp) {
    if (i < 0 && j < 0) return true;
    if (j < 0)          return false;
    if (i < 0)          return isAllStars(p, j);

    if (dp[i][j] != -1) return dp[i][j] == 1;

    boolean ans;

    if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
        ans = f(i - 1, j - 1, s, p, dp);
    }
    else if (p.charAt(j) == '*') {
        ans = f(i - 1, j, s, p, dp) || f(i, j - 1, s, p, dp);
    }
    else {
        ans = false;
    }

    dp[i][j] = ans ? 1 : 0;
    return ans;
}
2Tabulation — shifted indexO(n × m)
static boolean isMatch(String s, String p) {
    int n = s.length(), m = p.length();

    boolean[][] dp = new boolean[n + 1][m + 1];

    dp[0][0] = true;                       // dono khaali

    // s khaali, p baaki → sab '*' hone chahiye
    for (int j = 1; j <= m; j++) {
        boolean allStars = true;
        for (int k = 1; k <= j; k++)
            if (p.charAt(k - 1) != '*') { allStars = false; break; }
        dp[0][j] = allStars;
    }

    // p khaali, s baaki → dp[i][0] = false (default)

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s.charAt(i - 1) == p.charAt(j - 1)
                    || p.charAt(j - 1) == '?') {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if (p.charAt(j - 1) == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
            else {
                dp[i][j] = false;
            }
        }
    }

    return dp[n][m];
}
3Space OptimizedSC O(m)
static boolean isMatch(String s, String p) {
    int n = s.length(), m = p.length();

    boolean[] prev = new boolean[m + 1];
    prev[0] = true;

    for (int j = 1; j <= m; j++) {
        prev[j] = prev[j - 1] && p.charAt(j - 1) == '*';
    }

    for (int i = 1; i <= n; i++) {
        boolean[] curr = new boolean[m + 1];
        curr[0] = false;                    // p khaali, s baaki

        for (int j = 1; j <= m; j++) {
            if (s.charAt(i - 1) == p.charAt(j - 1)
                    || p.charAt(j - 1) == '?')
                curr[j] = prev[j - 1];
            else if (p.charAt(j - 1) == '*')
                curr[j] = prev[j] || curr[j - 1];
            else
                curr[j] = false;
        }

        prev = curr;
    }

    return prev[m];
}
Base case ka chhota upgrade

Space-optimized me prev[j] = prev[j-1] && p.charAt(j-1) == '*' — ye nested loop ki jagah ek line me "ab tak sab star the?" track kar leta hai. Pehla non-star aate hi false ho jaata hai aur phir kabhi true nahi hota. Chhota par saaf trick.

Dry Run

s = "adceb", p = "*a*b"

 ∅*a*b
∅TTFFF
aFTTTF
dFTFTF
cFTFTF
eFTFTF
bFTFTT

Kuch important cells

Cells charp charRuleValue
dp[0][1]∅*base: sab star takT
dp[0][2]∅abase: 'a' star nahiF
dp[1][2]aamatch → dp[0][1] = TT
dp[2][3]d*dp[1][3]=T || dp[2][2]=FT
dp[5][4]bbmatch → dp[4][3] = TT

Answer = true ✅

Kaise match hua

* (pehla) → khaali · a → 'a' · * (doosra) → "dce" · b → 'b'

Table me column * (index 3) poora T hai row 1 se aage — kyunki wo star kitne bhi characters nigal sakta hai. Yahi dp[i-1][j] wali line kar rahi hai.

Table ko padho

* ke columns vertically phailte hain (ek baar T hua toh neeche sab T) — kyunki star aur characters kha sakta hai. Normal characters ke columns me T sirf ek specific cell pe aata hai. Ye visual pattern * ki taakat ka seedha dikhta hua roop hai.

🎉 Phase 4 complete

#SawaalMatch peNo matchReduction
25LCS1 + diagmax(up, left)—
26Print LCSQ25 table pe backtrack—
27Common Substring1 + diag0 (reset)—
28LPS—LCS(s, rev(s))
29Min Insert Palindrome—n − LPS
30Insert/Delete A→B—n + m − 2·LCS
31Shortest Supersequence3-case backtrackn + m − LCS
32Distinct Subsequencesdiag + upup only—
33Edit Distance0 + diag1 + min(3)—
34Wildcard Matchingdiag* → up || left—

Chaar sawaal (Q28–Q31) me naya DP likha hi nahi — sirf LCS ko ghumaya. Phase 3 ka wahi sabak yahan bhi.

Khud try karo

  1. s = "aa", p = "*" → true. Aur s = "", p = "***" → true. Base cases test karo.
  2. Teesra base case (isAllStars) hata do — kaunsa test case tootega? (s = "a", p = "a*")
  3. Regular Expression Matching — LeetCode 10 (hard). Wahan * ka matlab alag hai: "pichla character zero ya zyada baar". Bahut zyada tedha hai — par agar Q34 samajh gaye toh wo bhi lag jaayega.

Phase 5 · Q35–Q40

DP on Stocks

Chhe sawaal, ek hi soch. Har din pe ek hi sawaal: "abhi mere paas share hai ya nahi?" — aur usi ke hisaab se do choices banti hain. Ye Q7 (Ninja's Training) wali soch hai: jo cheez decision ko affect karti hai, use state me daal do.

Phase 5 core recurrence f(i, buy):  // buy = 1 → khareed sakte ho, 0 → bech sakte ho

    if (buy == 1)
        return max( -prices[i] + f(i+1, 0),  // khareed lo
                     0 + f(i+1, 1) )  // skip

    return max( +prices[i] + f(i+1, 1),  // bech do
                0 + f(i+1, 0) )  // skip
    // base: i == n → 0
Q35

Best Time to Buy and Sell Stock

LeetCode 121 · exactly 1 transaction

Transactions1
StateminPrice tak
TimeO(n), SC O(1)

Problem

prices[i] = i-th din ka share ka daam. Ek baar khareedo aur ek baar becho (bechne se pehle khareedna zaroori). Maximum profit?

prices = [7, 1, 5, 3, 6, 4] → 5 (din 1 pe ₹1 me khareedo, din 4 pe ₹6 me becho)

prices = [7, 6, 4, 3, 1] → 0 (daam sirf girta hai — kuch mat karo)

Soch — ye DP hai bhi ya nahi?

Sirf ek transaction hai, toh sawaal simple ban jaata hai:

Har din i ke liye: agar aaj bechun, toh maximum profit kitna? = prices[i] − (ab tak ka sabse kam daam)

Toh bas left se chalte jao aur do cheezein track karo: ab tak ka minimum price, aur ab tak ka maximum profit.

Ye technically DP hi hai

minPrice ek 1-state DP hai — "din i tak ka best buying point". Bas itna simple hai ki alag dp[] array ki zaroorat hi nahi, ek variable kaafi hai. Q1 me Fibonacci ka space-optimized version bhi to yahi tha.

Code

→Single passO(n) / SC O(1)
static int maxProfit(int[] prices) {
    int minPrice  = prices[0];
    int maxProfit = 0;

    for (int i = 1; i < prices.length; i++) {

        // agar aaj bechein toh kitna profit
        int profit = prices[i] - minPrice;
        maxProfit  = Math.max(maxProfit, profit);

        // kal ke liye best buying point update karo
        minPrice   = Math.min(minPrice, prices[i]);
    }

    return maxProfit;
}
Order matter karta hai

profit pehle nikalo, minPrice baad me update karo. Ulta karoge toh aaj ke din khareed ke aaj hi bech doge — profit hamesha 0. Logically galat, aur silently galat.

Dry Run

prices = [7, 1, 5, 3, 6, 4]

ipriceminPrice (pehle)profit = price − minmaxProfitminPrice (baad me)
07——07
1171−7 = −601
2515−1 = 441
3313−1 = 241
4616−1 = 551
5414−1 = 351

Answer = 5 ✅

i = 1 pe profit negative aaya — par maxProfit 0 se shuru hua tha, isliye wo 0 hi raha. Yahi "kuch mat karo" wala option hai, automatically handled.

Khud try karo

  1. Kaunse din khareeda aur becha, wo bhi print karo. (Do extra variables track karne padenge.)
  2. Ye same sawaal Phase 5 wale f(i, buy) template se likho, aur verify karo ki same answer aata hai. Us version me ek teesra state (cap = 1) chahiye hoga — wo Q37 ka warm-up hai.
  3. Agar short selling allowed ho (pehle bech ke baad me khareedna)? Answer kya badlega?
Q36

Stock II — Infinite Transactions

LeetCode 122 · asli DP template yahan se shuru

Transactionsinfinite
Statei, buy
dp sizen × 2

Problem

Jitni chaaho utni transactions kar sakte ho. Par ek waqt me sirf ek share — bechne se pehle dobara nahi khareed sakte. Maximum profit?

prices = [7, 1, 5, 3, 6, 4] → 7

Khareedo ₹1 becho ₹5 (profit 4), khareedo ₹3 becho ₹6 (profit 3). Total 7 ✅

Soch — "buy" ko state banao

Har din pe kya kar sakte ho, ye is baat pe depend karta hai ki abhi share paas me hai ya nahi. Toh wahi state me daal do.

buyMatlabDo choices
1share paas me nahi hai — khareed sakte hokhareedo (−price) ya skip
0share paas me hai — bech sakte hobecho (+price) ya skip
Naam ka confusion

buy = 1 ka matlab hai "khareedne ki baari hai", na ki "khareed liya hai". Bahut log ulta samajh lete hain. Agar confusion ho toh canBuy naam de do.

f(i, buy) = "din i se aage, buy state me, maximum profit"

if (buy == 1)
    return max( -prices[i] + f(i+1, 0),    // khareeda → ab bech sakte ho
                 0         + f(i+1, 1) );  // skip

return max( +prices[i] + f(i+1, 1),        // becha → ab khareed sakte ho
             0         + f(i+1, 0) );      // skip
Paisa kaise chalta hai

Khareedne pe -prices[i] (kharcha) aur bechne pe +prices[i] (kamai). End me sab jud ke net profit ban jaata hai. Alag se "kitne me khareeda tha" yaad rakhne ki zaroorat hi nahi — ye ek bahut saaf trick hai.

Base case

if (i == n) return 0;    // din khatam, aage kamai nahi

Code

1MemoizationO(n × 2)
static long f(int i, int buy, int n, int[] prices, long[][] dp) {
    if (i == n) return 0;

    if (dp[i][buy] != -1) return dp[i][buy];

    long profit;

    if (buy == 1) {
        profit = Math.max(-prices[i] + f(i + 1, 0, n, prices, dp),
                           0         + f(i + 1, 1, n, prices, dp));
    } else {
        profit = Math.max( prices[i] + f(i + 1, 1, n, prices, dp),
                           0         + f(i + 1, 0, n, prices, dp));
    }

    return dp[i][buy] = profit;
}

// driver
long[][] dp = new long[n][2];
for (long[] row : dp) Arrays.fill(row, -1);
System.out.println(f(0, 1, n, prices, dp));
2TabulationO(n × 2)
static long maxProfit(int[] prices) {
    int n = prices.length;

    long[][] dp = new long[n + 1][2];

    dp[n][0] = 0;                          // base case
    dp[n][1] = 0;

    for (int i = n - 1; i >= 0; i--) {     // ULTA (recursion aage jaati thi)
        for (int buy = 0; buy <= 1; buy++) {

            long profit;

            if (buy == 1) {
                profit = Math.max(-prices[i] + dp[i + 1][0],
                                   0         + dp[i + 1][1]);
            } else {
                profit = Math.max( prices[i] + dp[i + 1][1],
                                   0         + dp[i + 1][0]);
            }

            dp[i][buy] = profit;
        }
    }

    return dp[0][1];
}
3Space OptimizedSC O(1)
static long maxProfit(int[] prices) {
    int n = prices.length;

    long aheadBuy = 0, aheadSell = 0;      // dp[i+1][1], dp[i+1][0]

    for (int i = n - 1; i >= 0; i--) {
        long currBuy  = Math.max(-prices[i] + aheadSell, aheadBuy);
        long currSell = Math.max( prices[i] + aheadBuy,  aheadSell);

        aheadBuy  = currBuy;
        aheadSell = currSell;
    }

    return aheadBuy;
}
2D dp → 2 variables

dp[i] sirf dp[i+1] pe depend hai, aur har row me sirf 2 cells hain. Toh 2 variables kaafi — O(1) space. Phase 1 ke prev/prev2 ka hi bada bhai hai.

Dry Run

prices = [7, 1, 5, 3, 6, 4], n = 6. Ulta chalte hain (i = 5 se 0).

ipricecurrBuy = max(−p + aheadSell, aheadBuy)currSell = max(p + aheadBuy, aheadSell)
6—0 (base)0 (base)
54max(−4+0, 0) = 0max(4+0, 0) = 4
46max(−6+4, 0) = 0max(6+0, 4) = 6
33max(−3+6, 0) = 3max(3+0, 6) = 6
25max(−5+6, 3) = 3max(5+3, 6) = 8
11max(−1+8, 3) = 7max(1+3, 8) = 8
07max(−7+8, 7) = 7max(7+7, 8) = 14

Answer = currBuy at i=0 = 7 ✅

Trace karo kaunse din

i=1 pe currBuy = 7 aaya -1 + 8 se — matlab din 1 pe ₹1 me khareeda.

i=2 pe currSell = 8 aaya 5 + 3 se — din 2 pe ₹5 me becha, aur baaki 3 aage se.

i=3 pe currBuy = 3 aaya -3 + 6 se — din 3 pe ₹3 me khareeda.

i=4 pe currSell = 6 aaya 6 + 0 se — din 4 pe ₹6 me becha.

Total: (5-1) + (6-3) = 4 + 3 = 7 ✅

Ek greedy shortcut bhi hai

Infinite transactions me jahan bhi prices[i+1] > prices[i] ho, wo farak jod do — answer wahi aayega, O(n) me ek line me. Par interview me DP hi likhna, kyunki Q37–Q40 me greedy kaam nahi karta aur DP wahi ka wahi rehta hai.

Khud try karo

  1. Greedy version likho (sum of positive diffs) aur DP se compare karo. Random arrays pe 1000 baar test karo.
  2. f(0, 0) se call karke dekho — kya milta hai? (Galat answer, kyunki shuruaat me share paas me nahi hota.)
  3. Q35 ko is template se likho: teesra state cap add karo aur cap = 1 se shuru karo. Answer 5 aana chahiye.
Q37

Stock III — At Most 2 Transactions

LeetCode 123 (hard) · teesra state add hota hai

Transactionsat most 2
Statei, buy, cap
dp sizen × 2 × 3

Problem

Zyada se zyada 2 transactions. Maximum profit?

prices = [3, 3, 5, 0, 0, 3, 1, 4] → 6

Khareedo ₹0 (din 3) becho ₹3 (din 5) → profit 3. Khareedo ₹1 (din 6) becho ₹4 (din 7) → profit 3. Total 6 ✅

Soch — wahi sawaal, phir se

"Decision lene ke liye mujhe kya-kya pata hona chahiye?"

  1. Kaunsa din hai → i
  2. Share paas me hai ya nahi → buy
  3. Kitni transactions bachi hain → cap ← naya!

Bina cap ke pata hi nahi chalega ki aur transaction kar sakte ho ya limit khatam ho gayi. Isliye state me daalna zaroori hai.

Cap kab ghatana hai — ek convention chuno

Transaction "poori" tab hoti hai jab bech diya. Toh cap bechne pe ghatega, khareedne pe nahi.

(Ulta convention bhi chalta hai — khareedne pe ghatao. Par ek hi chuno aur uspe tike raho, warna off-by-one bug pakka.)

if (buy == 1)
    return max( -prices[i] + f(i+1, 0, cap),
                 0         + f(i+1, 1, cap) );

return max( +prices[i] + f(i+1, 1, cap - 1),   // ⚠️ cap ghata
             0         + f(i+1, 0, cap) );

Base cases — ab do hain

if (i == n)   return 0;    // din khatam
if (cap == 0) return 0;    // transactions khatam

Code

1Memoization — 3D dpO(n × 2 × 3)
static int f(int i, int buy, int cap, int n, int[] prices, int[][][] dp) {
    if (i == n)   return 0;
    if (cap == 0) return 0;

    if (dp[i][buy][cap] != -1) return dp[i][buy][cap];

    int profit;

    if (buy == 1) {
        profit = Math.max(-prices[i] + f(i + 1, 0, cap,     n, prices, dp),
                           0         + f(i + 1, 1, cap,     n, prices, dp));
    } else {
        profit = Math.max( prices[i] + f(i + 1, 1, cap - 1, n, prices, dp),
                           0         + f(i + 1, 0, cap,     n, prices, dp));
    }

    return dp[i][buy][cap] = profit;
}

// driver
int[][][] dp = new int[n][2][3];      // cap: 0, 1, 2
for (int[][] a : dp) for (int[] b : a) Arrays.fill(b, -1);
System.out.println(f(0, 1, 2, n, prices, dp));
2TabulationO(n × 2 × 3)
static int maxProfit(int[] prices) {
    int n = prices.length;

    int[][][] dp = new int[n + 1][2][3];
    // base cases sab 0 hain — Java default ✅

    for (int i = n - 1; i >= 0; i--) {
        for (int buy = 0; buy <= 1; buy++) {
            for (int cap = 1; cap <= 2; cap++) {   // cap=0 hamesha 0

                int profit;

                if (buy == 1) {
                    profit = Math.max(-prices[i] + dp[i + 1][0][cap],
                                       0         + dp[i + 1][1][cap]);
                } else {
                    profit = Math.max( prices[i] + dp[i + 1][1][cap - 1],
                                       0         + dp[i + 1][0][cap]);
                }

                dp[i][buy][cap] = profit;
            }
        }
    }

    return dp[0][1][2];
}
3Space Optimized — ek 2D layerSC O(1)
static int maxProfit(int[] prices) {
    int n = prices.length;

    int[][] ahead = new int[2][3];
    int[][] curr  = new int[2][3];

    for (int i = n - 1; i >= 0; i--) {
        for (int buy = 0; buy <= 1; buy++) {
            for (int cap = 1; cap <= 2; cap++) {

                if (buy == 1) {
                    curr[buy][cap] = Math.max(-prices[i] + ahead[0][cap],
                                               0         + ahead[1][cap]);
                } else {
                    curr[buy][cap] = Math.max( prices[i] + ahead[1][cap - 1],
                                               0         + ahead[0][cap]);
                }
            }
        }

        // deep copy zaroori hai, warna reference share ho jaayega
        for (int b = 0; b < 2; b++)
            ahead[b] = curr[b].clone();
    }

    return ahead[1][2];
}
Java ka reference trap

ahead = curr; likhoge toh dono same array point karenge, aur agli iteration me curr badalte hi ahead bhi badal jaayega. Ye silently galat answer deta hai. clone() ya nayi array banana zaroori hai. (Q7–Q13 me hum har baar new int[] bana rahe the, isliye ye problem nahi aayi thi.)

Dry Run

prices = [3, 3, 5, 0, 0, 3, 1, 4], n = 8

Poori 8×2×3 table lambi hai, toh important cells dekhte hain (ulta chalte hue).

iprice[1][2] — buy, 2 left[0][2] — sell, 2 left[1][1] — buy, 1 left[0][1] — sell, 1 left
8—0000
740404
613434
533634
406634
306634
256635
036———

Do important cells samjho

i=5, [0][2] = 6 — din 5 pe share paas me hai, 2 transactions bachi hain.
max(3 + dp[6][1][1], dp[6][0][2]) = max(3 + 3, 4) = 6. Bech diya ₹3 me, aur cap 1 ho gaya — phir bhi ek transaction bachi thi jo aage 3 aur kama layi.

i=4, [1][2] = 6 — din 4 pe khareedne ki baari, price ₹0.
max(-0 + dp[5][0][2], dp[5][1][2]) = max(0 + 6, 3) = 6. Muft me khareed liya ✅

Answer = dp[0][1][2] = 6 ✅

Khud try karo

  1. cap ko khareedne pe ghatane wala version likho. Base case aur initial call kaise badlenge? (Hint: cap ab "kitni buy bachi hain" ho jaayega.)
  2. ahead[b] = curr[b].clone() ko ahead = curr se badal ke dekho — kya answer galat aata hai?
  3. cap = 2 ki jagah cap = 1 daalo — kya Q35 ka answer aata hai? Aana chahiye.
Q38

Stock IV — At Most K Transactions

LeetCode 188 (hard) · Q37 me 2 ki jagah k

Transactionsat most k
Statei, buy, cap
dp sizen × 2 × (k+1)

Problem

Q37 wahi, bas ab limit 2 nahi k hai.

k = 2, prices = [2, 4, 1] → 2

k = 2, prices = [3, 2, 6, 5, 0, 3] → 7

Soch

Q37 ka code lo, 2 ki jagah k likh do. Bas.

Ye bilkul Q3 → Q4 (Frog Jump → Frog Jump K) wala jump hai — hardcoded constant ko variable bana dena.

Q37Q38
dp size[n][2][3][n][2][k+1]
cap loop1 to 21 to k
initial callf(0, 1, 2)f(0, 1, k)
ComplexityO(n × 2 × 3)O(n × 2 × k)
Ek chhota par zaroori observation

Agar k ≥ n/2 ho, toh limit ka koi matlab hi nahi rehta — n dinon me n/2 se zyada transactions ho hi nahi sakti (har transaction ko kam se kam 2 din chahiye). Us case me seedha Q36 (infinite) chala do — O(n) me kaam ho jaayega. Interview me ye optimization mention karna.

Code

1TabulationO(n × 2 × k)
static int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (n == 0 || k == 0) return 0;

    int[][][] dp = new int[n + 1][2][k + 1];

    for (int i = n - 1; i >= 0; i--) {
        for (int buy = 0; buy <= 1; buy++) {
            for (int cap = 1; cap <= k; cap++) {

                int profit;

                if (buy == 1) {
                    profit = Math.max(-prices[i] + dp[i + 1][0][cap],
                                       0         + dp[i + 1][1][cap]);
                } else {
                    profit = Math.max( prices[i] + dp[i + 1][1][cap - 1],
                                       0         + dp[i + 1][0][cap]);
                }

                dp[i][buy][cap] = profit;
            }
        }
    }

    return dp[0][1][k];
}
2Space OptimizedSC O(k)
static int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (n == 0 || k == 0) return 0;

    int[][] ahead = new int[2][k + 1];

    for (int i = n - 1; i >= 0; i--) {
        int[][] curr = new int[2][k + 1];

        for (int buy = 0; buy <= 1; buy++) {
            for (int cap = 1; cap <= k; cap++) {

                if (buy == 1) {
                    curr[buy][cap] = Math.max(-prices[i] + ahead[0][cap],
                                               0         + ahead[1][cap]);
                } else {
                    curr[buy][cap] = Math.max( prices[i] + ahead[1][cap - 1],
                                               0         + ahead[0][cap]);
                }
            }
        }

        ahead = curr;       // curr har baar naya hai, isliye safe
    }

    return ahead[1][k];
}
Ab ahead = curr safe kyun hai

Kyunki curr loop ke andar naya banaya jaata hai. Q37 me hum ek hi curr reuse kar rahe the, isliye clone() chahiye tha. Do valid patterns hain — par mix mat karna.

Dry Run

k = 2, prices = [3, 2, 6, 5, 0, 3], n = 6

iprice[1][2][0][2][1][1][0][1]
6—0000
530303
403333
353835
263936
127946
037———

Do cells samjho

i=2, [0][2] = 9 — max(6 + dp[3][1][1], dp[3][0][2]) = max(6 + 3, 8) = 9. ₹6 me becha, aur bachi hui ek transaction se aage 3 aur mile.

i=1, [1][2] = 7 — max(-2 + dp[2][0][2], dp[2][1][2]) = max(-2 + 9, 3) = 7. ₹2 me khareeda ✅

Answer = 7 ✅ — khareedo ₹2 becho ₹6 (4), khareedo ₹0 becho ₹3 (3). Total 7.

Khud try karo

  1. k = 100, prices length 6 daalo. Kya answer Q36 (infinite) ke barabar aata hai? Aur k ≥ n/2 wala shortcut laga ke time compare karo.
  2. k = 0 → 0. Guard clause ke bina kya hota? (Array size [n][2][1], cap loop chalta hi nahi, dp[0][1][0] = 0 — sahi answer, par guard rakhna saaf hai.)
  3. Q36, Q37, Q38 ka code side-by-side rakho. Q36 = Q38 with k = ∞, Q37 = Q38 with k = 2, Q35 = Q38 with k = 1. Chaar sawaal, ek code.
Q39

Stock with Cooldown

LeetCode 309 · bechne ke baad ek din ka rest

Transactionsinfinite
Twistsell → i+2
Statei, buy

Problem

Infinite transactions, par bechne ke agle din khareed nahi sakte (ek din ka cooldown).

prices = [1, 2, 3, 0, 2] → 3

Khareedo ₹1 → becho ₹2 (profit 1) → cooldown → khareedo ₹0 → becho ₹2 (profit 2). Total 3 ✅

Soch — ek character ka change

Q36 ka poora code lo. Sirf sell wali line me i+1 ko i+2 kar do.

// Q36 (no cooldown)
sell = prices[i] + f(i + 1, 1);

// Q39 (cooldown)
sell = prices[i] + f(i + 2, 1);    // ek din skip
Kyun i+2

Aaj becha (i), kal cooldown (i+1) — toh agla din jab kuch kar sakte ho wo i+2 hai. Bas itna. Kuch aur badalne ki zaroorat nahi. Ye Q5 (House Robber) wali soch hi hai — wahan bhi take karne pe i-2 pe koodte the.

Base case — ab thoda sambhal ke

if (i >= n) return 0;    // ⚠️ == nahi, >=
Ek akshar ka bug

i + 2 ki wajah se index n ko chhod ke seedha n+1 pe pahunch sakta hai. if (i == n) likha toh wo case miss ho jaayega aur ArrayIndexOutOfBounds aayega. >= zaroori hai.

Tabulation me isi wajah se dp array [n + 2][2] banana padta hai, [n + 1][2] nahi.

Code

1MemoizationO(n × 2)
static int f(int i, int buy, int n, int[] prices, int[][] dp) {
    if (i >= n) return 0;                // ⚠️ >=

    if (dp[i][buy] != -1) return dp[i][buy];

    int profit;

    if (buy == 1) {
        profit = Math.max(-prices[i] + f(i + 1, 0, n, prices, dp),
                           0         + f(i + 1, 1, n, prices, dp));
    } else {
        profit = Math.max( prices[i] + f(i + 2, 1, n, prices, dp),  // i+2
                           0         + f(i + 1, 0, n, prices, dp));
    }

    return dp[i][buy] = profit;
}
2TabulationO(n × 2)
static int maxProfit(int[] prices) {
    int n = prices.length;

    int[][] dp = new int[n + 2][2];      // ⚠️ +2, kyunki i+2 access hota hai

    for (int i = n - 1; i >= 0; i--) {
        for (int buy = 0; buy <= 1; buy++) {

            int profit;

            if (buy == 1) {
                profit = Math.max(-prices[i] + dp[i + 1][0],
                                   0         + dp[i + 1][1]);
            } else {
                profit = Math.max( prices[i] + dp[i + 2][1],   // i+2
                                   0         + dp[i + 1][0]);
            }

            dp[i][buy] = profit;
        }
    }

    return dp[0][1];
}
3Space Optimized — ab TEEN rows chahiyeSC O(1)
static int maxProfit(int[] prices) {
    int n = prices.length;

    int[] front2 = new int[2];    // dp[i+2]
    int[] front1 = new int[2];    // dp[i+1]

    for (int i = n - 1; i >= 0; i--) {
        int[] curr = new int[2];

        curr[1] = Math.max(-prices[i] + front1[0], front1[1]);
        curr[0] = Math.max( prices[i] + front2[1], front1[0]);

        front2 = front1;          // window slide, do kadam
        front1 = curr;
    }

    return front1[1];
}
Do rows nahi, teen

Ab tak Phase 5 me ahead aur curr se kaam chal raha tha. Yahan i+2 access hota hai, toh do aage wali rows rakhni padti hain. Bilkul Q1 (Fibonacci) ke prev/prev2 jaisa — dependency jitni door tak jaati hai, utni rows rakho.

Dry Run

prices = [1, 2, 3, 0, 2], n = 5. Ulta chalte hain.

ipricefront2[1]front1[0]front1[1]curr[1] = max(−p+f1[0], f1[1])curr[0] = max(p+f2[1], f1[0])
5,6—000——
42000max(−2+0, 0) = 0max(2+0, 0) = 2
30020max(−0+2, 0) = 2max(0+0, 2) = 2
23022max(−3+2, 2) = 2max(3+0, 2) = 3
12232max(−2+3, 2) = 2max(2+2, 3) = 4
01242max(−1+4, 2) = 3max(1+2, 4) = 4

Answer = 3 ✅

Cooldown kahan dikha

i=1 pe curr[0] = 4 aaya 2 + front2[1] se — matlab din 1 pe becha, aur agla khareedne ka mauka din 3 pe (din 2 cooldown). Aur front2[1] tab dp[3][1] = 2 tha ✅

Agar cooldown na hota (Q36), toh i=1 pe 2 + dp[2][1] = 2 + 2 = 4 hi aata — is example me sanyog se same. Par bade arrays me farak saaf dikhta hai.

Khud try karo

  1. i+2 ko i+1 kar do — Q36 ban jaana chahiye. Same input pe answer 4 aayega (cooldown ke bina behtar).
  2. dp array [n+1][2] banao (+2 ki jagah) — crash hota hai? Kaunse input pe?
  3. Cooldown 2 din ka ho toh? (i+3, aur front3 bhi rakhna padega.)
Q40

Stock with Transaction Fee

LeetCode 714 · Phase 5 ka aakhri — sabse aasan

Transactionsinfinite
Twistsell pe − fee
Statei, buy

Problem

Infinite transactions, par har poori transaction pe ek fixed fee lagti hai. Maximum profit?

prices = [1, 3, 2, 8, 4, 9], fee = 2 → 8

Khareedo ₹1 becho ₹8 → 8 - 1 - 2 = 5. Khareedo ₹4 becho ₹9 → 9 - 4 - 2 = 3. Total 8 ✅

Soch — ek term ka change

Q36 ka code lo. Sell wali line me - fee jod do.

// Q36
sell = prices[i] + f(i + 1, 1);

// Q40
sell = prices[i] - fee + f(i + 1, 1);
Fee kahan lagayein — buy ya sell?

Dono chalte hain! -prices[i] - fee (buy pe) ya +prices[i] - fee (sell pe) — ek transaction me ek hi baar lagti hai, toh answer same.

Par sell pe lagana behtar hai, kyunki tab fee sirf poori transactions pe lagti hai. Buy pe lagate toh aakhri me agar share bina bike reh gaya (jo optimal solution me hota nahi, par logically) toh fee bekaar lag jaati.

Code

1MemoizationO(n × 2)
static int f(int i, int buy, int n, int fee, int[] prices, int[][] dp) {
    if (i == n) return 0;

    if (dp[i][buy] != -1) return dp[i][buy];

    int profit;

    if (buy == 1) {
        profit = Math.max(-prices[i] + f(i + 1, 0, n, fee, prices, dp),
                           0         + f(i + 1, 1, n, fee, prices, dp));
    } else {
        profit = Math.max( prices[i] - fee + f(i + 1, 1, n, fee, prices, dp),
                           0               + f(i + 1, 0, n, fee, prices, dp));
    }

    return dp[i][buy] = profit;
}
2Space OptimizedSC O(1)
static int maxProfit(int[] prices, int fee) {
    int n = prices.length;

    int aheadBuy = 0, aheadSell = 0;

    for (int i = n - 1; i >= 0; i--) {
        int currBuy  = Math.max(-prices[i]       + aheadSell, aheadBuy);
        int currSell = Math.max( prices[i] - fee + aheadBuy,  aheadSell);

        aheadBuy  = currBuy;
        aheadSell = currSell;
    }

    return aheadBuy;
}

Dry Run

prices = [1, 3, 2, 8, 4, 9], fee = 2, n = 6

ipricecurrBuy = max(−p + aheadSell, aheadBuy)currSell = max(p − 2 + aheadBuy, aheadSell)
6—00
59max(−9+0, 0) = 0max(9−2+0, 0) = 7
44max(−4+7, 0) = 3max(4−2+0, 7) = 7
38max(−8+7, 3) = 3max(8−2+3, 7) = 9
22max(−2+9, 3) = 7max(2−2+3, 9) = 9
13max(−3+9, 7) = 7max(3−2+7, 9) = 9
01max(−1+9, 7) = 8max(1−2+8, 9) = 9

Answer = 8 ✅

Fee ka asar dekho

i=4 pe currSell = 7 aaya — aur wo aheadSell (7) se aaya, na ki 4 - 2 + 0 = 2 se. Matlab din 4 pe ₹4 me bechna faayde ka nahi tha — fee kha jaati. Ruk ke din 5 pe ₹9 me bechna behtar raha.

Bina fee ke (Q36) same input pe answer 13 aata (2+6+5). Fee ne 5 kha liya — aur chhoti transactions ko poori tarah band kar diya.

🎉 Phase 5 complete

#SawaalStateQ36 se farak
35Stock I (1 txn)minPricecap = 1
36Stock II (infinite)i, buybaseline
37Stock III (2 txn)i, buy, capcap add
38Stock IV (k txn)i, buy, capcap = k
39Cooldowni, buysell → i+2
40Transaction Feei, buysell → −fee

Chhe sawaal, ek recurrence. Q36 ka code likh lo aur teen knobs yaad rakho: cap add karo (Q37/38), sell pe i+2 (Q39), sell pe -fee (Q40). Poora Phase 5 khatam.

Khud try karo

  1. fee = 0 daalo → Q36 ka answer (13) aana chahiye.
  2. Fee ko buy wali line me shift karo — same answer aata hai? (Haan.)
  3. Cooldown + fee dono wala version likho. Kaunsi do lines badalni padengi? (Dono sell wali line me — prices[i] - fee + dp[i+2][1].)

Phase 6 · Q41–Q47

LIS — Longest Increasing Subsequence

Ek naya dhaancha: dp[i] ka matlab hai "index i pe khatam hone wali best subsequence". Aur answer poore array ka maximum hota hai, aakhri cell nahi — bilkul Q27 (Common Substring) jaisa. Saat sawaal, aur chaar me sirf ek condition badalti hai.

Phase 6 core recurrence for i = 0 to n-1:
    dp[i] = 1  // akela element bhi ek subsequence hai

    for j = 0 to i-1:
        if (CONDITION(arr[j], arr[i]))
            dp[i] = max(dp[i], 1 + dp[j])

answer = max(dp[0..n-1])  // aakhri cell NAHI
Q41

Longest Increasing Subsequence

LeetCode 300 · Phase 6 ki neev

Conditionarr[j] < arr[i]
dp[i]i pe khatam
Answermax of all dp[]

Problem

Array me sabse lambi strictly increasing subsequence ki length.

nums = [10, 9, 2, 5, 3, 7, 101, 18] → 4 ([2, 3, 7, 101] ya [2, 3, 7, 18])

Soch 1 — take/notTake with prev index

Phase 3 wali soch: har element pe "loon ya na loon?". Par yahan ek naya sawaal bhi hai — "pichla kaunsa liya tha?", kyunki increasing rakhna hai.

Toh state = (index, prevIndex):

f(i, prev):
    if (i == n) return 0;

    notTake = 0 + f(i+1, prev);

    take = 0;
    if (prev == -1 || arr[i] > arr[prev])
        take = 1 + f(i+1, i);       // ab prev = i

    return max(take, notTake);
prev = −1 ka jhol

prev ki value -1 se n-1 tak jaati hai — aur dp[-1] possible nahi. Toh coordinate shift karna padta hai: dp[i][prev + 1], array size [n][n+1]. Ye kaam karta hai par ganda hai, aur O(n²) space leta hai.

Soch 2 — "i pe khatam" wala dhaancha (yahi seekho)

Phase 6 ka asli dhaancha

dp[i] = "index i pe khatam hone wali sabse lambi increasing subsequence ki length"

Iska faayda: state sirf ek parameter ka hai (i), aur prev ki zaroorat hi nahi — kyunki "i pe khatam" ka matlab hi hai ki arr[i] aakhri element hai.

dp[i] = 1 + max( dp[j] )   for all j < i where arr[j] < arr[i]

Aur agar koi bhi aisa j nahi mila, toh dp[i] = 1 (akela element).

Answer aakhri cell me kyun nahi hai

Kyunki sabse lambi subsequence kisi bhi index pe khatam ho sakti hai. Example me dp[7] = 4 hai (18 pe khatam) aur dp[6] = 4 bhi (101 pe). Par agar array [1,2,3,0] hota toh dp[3] = 1 hota aur answer dp[2] = 3 hota. Poori array scan karo.

Code

1Tabulation — O(n²)SC O(n)
static int lengthOfLIS(int[] nums) {
    int n = nums.length;

    int[] dp = new int[n];
    Arrays.fill(dp, 1);              // har element akela = length 1

    int ans = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {                // CONDITION
                dp[i] = Math.max(dp[i], 1 + dp[j]);
            }
        }

        ans = Math.max(ans, dp[i]);   // har i pe answer update
    }

    return ans;
}
2Memoization — take/notTake versionO(n²) / SC O(n²)
static int f(int i, int prev, int n, int[] nums, int[][] dp) {
    if (i == n) return 0;

    if (dp[i][prev + 1] != -1) return dp[i][prev + 1];   // shift

    int notTake = 0 + f(i + 1, prev, n, nums, dp);

    int take = 0;
    if (prev == -1 || nums[i] > nums[prev]) {
        take = 1 + f(i + 1, i, n, nums, dp);
    }

    return dp[i][prev + 1] = Math.max(take, notTake);
}

// call: f(0, -1, n, nums, dp)  with dp = new int[n][n+1]
Kaunsa likhna interview me

Version 1 — chhota, saaf, O(n) space, aur Q42–Q47 sab isi pe bante hain. Version 2 sirf tab likho jab interviewer specifically "recursion se derive karo" bole.

Dry Run

nums = [10, 9, 2, 5, 3, 7, 101, 18]

inums[i]Kaunse j chale (nums[j] < nums[i])1 + max(dp[j])dp[i]
010——1
19koi nahi (10 > 9)—1
22koi nahi—1
35j=2 (2<5), dp[2]=11+12
43j=2 (2<3), dp[2]=11+12
57j=2 (dp=1), j=3 (dp=2), j=4 (dp=2)1+23
6101j=0..5 sab, max dp = 3 (j=5)1+34
718j=0..5 (101 nahi), max dp = 3 (j=5)1+34
index01234567
nums109253710118
dp11122344

Answer = max(dp) = 4 ✅

Table ko padho

  • dp[0] = dp[1] = dp[2] = 1 — shuruaat me values girti ja rahi hain (10, 9, 2), toh koi chain banti hi nahi.
  • dp[5] = 3 — [2, 3, 7] ya [2, 5, 7]. Dono length 3.
  • dp[6] = dp[7] = 4 — do alag subsequences, dono length 4. DP ko farak nahi padta.
  • Aakhri cell dp[7] = 4 ittefaq se answer hai. nums = [10, 9, 2, 5, 3, 7, 101, 1] hota toh dp[7] = 1 hota par answer phir bhi 4.

Complexity

ApproachTimeSpace
Memoization (i, prev)O(n²)O(n²) + O(n)
Tabulation (i pe khatam)O(n²)O(n)
Binary search (Q43)O(n log n)O(n)

Khud try karo

  1. nums = [7,7,7,7] → 1. Condition < hai, ≤ nahi — strictly increasing.
  2. Condition ko ≤ kar do → non-decreasing LIS milegi. Same input pe ab 4 aayega.
  3. Longest Decreasing Subsequence — condition nums[j] > nums[i] kar do. Bas.
Q42

Print the LIS

GFG · hash array se backtrack

Extrahash[] array
TracklastIndex of max
TimeO(n²) + O(n)

Problem

Sirf length nahi, actual subsequence print karo.

nums = [10, 9, 2, 5, 3, 7, 101, 18] → [2, 3, 7, 18]

Soch — parent pointer rakho

Q41 me jab dp[i] update hota hai, hum bhool jaate hain ki kaunse j se aaya tha. Bas wahi yaad rakh lo.

ArrayMatlab
dp[i]i pe khatam hone wali LIS ki length
hash[i]kaunse index se aaya tha (parent). Agar koi nahi, toh i khud.

Phir lastIndex (jahan max mila) se shuru karke hash follow karte jao jab tak hash[i] == i na ho jaye. Bilkul linked list traverse karne jaisa.

Code

→dp + hash + backtrackO(n²)
static ArrayList<Integer> printLIS(int[] nums) {
    int n = nums.length;

    int[] dp   = new int[n];
    int[] hash = new int[n];

    Arrays.fill(dp, 1);

    int maxLen = 1, lastIndex = 0;

    for (int i = 0; i < n; i++) {
        hash[i] = i;                       // default: khud parent

        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && 1 + dp[j] > dp[i]) {
                dp[i]   = 1 + dp[j];
                hash[i] = j;               // parent yaad rakho
            }
        }

        if (dp[i] > maxLen) {
            maxLen    = dp[i];
            lastIndex = i;                 // answer kahan khatam hua
        }
    }

    // ---- backtrack ----
    ArrayList<Integer> lis = new ArrayList<>();

    lis.add(nums[lastIndex]);

    while (hash[lastIndex] != lastIndex) {
        lastIndex = hash[lastIndex];
        lis.add(nums[lastIndex]);
    }

    Collections.reverse(lis);              // ulta bana tha
    return lis;
}
Do chhote traps

1. Condition me 1 + dp[j] > dp[i] hona chahiye (≥ nahi). Warna barabar length pe bhi hash update hoga aur galat parent set ho jaayega.

2. hash[i] = i loop ke shuru me set karo, warna kuch indices ka hash 0 reh jaayega (Java default) aur backtrack galat chalega.

Dry Run

nums = [10, 9, 2, 5, 3, 7, 101, 18]

index01234567
nums109253710118
dp11122344
hash01222355

maxLen = 4, lastIndex = 6 (pehla jahan 4 mila — condition > hai, isliye index 7 se update nahi hua)

Backtrack trace

SteplastIndexnums[lastIndex]hash[lastIndex]lis (ulta)
161015[101]
2573[101, 7]
3352[101, 7, 5]
4222 (== khud)[101, 7, 5, 2]

reverse() → [2, 5, 7, 101] ✅

Length 4 ✅. Ye [2, 3, 7, 101] se alag hai par dono valid hain — hash[3] = 2 tha kyunki j=2 pehle mila tha. Multiple LIS ho toh koi bhi ek acceptable hai.

Khud try karo

  1. Condition ko 1 + dp[j] ≥ dp[i] kar do — kya output galat aata hai? Kaunse input pe?
  2. lastIndex track karne ki jagah end me dp array scan karo — same result aana chahiye.
  3. Saari LIS print karo (sirf ek nahi). Recursion + backtracking chahiye hoga.
Q43

LIS in O(n log n)

LeetCode 300 (optimal) · ye DP nahi hai — aur wahi seekhne wali baat hai

Techniquebinary search
TimeO(n log n)
Caveattemp ≠ actual LIS

Soch — ek greedy idea

Ek temp list rakho. Har naye element x ke liye:

  • Agar x temp ke aakhri element se bada hai → end me append karo (chain lambi ho gayi)
  • Warna → temp me sabse chhoti aisi value dhoondo jo x se ≥ hai, aur usko x se replace karo

Answer = temp.size()

Replace kyun karte hain

temp hamesha sorted rehti hai. Chhoti value se replace karne ka matlab: "utni hi lambi chain, par ab kam value pe khatam ho rahi hai" — jo aage aur elements jodne ke liye behtar hai. Chain ki length nahi badalti, sirf uska "potential" behtar hota hai.

Sabse zaroori caveat

temp ki length hamesha sahi hoti hai, par temp ke contents aksar actual LIS nahi hote! Replace hone ki wajah se andar mila-jula ho jaata hai. Agar actual subsequence chahiye toh Q42 (O(n²) + hash) hi use karo.

Code

→Binary searchO(n log n) / SC O(n)
static int lengthOfLIS(int[] nums) {
    ArrayList<Integer> temp = new ArrayList<>();

    temp.add(nums[0]);

    for (int i = 1; i < nums.length; i++) {

        if (nums[i] > temp.get(temp.size() - 1)) {
            temp.add(nums[i]);                    // chain lambi
        } else {
            // pehla index jahan temp[idx] ≥ nums[i]
            int idx = lowerBound(temp, nums[i]);
            temp.set(idx, nums[i]);               // replace
        }
    }

    return temp.size();
}

// lower_bound: pehla index jahan list.get(idx) ≥ target
static int lowerBound(ArrayList<Integer> list, int target) {
    int lo = 0, hi = list.size() - 1, ans = list.size();

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (list.get(mid) >= target) {
            ans = mid;
            hi  = mid - 1;
        } else {
            lo  = mid + 1;
        }
    }

    return ans;
}
Java shortcut

Arrays.binarySearch() use kar sakte ho, par wo not-found pe -(insertionPoint) - 1 return karta hai — usko decode karna padta hai. Interview me apna lowerBound likhna zyada saaf hai aur off-by-one bugs kam hote hain.

Dry Run

nums = [10, 9, 2, 5, 3, 7, 101, 18]

inums[i]temp (pehle)Actiontemp (baad me)
010[]init[10]
19[10]9 < 10 → replace idx 0[9]
22[9]2 < 9 → replace idx 0[2]
35[2]5 > 2 → append[2, 5]
43[2, 5]3 < 5 → replace idx 1[2, 3]
57[2, 3]7 > 3 → append[2, 3, 7]
6101[2, 3, 7]101 > 7 → append[2, 3, 7, 101]
718[2, 3, 7, 101]18 < 101 → replace idx 3[2, 3, 7, 18]

Answer = temp.size() = 4 ✅

Yahan temp sanyog se sahi LIS hai

[2, 3, 7, 18] sach me ek valid LIS hai. Par ye hamesha nahi hota. Dekho:

numsfinal tempsizeKya temp valid LIS hai?
[1, 2, 3][1, 2, 3]3haan
[3, 4, 5, 1][1, 4, 5]3nahi! (1 aakhir me tha)

[3, 4, 5, 1] me answer 3 sahi hai ([3,4,5]), par temp = [1, 4, 5] me 1 aakhri element tha — wo 4 aur 5 se pehle aa hi nahi sakta. Length sahi, contents galat. Yahi wo caveat hai.

Complexity

n elements, har ek pe O(log n) binary search → O(n log n). Space O(n).

Khud try karo

  1. [3, 4, 5, 1] chala ke temp print karo — upar wala caveat khud dekho.
  2. lowerBound ko upperBound (pehla > target) me badal do → non-decreasing LIS milegi. [7,7,7] pe test karo: 1 vs 3.
  3. Q41 (O(n²)) aur Q43 dono ko 10⁵ size ke random array pe chalao — time ka farak khud dekho.
Q44

Largest Divisible Subset

LeetCode 368 · LIS with a different condition

Pre-stepsort karo!
Conditionarr[i] % arr[j] == 0
BaakiQ42 ka code

Problem

Sabse bada subset dhoondo jisme har jodi (a, b) ke liye ya toh a % b == 0 ho ya b % a == 0.

nums = [1, 16, 7, 8, 4] → [1, 4, 8, 16] (size 4)

Soch — do insights

1 · Sort karna zaroori hai

Subset hai, subsequence nahi

Sawaal subset maangta hai — order matter nahi karta. Toh hum array ko sort kar sakte hain, aur usse problem "subsequence" ban jaati hai — jise hum LIS se solve kar sakte hain.

Ye Phase 3 ke Q15 wali "problem reduction" hi hai, bas ek sort ke saath.

2 · Sorted me sirf padosi check karna kaafi hai

Ye subtle hai. Agar list sorted hai aur har element apne pichle element se divisible hai, toh saare pairs automatically divisible ho jaate hain.

Kyunki divisibility transitive hai: 8 % 4 == 0 aur 4 % 1 == 0 → toh 8 % 1 == 0 bhi. Isliye chain me har consecutive pair check karna kaafi hai, saare pairs nahi.

Toh code Q42 ka hi hai, sirf:

Arrays.sort(nums);                        // ⚠️ naya

if (nums[i] % nums[j] == 0 && ...)        // condition badli
// Q41 me ye tha: if (nums[j] < nums[i] && ...)

Code

→Sort + LIS + hashO(n²)
static List<Integer> largestDivisibleSubset(int[] nums) {
    int n = nums.length;

    Arrays.sort(nums);                     // ⚠️ pehla step

    int[] dp   = new int[n];
    int[] hash = new int[n];
    Arrays.fill(dp, 1);

    int maxLen = 1, lastIndex = 0;

    for (int i = 0; i < n; i++) {
        hash[i] = i;

        for (int j = 0; j < i; j++) {
            if (nums[i] % nums[j] == 0 && 1 + dp[j] > dp[i]) {
                dp[i]   = 1 + dp[j];
                hash[i] = j;
            }
        }

        if (dp[i] > maxLen) {
            maxLen    = dp[i];
            lastIndex = i;
        }
    }

    // backtrack — Q42 jaisa
    List<Integer> ans = new ArrayList<>();
    ans.add(nums[lastIndex]);

    while (hash[lastIndex] != lastIndex) {
        lastIndex = hash[lastIndex];
        ans.add(nums[lastIndex]);
    }

    Collections.reverse(ans);
    return ans;
}

Dry Run

nums = [1, 16, 7, 8, 4] → sort → [1, 4, 7, 8, 16]

inums[i]Kaunse j pe divisibledp[i]hash[i]
01—10
14j=0 (4%1=0), dp[0]=120
27j=0 (7%1=0), dp[0]=120
38j=0 (dp=1), j=1 (8%4=0, dp=2)31
416j=0 (dp=1), j=1 (16%4=0, dp=2), j=3 (16%8=0, dp=3)43
index01234
nums (sorted)147816
dp12234
hash00013

maxLen = 4, lastIndex = 4

Backtrack

4 → hash[4]=3 → hash[3]=1 → hash[1]=0 → hash[0]=0 (ruk gaya)

Values: 16, 8, 4, 1 → reverse → [1, 4, 8, 16] ✅

Verify — saare pairs

PairDivisible?
4 % 10 ✅
8 % 10 ✅
8 % 40 ✅
16 % 1, 16 % 4, 16 % 8sab 0 ✅

Chhe pairs, sab divisible — aur humne code me sirf consecutive check kiye the. Transitivity ne baaki sambhal liya. 🎯

Khud try karo

  1. Arrays.sort() hata do — [1, 16, 7, 8, 4] pe kya aata hai? (Chhota answer, kyunki 4 aakhir me hai aur 16 use dekh hi nahi paata.)
  2. nums = [1, 2, 3] → [1, 2] ya [1, 3], size 2.
  3. Q42 ka code aur Q44 ka code side-by-side rakho — do line ka farak hai (sort + condition). Wahi Phase 6 ka poora sabak hai.
Q45

Longest String Chain

LeetCode 1048 · LIS with a custom predicate

Pre-stepsort by length
ConditionisPredecessor()
TimeO(n² × L)

Problem

Words ki list hai. wordA wordB ka predecessor hai agar wordA me exactly ek character kahin bhi insert karke wordB ban jaye.

Sabse lambi chain ki length nikalo.

words = ["a","b","ba","bca","bda","bdca"] → 4 ("a" → "ba" → "bda" → "bdca")

Soch

1 · Length ke hisaab se sort karo

Chain me har agla word exactly ek character bada hota hai. Toh agar length se sort kar dein, chain hamesha left-to-right chalegi — aur ye LIS ban jaayegi.

Arrays.sort(words, (a, b) -> a.length() - b.length());

2 · Condition ek helper function ban gayi

Q41 me condition nums[j] < nums[i] thi — ek comparison. Yahan wo ek function hai:

isPredecessor(s1, s2):
    // kya s1 me ek char daal ke s2 ban sakta hai?
    if (s2.length() != s1.length() + 1) return false;

    two pointers se check karo
Phase 6 ka pattern ab saaf dikhna chahiye

Q41 → Q44 → Q45: sirf condition badalti hai. Baaki dp loop, 1 + dp[j], max scan — sab identical. Condition chahe < ho, % ho, ya poora function — dhaancha wahi.

isPredecessor kaise likhein

Do pointer chalao. Jab mismatch mile, ek baar lambi string ka pointer aage badhao (wahi insert kiya hua character hai). Doosri baar mismatch mila toh false.

Code

→Sort + LIS + predicateO(n² × L)
static boolean isPredecessor(String s1, String s2) {
    // s1 chhota, s2 bada — exactly 1 char ka farak
    if (s2.length() != s1.length() + 1) return false;

    int i = 0, j = 0;
    boolean skipped = false;

    while (i < s1.length() && j < s2.length()) {

        if (s1.charAt(i) == s2.charAt(j)) {
            i++; j++;
        } else {
            if (skipped) return false;    // doosra mismatch → nahi
            skipped = true;
            j++;                          // bade wale ka char skip
        }
    }

    return true;
}

static int longestStrChain(String[] words) {
    int n = words.length;

    Arrays.sort(words, (a, b) -> a.length() - b.length());

    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int ans = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {

            if (isPredecessor(words[j], words[i]) && 1 + dp[j] > dp[i]) {
                dp[i] = 1 + dp[j];
            }
        }

        ans = Math.max(ans, dp[i]);
    }

    return ans;
}
Ek chhota simplification

while loop ke baad seedha return true kar diya. Kyun safe hai? Kyunki length ka check pehle hi ho chuka hai (s2 = s1 + 1), toh i ke khatam hone pe j me zyada se zyada ek character bacha hoga — aur wo hi insert kiya hua hai.

Dry Run

words = ["a","b","ba","bca","bda","bdca"] — already length-sorted

iwordKaunse j predecessor haindp[i]
0"a"—1
1"b"koi nahi (same length)1
2"ba"j=0 ("a"→"ba" ✅), j=1 ("b"→"ba" ✅)2
3"bca"j=2 ("ba"→"bca" ✅), dp[2]=23
4"bda"j=2 ("ba"→"bda" ✅), dp[2]=23
5"bdca"j=3 ("bca"→"bdca" ✅ dp=3), j=4 ("bda"→"bdca" ✅ dp=3)4
wordabbabcabdabdca
dp112334

Answer = 4 ✅ — chain: "a" → "ba" → "bda" → "bdca"

isPredecessor("ba", "bda") ka trace

i, js1[i]s2[j]Match?Action
0, 0bb✅i→1, j→1
1, 1ad❌skipped=true, j→2
1, 2aa✅i→2, j→3
2, 3i == s1.length() → loop khatamreturn true ✅

Complexity

O(n log n) sort + O(n²) dp loops × O(L) per isPredecessor = O(n² × L), jahan L = max word length.

Ek faster alternative

HashMap se bhi hota hai: har word ke liye uske saare possible predecessors (ek char hata ke) generate karo aur map me dhoondo. O(n × L²) — bade n pe zyada tez. Par interview me LIS version likhna kaafi hai, aur pattern recognition dikhata hai.

Khud try karo

  1. Sort hata do — ["bdca","bda","ba","a"] pe kya aata hai? (1, kyunki chain ulti direction me hai.)
  2. Actual chain print karo — Q42 wala hash[] laga do.
  3. HashMap wala O(n × L²) version likho aur dono ka time compare karo.
Q46

Longest Bitonic Subsequence

GFG · do LIS, ulti disha me

dp1LIS left → right
dp2LIS right → left
Answermax(dp1[i]+dp2[i]−1)

Problem

Bitonic subsequence = pehle strictly badhti hai, phir strictly ghatti hai. (Sirf badhti ya sirf ghatti bhi valid hai.)

nums = [1, 2, 1, 2, 1] → 3 ([1, 2, 1])

nums = [1, 11, 2, 10, 4, 5, 2, 1] → 6 ([1, 2, 10, 4, 2, 1])

Soch — peak ko fix karo

Poora sawaal ek line me

Har bitonic subsequence ka ek peak hota hai. Toh har index i ko peak maan ke dekho:

bitonic(i) = (i pe khatam hone wali LIS) + (i se shuru hone wali LDS) − 1

−1 kyun? Kyunki peak dono me count ho jaata hai. Ek baar ghata do.

ArrayMatlabKaise bhare
dp1[i]i pe khatam hone wali LIS (badhti hui)Q41 seedha, left → right
dp2[i]i se shuru hone wali LDS (ghatti hui)Q41 ulta, right → left
dp2 ko aise socho

"i se shuru hone wali decreasing" = "array ko ulta karke i pe khatam hone wali increasing". Isliye same Q41 code, bas dono loops ulti direction me.

Code

→Do LIS + combineO(n²) / SC O(n)
static int longestBitonicSequence(int[] nums, int n) {

    int[] dp1 = new int[n];    // i pe khatam, badhti hui
    int[] dp2 = new int[n];    // i se shuru, ghatti hui

    Arrays.fill(dp1, 1);
    Arrays.fill(dp2, 1);

    // ---- LIS left to right ----
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp1[i] = Math.max(dp1[i], 1 + dp1[j]);
            }
        }
    }

    // ---- LIS right to left (= LDS) ----
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (nums[j] < nums[i]) {
                dp2[i] = Math.max(dp2[i], 1 + dp2[j]);
            }
        }
    }

    // ---- har index ko peak maan ke dekho ----
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = Math.max(ans, dp1[i] + dp2[i] - 1);
    }

    return ans;
}
Dono loops me condition same hai

Dono jagah nums[j] < nums[i] hai — ye galti nahi hai. Doosre loop me j > i hai (right side), toh nums[j] < nums[i] ka matlab banta hai "i ke baad wali value chhoti hai" = ghatti hui. Direction ne condition ka matlab palat diya.

Dry Run

nums = [1, 11, 2, 10, 4, 5, 2, 1], n = 8

dp1 — LIS left to right

index01234567
nums1112104521
dp112233421

dp1[3] = 3 → [1, 2, 10]  ·  dp1[5] = 4 → [1, 2, 4, 5]

dp2 — LDS right to left

index01234567
nums1112104521
dp215343321

dp2[3] = 4 → [10, 4, 2, 1]  ·  dp2[1] = 5 → [11, 10, 4, 2, 1]

Combine — har index peak

inums[i]dp1[i]dp2[i]sum − 1
01111
111256
22234
310346
44335
55436
62223
71111

Answer = 6 ✅

Teen alag peaks, same answer

PeakSubsequence
i=1 (11)[1, 11] + [11, 10, 4, 2, 1] = [1, 11, 10, 4, 2, 1]
i=3 (10)[1, 2, 10] + [10, 4, 2, 1] = [1, 2, 10, 4, 2, 1]
i=5 (5)[1, 2, 4, 5] + [5, 2, 1] = [1, 2, 4, 5, 2, 1]

Teeno length 6 hain. DP ko farak nahi padta — wo bas maximum batata hai.

Khud try karo

  1. nums = [1, 2, 3, 4] (sirf badhti) → 4. dp2 sab 1 hoga.
  2. −1 hata do — answer 7 aayega. Peak do baar gina gaya.
  3. Kuch definitions me bitonic ke liye dono hisse zaroori hote hain (sirf increasing valid nahi). Us case me condition kya lagegi? (dp1[i] > 1 && dp2[i] > 1)
Q47

Number of Longest Increasing Subsequences

LeetCode 673 · Phase 6 ka finale — do arrays chahiye

dp[i]length at i
cnt[i]count at i
Combine> vs == alag

Problem

Kitni longest increasing subsequences hain? (Length nahi, ginti.)

nums = [1, 3, 5, 4, 7] → 2 ([1,3,5,7] aur [1,3,4,7])

nums = [2, 2, 2, 2, 2] → 5 (LIS length 1, aur paanch alag single elements)

Soch — do arrays saath-saath

ArrayMatlab
dp[i]i pe khatam hone wali LIS ki length
cnt[i]utni hi length wali kitni subsequences hain jo i pe khatam hoti hain

Do cases — yahi poora sawaal hai

Jab nums[j] < nums[i] ho:

Case A — nayi lambi chain mili

1 + dp[j] > dp[i]

Purani length beat ho gayi. Toh length update karo, aur count ko reset karo (purani counts ab bekaar hain):

dp[i]  = 1 + dp[j];
cnt[i] = cnt[j];        // reset, += nahi
Case B — barabar length ka doosra raasta

1 + dp[j] == dp[i]

Utni hi lambi chain, par alag raaste se. Toh length wahi rehti hai, aur count jud jaata hai:

cnt[i] += cnt[j];       // = nahi, +=
Yahi wo jagah hai jahan sab galti karte hain

> pe = lagta hai aur == pe +=. Ulta kar diya toh counts galat aayenge, par length sahi aayegi — toh bug pakadna mushkil hota hai. Yaad rakho: nayi length → reset. Barabar length → add.

Final answer

maxLen nikalo, phir saare i ka cnt[i] jodo jahan dp[i] == maxLen. Ek hi index kaafi nahi — multiple indices pe LIS khatam ho sakti hai.

Code

→dp + cntO(n²) / SC O(n)
static int findNumberOfLIS(int[] nums) {
    int n = nums.length;

    int[] dp  = new int[n];
    int[] cnt = new int[n];

    Arrays.fill(dp, 1);
    Arrays.fill(cnt, 1);      // har element akela = 1 tareeka

    int maxLen = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {

                if (1 + dp[j] > dp[i]) {          // Case A
                    dp[i]  = 1 + dp[j];
                    cnt[i] = cnt[j];              // reset
                }
                else if (1 + dp[j] == dp[i]) {    // Case B
                    cnt[i] += cnt[j];             // add
                }
            }
        }

        maxLen = Math.max(maxLen, dp[i]);
    }

    // saare indices jahan maxLen khatam hui
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] == maxLen) total += cnt[i];
    }

    return total;
}

Dry Run

nums = [1, 3, 5, 4, 7]

inums[i]jCasedp[i]cnt[i]
01——11
13j=0: 1+1 > 1 ✅A21
25j=0: 1+1 > 1 ✅A21
  j=1: 1+2 > 2 ✅A31
34j=0: 1+1 > 1 ✅A21
  j=1: 1+2 > 2 ✅A31
  j=2: 5 > 4, skip—31
47j=0: 1+1 > 1 ✅A21
  j=1: 1+2 > 2 ✅A31
  j=2: 1+3 > 3 ✅A41
  j=3: 1+3 == 4 ✅B42
index01234
nums13547
dp12334
cnt11112

maxLen = 4. Sirf i = 4 pe dp[i] == 4. Toh total = cnt[4] = 2 ✅

Case B wala moment

i=4, j=3 pe: dp[3] = 3 (chain [1,3,4]) aur dp[4] already 4 tha (chain [1,3,5,7] se). 1 + 3 == 4 → Case B → cnt[4] += cnt[3] → 1 + 1 = 2.

Do chains: [1,3,5,7] aur [1,3,4,7] ✅

Doosra example — sab barabar

nums = [2,2,2,2,2]: koi nums[j] < nums[i] nahi, toh sab dp[i] = 1, cnt[i] = 1. maxLen = 1, aur paanchon indices pe dp[i] == 1 → total = 5 ✅

Yahi wo case hai jahan final scan zaroori hai — ek index dekh ke 1 aa jaata.

🎉 Phase 6 complete

#SawaalPre-stepConditionExtra
41LIS—arr[j] < arr[i]—
42Print LIS—samehash[] + backtrack
43LIS O(n log n)—binary search — DP nahi
44Divisible Subsetsortarr[i] % arr[j] == 0hash[]
45String Chainsort by lengthisPredecessor()—
46Bitonic—same, dono dishadp1 + dp2 − 1
47Number of LIS—samecnt[] array

Saat sawaal, ek loop. Q41 ka 10-line ka code likh lo. Baaki sab me ya toh condition badalti hai (Q44, Q45), ya ek extra array add hota hai (Q42, Q46, Q47).

Khud try karo

  1. Case A me cnt[i] = cnt[j] ki jagah cnt[i] += cnt[j] kar do — kaunsa input galat aayega? [1,3,5,4,7] pe test karo.
  2. Final scan hata ke sirf cnt[lastMaxIndex] return karo — [2,2,2,2,2] pe 1 aayega (galat).
  3. Ye O(n log n) me bhi hota hai (segment tree se). Bahut advanced hai — par soch ke dekho ki count ko binary search ke saath kaise maintain karoge.

Phase 7 · Q48–Q53

MCM / Partition DP

Phase ka sabse tedha hissa — aur sabse zyada "aha" moments wala. State ab ek index nahi, ek interval (i, j) hai. Aur us interval ke andar hum har possible jagah pe todte hain, dono tukdon ko recursively solve karte hain, aur best combination lete hain.

Phase 7 core recurrence — interval partition f(i, j):  // i se j tak ka interval
    if (i == j) return BASE  // ek hi element

    best = INIT
    for k = i to j-1:  // har jagah todo
        steps = f(i, k) + f(k+1, j) + COST(i, k, j)
        best = min/max(best, steps)

    return best
// Tabulation: i ULTA (n-1 → 0), j SEEDHA (i+1 → n-1)
Q48

Matrix Chain Multiplication

GFG classic · poore phase ka naam isi pe hai

Combinemin
Costarr[i-1]×arr[k]×arr[j]
Basei == j → 0

Problem

Array arr[] me matrices ke dimensions hain. n elements ka matlab n-1 matrices:

Matrix i ka size = arr[i-1] × arr[i]

Matrix multiplication associative hai — bracket kahin bhi laga sakte ho, answer wahi. Par operations ki ginti badal jaati hai. Minimum operations nikalo.

arr = [10, 20, 30, 40, 50] → 4 matrices: A(10×20), B(20×30), C(30×40), D(40×50) → answer 38000

Yaad dilao: cost kaise nikalta hai

(a × b) aur (b × c) ko multiply karne me a × b × c operations lagte hain, aur result (a × c) hota hai.

Soch — bracket kahan lagayein

Q41 tak har sawaal me hum "index pe kya karna hai" soch rahe the. Yahan sawaal alag hai: "is chain ko kahan todun?"

f(i, j) = "matrix i se matrix j tak multiply karne ka minimum cost"

Chain i..j ko kisi bhi k pe tod sakte ho:

(A_i ... A_k) × (A_k+1 ... A_j)
  • Left tukda solve karo → f(i, k), result size arr[i-1] × arr[k]
  • Right tukda solve karo → f(k+1, j), result size arr[k] × arr[j]
  • Ab in dono ko multiply karo → cost arr[i-1] × arr[k] × arr[j]
f(i, j) = min over k = i to j-1 of
              f(i, k) + f(k+1, j) + arr[i-1] * arr[k] * arr[j]
Indexing — yahan sabse zyada log fasste hain

Matrices 1 se n-1 tak number hoti hain, 0 se nahi. Kyunki matrix i ke liye arr[i-1] chahiye — aur arr[-1] hota nahi.

Toh initial call: f(1, n-1), na ki f(0, n-1).

Base case

if (i == j) return 0;    // ek hi matrix, multiply karne ko kuch nahi

Code

1MemoizationO(n³)
static int f(int i, int j, int[] arr, int[][] dp) {
    if (i == j) return 0;

    if (dp[i][j] != -1) return dp[i][j];

    int mini = Integer.MAX_VALUE;

    for (int k = i; k <= j - 1; k++) {

        int steps = arr[i - 1] * arr[k] * arr[j]
                  + f(i, k, arr, dp)
                  + f(k + 1, j, arr, dp);

        mini = Math.min(mini, steps);
    }

    return dp[i][j] = mini;
}

// driver
int n = arr.length;
int[][] dp = new int[n][n];
for (int[] row : dp) Arrays.fill(row, -1);
System.out.println(f(1, n - 1, arr, dp));
2TabulationO(n³) / SC O(n²)
static int matrixMultiplication(int[] arr, int n) {
    int[][] dp = new int[n][n];

    // base: i == j → 0 (Java default ✅)

    for (int i = n - 1; i >= 1; i--) {          // ⚠️ i ULTA
        for (int j = i + 1; j < n; j++) {      // ⚠️ j SEEDHA, i+1 se

            int mini = Integer.MAX_VALUE;

            for (int k = i; k <= j - 1; k++) {
                int steps = arr[i - 1] * arr[k] * arr[j]
                          + dp[i][k]
                          + dp[k + 1][j];

                mini = Math.min(mini, steps);
            }

            dp[i][j] = mini;
        }
    }

    return dp[1][n - 1];
}
Loop directions — Phase 7 ka sabse zaroori rule

dp[i][j] ko chahiye dp[i][k] (same row, chhota j) aur dp[k+1][j] (bada i wali row).

Toh i ulta chalao (badi rows pehle bharo) aur j seedha (chhote j pehle). Ye do direction har Phase 7 sawaal me same rahengi — ratt lo.

Aur j hamesha i+1 se shuru hota hai, kyunki j < i wala aadha table use hi nahi hota. Sirf upper triangle bharti hai.

Dry Run

arr = [10, 20, 30, 40, 50], n = 5. Matrices: A(10×20), B(20×30), C(30×40), D(40×50)

Length 2 chains

CellChainCost = arr[i−1]×arr[k]×arr[j]dp
dp[1][2]A×B10×20×306000
dp[2][3]B×C20×30×4024000
dp[3][4]C×D30×40×5060000

Length 3 chains

dp[1][3] (A×B×C), do tareeke:

kBracketdp[1][k] + dp[k+1][3] + costTotal
1A × (BC)0 + 24000 + 10×20×4032000 ✅
2(AB) × C6000 + 0 + 10×30×4018000 ✅

dp[1][3] = min(32000, 18000) = 18000

dp[2][4] (B×C×D):

kBracketCalculationTotal
2B × (CD)0 + 60000 + 20×30×5090000
3(BC) × D24000 + 0 + 20×40×5064000 ✅

dp[2][4] = 64000

Final — dp[1][4] (poori chain)

kBracketdp[1][k] + dp[k+1][4] + arr[0]×arr[k]×arr[4]Total
1A × (BCD)0 + 64000 + 10×20×50 = 0 + 64000 + 1000074000
2(AB) × (CD)6000 + 60000 + 10×30×50 = 6000+60000+1500081000
3(ABC) × D18000 + 0 + 10×40×50 = 18000+0+2000038000 ✅

Answer = 38000 ✅ — best bracketing: ((A×B)×C)×D

Poori table

i \ j1234
1060001800038000
2—02400064000
3——060000
4———0

Sirf upper triangle bhari — aur diagonal poori zeros. Ye Phase 7 ki har table ki shakl hai.

Complexity

O(n²) states, har state pe O(n) ka k loop → O(n³). Space O(n²).

Space optimization possible nahi — dp[i][j] ko poore table se cells chahiye, sirf ek row se kaam nahi chalta. Ye Phase 7 ki general baat hai.

Khud try karo

  1. f(0, n-1) se call karke dekho — arr[-1] pe crash. Isliye 1 se shuru hota hai.
  2. Tabulation me i ko seedha chala do — galat answer aayega (cells abhi tak nahi bhari hongi).
  3. Best bracketing print karo: ((AB)C)D. Hint: har cell ke liye best k yaad rakho, phir recursively print karo.
Q49

Minimum Cost to Cut a Stick

LeetCode 1547 (hard) · MCM ka twin

Pre-step0 aur n daalo, sort
Costcuts[j+1] − cuts[i-1]
k rangei to j (j-1 nahi)

Problem

n length ka stick hai. cuts[] array me positions hain jahan cut karna hai. Har cut ka cost = us waqt ke stick ke tukde ki length.

Cuts kisi bhi order me kar sakte ho. Minimum total cost?

n = 7, cuts = [1, 3, 4, 5] → 16

Soch — do preprocessing steps

1 · Array me 0 aur n daalo, phir sort

Kyun

Har tukde ki length nikalne ke liye uske dono kinare chahiye. Stick ke aakhri kinare 0 aur n hain — wo cuts me nahi hain, par length calculate karne ke liye zaroori hain.

Aur sort isliye ki cuts left-to-right order me hon — tabhi interval DP ka matlab banta hai.

cuts = [1,3,4,5] → [0, 1, 3, 4, 5, 7] (size m = 6)

2 · Ulta socho — ye MCM jaisa hi hai

f(i, j) = "cuts i se j tak karne ka minimum cost, jab stick ka tukda cuts[i-1] se cuts[j+1] tak hai"

Us tukde me pehla cut kaunsa lagayein? Har k try karo:

cost = cuts[j+1] - cuts[i-1]     // abhi ke tukde ki poori length
     + f(i, k-1)                  // left me bache cuts
     + f(k+1, j)                  // right me bache cuts
MCM se do farak

1. Cost k pe depend nahi karta — wo poore interval ki length hai. MCM me cost arr[k] pe depend karti thi.

2. k ka loop i se j tak jaata hai (j-1 nahi), kyunki k khud ek cut hai jo consume ho jaata hai — MCM me k ek split point tha jo dono taraf rehta tha.

Base case

if (i > j) return 0;    // koi cut baaki nahi

Code

1MemoizationO(m³)
static int f(int i, int j, int[] cuts, int[][] dp) {
    if (i > j) return 0;

    if (dp[i][j] != -1) return dp[i][j];

    int mini = Integer.MAX_VALUE;

    for (int k = i; k <= j; k++) {

        int cost = cuts[j + 1] - cuts[i - 1]
                 + f(i, k - 1, cuts, dp)
                 + f(k + 1, j, cuts, dp);

        mini = Math.min(mini, cost);
    }

    return dp[i][j] = mini;
}

static int minCost(int n, int[] cuts) {
    int c = cuts.length;

    int[] arr = new int[c + 2];
    arr[0] = 0;  arr[c + 1] = n;
    for (int i = 0; i < c; i++) arr[i + 1] = cuts[i];

    Arrays.sort(arr);

    int[][] dp = new int[c + 1][c + 1];
    for (int[] row : dp) Arrays.fill(row, -1);

    return f(1, c, arr, dp);
}
2TabulationO(m³) / SC O(m²)
static int minCost(int n, int[] cuts) {
    int c = cuts.length;

    int[] arr = new int[c + 2];
    arr[0] = 0;  arr[c + 1] = n;
    for (int i = 0; i < c; i++) arr[i + 1] = cuts[i];
    Arrays.sort(arr);

    int[][] dp = new int[c + 2][c + 2];

    for (int i = c; i >= 1; i--) {              // i ULTA
        for (int j = 1; j <= c; j++) {          // j SEEDHA

            if (i > j) continue;                // base case

            int mini = Integer.MAX_VALUE;

            for (int k = i; k <= j; k++) {
                int cost = arr[j + 1] - arr[i - 1]
                         + dp[i][k - 1]
                         + dp[k + 1][j];

                mini = Math.min(mini, cost);
            }

            dp[i][j] = mini;
        }
    }

    return dp[1][c];
}

Dry Run

n = 7, cuts = [1, 3, 4, 5] → arr = [0, 1, 3, 4, 5, 7], c = 4

Length 1 intervals (single cut)

CellCut atTukdacost = arr[j+1] − arr[i−1]
dp[1][1]10 → 33 − 0 = 3
dp[2][2]31 → 44 − 1 = 3
dp[3][3]43 → 55 − 3 = 2
dp[4][4]54 → 77 − 4 = 3

Length 2 intervals

dp[1][2] (cuts 1 aur 3, tukda 0→4, length 4):

k4 + dp[1][k−1] + dp[k+1][2]Total
14 + dp[1][0]=0 + dp[2][2]=37 ✅
24 + dp[1][1]=3 + dp[3][2]=07 ✅

dp[1][2] = 7

Similarly: dp[2][3] = tukda 1→5 (length 4) + best = 6  ·  dp[3][4] = tukda 3→7 (length 4) + best = 6

Final — dp[1][4] (tukda 0→7, length 7)

kPehla cut7 + dp[1][k−1] + dp[k+1][4]Total
1at 17 + 0 + dp[2][4]7 + 0 + 9 = 16 ✅
2at 37 + dp[1][1]=3 + dp[3][4]=67 + 3 + 6 = 16 ✅
3at 47 + dp[1][2]=7 + dp[4][4]=317
4at 57 + dp[1][3] + 07 + 10 = 17

Answer = 16 ✅

Verify — ek optimal order

StepCut atTukdaCostRunning total
130→7 (length 7)77
210→3 (length 3)310
343→7 (length 4)414
454→7 (length 3)216 ✅

Dhyaan do: pehle beech me cut karne se aage ke tukde chhote ho gaye. Greedy "sabse chhota tukda pehle" yahan kaam nahi karta — isliye DP chahiye.

Khud try karo

  1. 0 aur n daalna bhool jao — arr[i-1] pe crash ya galat cost. Test karo.
  2. Arrays.sort() hata do — cuts = [5,1,4,3] pe galat answer.
  3. Q48 aur Q49 ka k loop compare karo: k ≤ j-1 vs k ≤ j. Socho ki dono me k ka matlab kaise alag hai.
Q50

Burst Balloons

LeetCode 312 (hard) · Phase 7 ka sabse khoobsurat sawaal

Combinemax
TrickULTA socho — last burst
Costa[i-1]×a[k]×a[j+1]

Problem

nums[] me balloons hain. Balloon i phodne pe nums[i-1] × nums[i] × nums[i+1] coins milte hain. Phodne ke baad wo balloon gayab ho jaata hai aur padosi jud jaate hain.

Array ke bahar imaginary 1 maano. Maximum coins?

nums = [3, 1, 5, 8] → 167

Soch — seedha sochna kyun FAIL hota hai

Pehla instinct galat hai

Instinct: "balloon k ko pehle phodta hoon, phir left aur right ko alag-alag solve karta hoon."

Problem: k phodne ke baad uske padosi jud jaate hain. Ab left aur right ke tukde independent nahi rahe — left ka aakhri balloon right ke pehle balloon ka padosi ban gaya.

Aur DP tabhi kaam karta hai jab subproblems independent hon. Toh ye soch tootti hai. 💀

Ulti soch — poore Phase 7 ka sabse bada insight

Sawaal palat do: "balloon k ko SABSE AAKHIR me phodta hoon."

Agar k aakhri hai, toh jab uski baari aayegi tab uske dono taraf sirf interval ke boundaries bachi hongi — nums[i-1] aur nums[j+1]. Ye fixed hain, kyunki wo interval ke bahar hain aur abhi phoote nahi.

Aur ab left tukda (i..k-1) aur right tukda (k+1..j) bilkul independent hain. ✅

f(i, j) = max over k = i to j of
              nums[i-1] * nums[k] * nums[j+1]    // k aakhri me phoota
            + f(i, k-1)                          // left, pehle
            + f(k+1, j)                          // right, pehle

Preprocessing

Array ke dono taraf 1 daal do — taaki nums[i-1] aur nums[j+1] hamesha valid rahen. (Q49 me 0 aur n daale the — wahi idea.)

[3,1,5,8] → [1, 3, 1, 5, 8, 1]

Base case

if (i > j) return 0;

Code

1MemoizationO(n³)
static int f(int i, int j, int[] a, int[][] dp) {
    if (i > j) return 0;

    if (dp[i][j] != -1) return dp[i][j];

    int maxi = Integer.MIN_VALUE;

    for (int k = i; k <= j; k++) {

        int coins = a[i - 1] * a[k] * a[j + 1]   // k AAKHRI me
                  + f(i, k - 1, a, dp)
                  + f(k + 1, j, a, dp);

        maxi = Math.max(maxi, coins);
    }

    return dp[i][j] = maxi;
}

static int maxCoins(int[] nums) {
    int n = nums.length;

    int[] a = new int[n + 2];
    a[0] = 1;  a[n + 1] = 1;                     // dono taraf 1
    for (int i = 0; i < n; i++) a[i + 1] = nums[i];

    int[][] dp = new int[n + 2][n + 2];
    for (int[] row : dp) Arrays.fill(row, -1);

    return f(1, n, a, dp);
}
2TabulationO(n³) / SC O(n²)
static int maxCoins(int[] nums) {
    int n = nums.length;

    int[] a = new int[n + 2];
    a[0] = 1;  a[n + 1] = 1;
    for (int i = 0; i < n; i++) a[i + 1] = nums[i];

    int[][] dp = new int[n + 2][n + 2];

    for (int i = n; i >= 1; i--) {              // i ULTA
        for (int j = 1; j <= n; j++) {          // j SEEDHA

            if (i > j) continue;

            int maxi = Integer.MIN_VALUE;

            for (int k = i; k <= j; k++) {
                int coins = a[i - 1] * a[k] * a[j + 1]
                          + dp[i][k - 1]
                          + dp[k + 1][j];

                maxi = Math.max(maxi, coins);
            }

            dp[i][j] = maxi;
        }
    }

    return dp[1][n];
}

Dry Run

nums = [3, 1, 5, 8] → a = [1, 3, 1, 5, 8, 1] (indices 0–5), n = 4

Length 1 intervals

Cellka[i−1] × a[k] × a[j+1]dp
dp[1][1]11 × 3 × 13
dp[2][2]23 × 1 × 515
dp[3][3]31 × 5 × 840
dp[4][4]45 × 8 × 140

Length 2 intervals

dp[1][2] (balloons 3, 1 — boundaries a[0]=1, a[3]=5):

kAakhri phootaa[0]×a[k]×a[3] + dp[1][k−1] + dp[k+1][2]Total
131×3×5 + 0 + dp[2][2]=1515 + 15 = 30 ✅
211×1×5 + dp[1][1]=3 + 05 + 3 = 8

dp[1][2] = 30

Similarly: dp[2][3] = 135, dp[3][4] = 48

Length 3

dp[1][3] = 159  ·  dp[2][4] = 159

Final — dp[1][4]

kAakhri phootaa[0]×a[k]×a[5] + dp[1][k−1] + dp[k+1][4]Total
131×3×1 + 0 + dp[2][4]=1593 + 159 = 162
211×1×1 + dp[1][1]=3 + dp[3][4]=481 + 51 = 52
351×5×1 + dp[1][2]=30 + dp[4][4]=405 + 70 = 75
481×8×1 + dp[1][3]=159 + 08 + 159 = 167 ✅

Answer = 167 ✅

Order verify karo

k=4 jeeta — matlab balloon 8 sabse aakhir me phoota. Uske pehle sab kuch dp[1][3] me hua.

StepPhodaArrayCoinsTotal
11[3, 1, 5, 8] → [3,5,8]3×1×5 = 1515
25[3, 5, 8] → [3,8]3×5×8 = 120135
33[3, 8] → [8]1×3×8 = 24159
48[8] → []1×8×1 = 8167 ✅

Dhyaan do: sabse bada balloon (8) aakhir me phoota — taaki wo doosron ke multiplication me baar-baar kaam aata rahe. Ye greedy se nikalna namumkin tha.

Khud try karo

  1. "Pehle phodo" wali soch se code likho aur [3,1,5,8] pe chalao — galat answer aayega. Ye khud dekhna zaroori hai.
  2. Q49 aur Q50 ka code side-by-side rakho. Structure bilkul same hai — sirf cost formula aur min/max ka farak.
  3. nums = [1, 5] → 10. Haath se verify karo.
Q51

Evaluate Boolean Expression to True

GFG / LeetCode variant · interval DP + ek teesra state

Combine+ (count)
Statei, j, isTrue
ksirf operators pe

Problem

Ek boolean expression string hai jisme T, F, aur operators &, |, ^ hain. Kitne tareeke se brackets laga sakte ho taaki expression True evaluate ho?

exp = "T|T&F^T" → 4

Soch — Phase 7 + ek naya state

MCM ki tarah har jagah tod sakte hain. Par yahan k sirf operators pe ho sakta hai — operands pe nahi.

String ka structure

Expression hamesha operand operator operand operator ... hota hai. Toh even index pe operands (T/F) aur odd index pe operators. Isliye k loop i+1 se shuru hota hai aur 2 ke step me chalta hai.

Naya state: isTrue

Sirf "kitne tareeke True" ginna kaafi nahi. Kyunki & ke liye humein pata hona chahiye ki left kitne tareeke se True hai aur right kitne tareeke se True hai. Aur | ke liye False wale counts bhi chahiye.

Toh state: f(i, j, isTrue) = "exp[i..j] ko isTrue banane ke kitne tareeke"

Har operator ke rules

Maan lo lT, lF = left ke True/False ways, aur rT, rF = right ke.

OperatorTrue waysFalse ways
& (AND)lT × rTlT×rF + lF×rT + lF×rF
| (OR)lT×rT + lT×rF + lF×rTlF × rF
^ (XOR)lT×rF + lF×rTlT×rT + lF×rF

Multiply kyun? Kyunki left ke har tareeke ko right ke har tareeke ke saath jod sakte ho — combinations. Aur alag-alag k ke results judte hain (+).

Base case

if (i == j) {
    if (isTrue == 1) return exp.charAt(i) == 'T' ? 1 : 0;
    else             return exp.charAt(i) == 'F' ? 1 : 0;
}

Code

→Memoization — 3D dpO(n² × 2 × n)
static final int MOD = 1000000007;

static long f(int i, int j, int isTrue, String exp, long[][][] dp) {
    if (i > j) return 0;

    if (i == j) {
        if (isTrue == 1) return exp.charAt(i) == 'T' ? 1 : 0;
        else             return exp.charAt(i) == 'F' ? 1 : 0;
    }

    if (dp[i][j][isTrue] != -1) return dp[i][j][isTrue];

    long ways = 0;

    for (int k = i + 1; k <= j - 1; k += 2) {     // sirf operators

        long lT = f(i, k - 1, 1, exp, dp);
        long lF = f(i, k - 1, 0, exp, dp);
        long rT = f(k + 1, j, 1, exp, dp);
        long rF = f(k + 1, j, 0, exp, dp);

        char op = exp.charAt(k);

        if (op == '&') {
            if (isTrue == 1) ways += lT * rT;
            else             ways += lT * rF + lF * rT + lF * rF;
        }
        else if (op == '|') {
            if (isTrue == 1) ways += lT * rT + lT * rF + lF * rT;
            else             ways += lF * rF;
        }
        else {                                    // '^'
            if (isTrue == 1) ways += lT * rF + lF * rT;
            else             ways += lT * rT + lF * rF;
        }

        ways %= MOD;
    }

    return dp[i][j][isTrue] = ways;
}

// driver
int n = exp.length();
long[][][] dp = new long[n][n][2];
for (long[][] a : dp) for (long[] b : a) Arrays.fill(b, -1);
System.out.println(f(0, n - 1, 1, exp, dp));
Do zaroori details

1. k += 2 — agar k++ likha toh operands pe bhi todne ki koshish karega aur galat/crash.

2. long aur MOD — counts multiply hote hain, toh tezi se overflow. Har iteration me % MOD lagao.

Dry Run

exp = "T|T&F^T", indices: T(0) |(1) T(2) &(3) F(4) ^(5) T(6)

Base cells (single characters)

Cellchar[.][.][1] True ways[.][.][0] False ways
dp[0][0]T10
dp[2][2]T10
dp[4][4]F01
dp[6][6]T10

Length 3 (ek operator)

CellExpressionopTrue waysFalse ways
dp[0][2]T|T|lT×rT + lT×rF + lF×rT = 1+0+0 = 1lF×rF = 0
dp[2][4]T&F&lT×rT = 1×0 = 00+1+0 = 1
dp[4][6]F^T^lT×rF + lF×rT = 0+1 = 10+0 = 0

Length 5

dp[0][4] = "T|T&F", do split points:

kopleftrightTrue ways
1|T (lT=1,lF=0)T&F (rT=0,rF=1)1×0 + 1×1 + 0×0 = 1
3&T|T (lT=1,lF=0)F (rT=0,rF=1)lT×rT = 1×0 = 0

dp[0][4][1] = 1 + 0 = 1  ·  (aur dp[0][4][0] = 1)

Similarly dp[2][6] = "T&F^T" → True ways 2, False ways 0

Final — dp[0][6][1]

kopleft (i..k−1)right (k+1..j)True ways
1|T: lT=1, lF=0T&F^T: rT=2, rF=01×2 + 1×0 + 0×2 = 2
3&T|T: lT=1, lF=0F^T: rT=1, rF=0lT×rT = 1×1 = 1
5^T|T&F: lT=1, lF=1T: rT=1, rF=0lT×rF + lF×rT = 0 + 1 = 1

Answer = 2 + 1 + 1 = 4 ✅

Khud try karo

  1. Chaaron bracketings likho aur haath se verify karo ki sab True dete hain.
  2. k += 2 ko k++ kar do — kya hota hai?
  3. isTrue = 0 se call karo — kitne tareeke False dete hain? (Total bracketings − 4.)
Q52

Palindrome Partitioning II

LeetCode 132 (hard) · front partition — naya sub-pattern

Typefront partition
Statesirf i (1D!)
Answerf(0) − 1

Problem

String s ko is tarah cut karo ki har tukda palindrome ho. Minimum cuts kitne lagenge?

s = "aab" → 1 ("aa" | "b")

s = "abcde" → 4 (har character alag)

Soch — front partition

Phase 7 ka doosra sub-pattern

Q48–Q51 me hum interval (i, j) ko beech me todte the — 2D state.

Yahan hum sirf aage se todte hain: "index i se shuru karke, pehla tukda kahan tak?" Baaki string apne aap ek subproblem ban jaati hai. Toh state sirf ek index ka hai — 1D DP.

Ye front partition kehlata hai, aur Q53 bhi isi pe hai.

f(i) = "s[i..n-1] ko palindromes me todne ke liye minimum cuts"

f(i) = min over j = i to n-1, where s[i..j] is palindrome, of
           1 + f(j + 1)

Answer me −1 kyun

Off-by-one — classic

Recursion har tukde ke baad 1 ginta hai — aakhri tukde ke baad bhi. Par string ke end pe cut lagane ki zaroorat nahi hoti. Toh k tukdon ke liye recursion k deta hai, jabki cuts k-1 hote hain. Isliye final answer f(0) - 1.

Base case

if (i == n) return 0;    // string khatam

Code

1MemoizationO(n²) states × O(n) check
static boolean isPalindrome(int i, int j, String s) {
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return false;
        i++; j--;
    }
    return true;
}

static int f(int i, int n, String s, int[] dp) {
    if (i == n) return 0;

    if (dp[i] != -1) return dp[i];

    int mini = Integer.MAX_VALUE;

    for (int j = i; j < n; j++) {

        if (isPalindrome(i, j, s)) {
            int cost = 1 + f(j + 1, n, s, dp);
            mini = Math.min(mini, cost);
        }
    }

    return dp[i] = mini;
}

// driver
int n = s.length();
int[] dp = new int[n];
Arrays.fill(dp, -1);
System.out.println(f(0, n, s, dp) - 1);    // ⚠️ minus 1
2TabulationO(n³) / SC O(n)
static int minCut(String s) {
    int n = s.length();

    int[] dp = new int[n + 1];
    dp[n] = 0;                              // base case

    for (int i = n - 1; i >= 0; i--) {      // ULTA

        int mini = Integer.MAX_VALUE;

        for (int j = i; j < n; j++) {
            if (isPalindrome(i, j, s)) {
                mini = Math.min(mini, 1 + dp[j + 1]);
            }
        }

        dp[i] = mini;
    }

    return dp[0] - 1;
}
3Optimized — palindrome check precomputeO(n²)
static int minCut(String s) {
    int n = s.length();

    // pal[i][j] = kya s[i..j] palindrome hai
    boolean[][] pal = new boolean[n][n];

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                // length ≤ 2, ya andar wala bhi palindrome
                pal[i][j] = (j - i <= 2) || pal[i + 1][j - 1];
            }
        }
    }

    int[] dp = new int[n + 1];

    for (int i = n - 1; i >= 0; i--) {
        int mini = Integer.MAX_VALUE;

        for (int j = i; j < n; j++) {
            if (pal[i][j]) mini = Math.min(mini, 1 + dp[j + 1]);
        }

        dp[i] = mini;
    }

    return dp[0] - 1;
}
O(n³) → O(n²)

Har baar isPalindrome() chalane me O(n) lagta tha. Precompute karke wo O(1) lookup ban gaya. Palindrome table khud interval DP hai: s[i..j] palindrome hai agar s[i]==s[j] aur s[i+1..j-1] palindrome ho. Interview me ye optimization mention karna — badi baat hai.

Dry Run

s = "aab", n = 3

Palindrome table

i \ j0 (a)1 (a)2 (b)
0 (a)TT "aa"F "aab"
1 (a)—TF "ab"
2 (b)——T

dp array — ulta bharte hain

iKaunse j palindrome1 + dp[j+1]dp[i]
3base—0
2j=2 ("b" ✅)1 + dp[3] = 1+01
1j=1 ("a" ✅)1 + dp[2] = 1+12
0j=0 ("a" ✅)1 + dp[1] = 1+2 = 32
 j=1 ("aa" ✅)1 + dp[2] = 1+1 = 2 ✅

dp[0] = 2 → answer = 2 − 1 = 1 ✅

Verify

dp[0] = 2 ka matlab: 2 tukde lage. Tukde: "aa" aur "b". Toh cuts = 2 - 1 = 1 ✅

j=0 wala raasta ("a" | "a" | "b") 3 tukde deta — 2 cuts. DP ne behtar wala chuna.

Khud try karo

  1. -1 hata do — "aab" pe 2 aayega (galat).
  2. s = "aaaa" → 0 (poori string hi palindrome hai).
  3. Actual partitions print karo: ["aa", "b"]. Har i ke liye best j yaad rakho.
  4. Palindrome Partitioning I (LeetCode 131) — saare valid partitions list karo. Wo DP nahi, backtracking hai. Dono ka farak samajhna zaroori hai.
Q53

Partition Array for Maximum Sum

LeetCode 1043 · front partition, window ke saath

Typefront partition
Combinemax
Windowat most k

Problem

Array ko subarrays me baanto, har subarray ki length at most k. Har subarray ke saare elements uske maximum se replace ho jaate hain. Final array ka maximum sum?

arr = [1, 15, 7, 9, 2, 5, 10], k = 3 → 84

Partition: [1,15,7] [9] [2,5,10] → [15,15,15, 9, 10,10,10] → sum = 45 + 9 + 30 = 84 ✅

Soch — Q52 ka twin

Wahi front partition: "index i se shuru karke, pehla subarray kitna lamba?" — 1 se k tak.

f(i) = max over len = 1 to k (aur i+len ≤ n) of
           len * (max in arr[i..i+len-1]) + f(i + len)
Max ko loop ke andar hi maintain karo

Har len ke liye alag se max nikalna O(k) extra lagata. Par jaise-jaise len badhta hai, window ek element se badhti hai — toh maxi = Math.max(maxi, arr[i + len - 1]) se O(1) me update ho jaata hai. Ye chhota sa trick O(n k²) ko O(n k) bana deta hai.

Base case

if (i == n) return 0;

Yahan -1 wala jhol nahi hai (Q52 ke ulta), kyunki hum cuts nahi sum gin rahe hain.

Code

1MemoizationO(n × k)
static int f(int i, int n, int k, int[] arr, int[] dp) {
    if (i == n) return 0;

    if (dp[i] != -1) return dp[i];

    int maxi = Integer.MIN_VALUE;
    int best = Integer.MIN_VALUE;

    for (int len = 1; len <= k && i + len - 1 < n; len++) {

        maxi = Math.max(maxi, arr[i + len - 1]);   // window ka max

        int sum = len * maxi + f(i + len, n, k, arr, dp);

        best = Math.max(best, sum);
    }

    return dp[i] = best;
}

// driver
int[] dp = new int[n];
Arrays.fill(dp, -1);
System.out.println(f(0, n, k, arr, dp));
2TabulationO(n × k) / SC O(n)
static int maxSumAfterPartitioning(int[] arr, int k) {
    int n = arr.length;

    int[] dp = new int[n + 1];
    dp[n] = 0;

    for (int i = n - 1; i >= 0; i--) {         // ULTA

        int maxi = Integer.MIN_VALUE;
        int best = Integer.MIN_VALUE;

        for (int len = 1; len <= k && i + len - 1 < n; len++) {

            maxi = Math.max(maxi, arr[i + len - 1]);

            int sum = len * maxi + dp[i + len];

            best = Math.max(best, sum);
        }

        dp[i] = best;
    }

    return dp[0];
}

Dry Run

arr = [1, 15, 7, 9, 2, 5, 10], k = 3, n = 7. Ulta bharte hain.

ilen=1len=2len=3dp[i]
7base0
6 (10)1×10 + 0 = 10——10
5 (5)1×5 + 10 = 152×10 + 0 = 20—20
4 (2)1×2 + 20 = 222×5 + 10 = 203×10 + 0 = 3030
3 (9)1×9 + 30 = 392×9 + 20 = 383×9 + 10 = 3739
2 (7)1×7 + 39 = 462×9 + 30 = 483×9 + 20 = 4748
1 (15)1×15 + 48 = 632×15 + 39 = 693×15 + 30 = 7575
0 (1)1×1 + 75 = 762×15 + 48 = 783×15 + 39 = 8484

Answer = dp[0] = 84 ✅

Partition trace karo

dp[0] = 84 aaya len=3 se → pehla subarray [1,15,7], max 15, contribution 45. Phir dp[3] = 39.

dp[3] = 39 aaya len=1 se → [9], contribution 9. Phir dp[4] = 30.

dp[4] = 30 aaya len=3 se → [2,5,10], max 10, contribution 30. Phir dp[7] = 0.

Partition: [1,15,7] [9] [2,5,10] → 45 + 9 + 30 = 84 ✅

Interesting observation

i=1 pe len=3 jeeta ([15,7,9], sab 15 ban gaye = 45). Chhoti value 7 ko bade padosi ke saath rakh ke uska faayda uthaya. Ye greedy se nahi milta — greedy har chhote element ko akela chhodne ki koshish karta.

🎉 Phase 7 complete

#SawaalTypeStateCombine
48MCMintervali, jmin
49Cut a Stickintervali, jmin
50Burst Balloonsintervali, jmax
51Boolean Evaluationintervali, j, isTrue+ (count)
52Palindrome Partitioning IIfronti (1D)min
53Partition for Max Sumfronti (1D)max

Phase 7 ke do sub-patterns

Interval partition (Q48–51)Front partition (Q52–53)
State(i, j) — 2Di — 1D
Todte kahaninterval ke beech mehamesha aage se
Recursionf(i,k) + f(k+1,j)cost + f(j+1)
ComplexityO(n³)O(n × k)
Pehchan"bracket lagao", "order chuno""pehla tukda kahan tak"

Pehchanne ka tareeka: agar tukdon ka combine hone ka order matter karta hai (MCM, balloons) → interval. Agar bas kahan todna hai matter karta hai aur tukde independent hain (palindrome, subarray) → front.

Khud try karo

  1. k = 1 daalo → answer = poora array ka sum (49). Har element akela.
  2. k = 7 (poori length) → 7 × 15 = 105.
  3. Q52 aur Q53 ka code side-by-side rakho. Structure identical hai — min vs max, palindrome-check vs window-max, aur -1 vs kuch nahi.

Phase 8 · Q54–Q55

DP on Squares

Chhota phase, do sawaal — par dono interview me aksar aate hain. Idea ek hi hai: har cell ko bottom-right corner maan ke pucho, "yahan khatam hone wala sabse bada square/rectangle kitna bada hai?" Bilkul Phase 6 ka "i pe khatam" wala dhaancha, 2D me.

Phase 8 core recurrence if (matrix[i][j] == 1)
    dp[i][j] = 1 + min( dp[i-1][j], dp[i][j-1], dp[i-1][j-1] )
else
    dp[i][j] = 0  // reset — Q27 jaisa

answer = sum / max over all cells
Q54

Count Square Submatrices with All Ones

LeetCode 1277 · min of three neighbours

dp[i][j](i,j) pe khatam
Combine1 + min(3)
Answersum of all cells

Problem

Binary matrix me kitne square submatrices hain jinme saare 1 hain? (Har size ke — 1×1, 2×2, 3×3...)

matrix = 0 1 1 1
         1 1 1 1
         0 1 1 1

answer = 15

Soch — do insights

1 · dp[i][j] = "yahan khatam hone wala sabse bada square"

dp[i][j] = "cell (i,j) ko bottom-right corner maan ke, sabse bade all-ones square ki side length"

Sabse bada trick — ginti apne aap ho jaati hai

Agar dp[i][j] = 3 hai, toh us corner pe teen squares khatam hote hain: 1×1, 2×2, aur 3×3.

Matlab dp[i][j] ki value hi us cell pe khatam hone wale squares ki ginti hai!

Toh answer = poori table ka sum. Alag se counting logic likhne ki zaroorat hi nahi. 🎯

2 · Recurrence — teen padosi ka minimum

(i,j) pe k size ka square tabhi ban sakta hai jab uske teeno padosi bhi kam se kam k-1 size ka square rakh sakte hon:

  • dp[i-1][j] — upar
  • dp[i][j-1] — left
  • dp[i-1][j-1] — diagonal

Minimum lete hain kyunki sabse kamzor kadi hi decide karti hai. Ek bhi chhota hua toh square utna hi bada ban paayega.

if (matrix[i][j] == 1)
    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
else
    dp[i][j] = 0;

Base case

Pehli row aur pehla column: wahan square sirf 1×1 hi ho sakta hai, toh dp[i][j] = matrix[i][j] (0 ya 1).

Code

→TabulationO(n × m) / SC O(n × m)
static int countSquares(int[][] matrix) {
    int n = matrix.length, m = matrix[0].length;

    int[][] dp = new int[n][m];

    // base: pehli row
    for (int j = 0; j < m; j++) dp[0][j] = matrix[0][j];

    // base: pehla column
    for (int i = 0; i < n; i++) dp[i][0] = matrix[i][0];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {

            if (matrix[i][j] == 0) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j],
                           Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
            }
        }
    }

    // answer = poori table ka sum
    int sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            sum += dp[i][j];

    return sum;
}
In-place bhi kar sakte ho

matrix me hi likh do (agar modify allowed hai) → O(1) extra space. Interview me poochna ki input modify kar sakte hain ya nahi.

Dry Run

matrix0123
00111
11111
20111
dp0123
00111
11122
20123

Cell by cell — important wale

Cellmatrixup, left, diag1 + mindp
dp[1][1]1dp[0][1]=1, dp[1][0]=1, dp[0][0]=01 + 01
dp[1][2]1dp[0][2]=1, dp[1][1]=1, dp[0][1]=11 + 12
dp[2][2]1dp[1][2]=2, dp[2][1]=1, dp[1][1]=11 + 12
dp[2][3]1dp[1][3]=2, dp[2][2]=2, dp[1][2]=21 + 23

dp[1][1] = 1 hi raha kyunki diagonal dp[0][0] = 0 tha — wahan 0 hai matrix me. Ek kamzor corner ne poora 2×2 rok diya.

Sum nikalo

Row 0: 0+1+1+1 = 3
Row 1: 1+1+2+2 = 6
Row 2: 0+1+2+3 = 6

Total = 3 + 6 + 6 = 15 ✅

Verify — ginti check

SizeKitne
1×110 (matrix me 10 ones hain)
2×24
3×31
Total15 ✅

Khud try karo

  1. Maximal Square (LeetCode 221) — sabse bade square ka area. Same dp, bas sum ki jagah max(dp[i][j]) lo aur square kar do. Do line ka farak.
  2. min ki jagah max lagao — kya galat aata hai? Kyun?
  3. Sirf do padosi (up, left) lo, diagonal chhod do — kaunsa case tootega? (Diagonal pe hole ho toh galat bada square gina jaayega.)
Q55

Maximal Rectangle

LeetCode 85 (hard) · DP nahi — histogram + stack

Techniqueprefix + stack
Reductionn × histogram
TimeO(n × m)

Problem

Binary matrix me sabse bade rectangle (square nahi) ka area jisme saare 1 hain.

matrix = 1 0 1 0 0
         1 0 1 1 1
         1 1 1 1 1
         1 0 0 1 0

answer = 6

Soch — har row ko histogram maano

Poora sawaal ek reduction hai

Har row ko base maano, aur uske upar column-wise consecutive 1s ki height gino. Ab har row ek histogram ban gaya.

Toh sawaal ban gaya: "n histograms me se har ek me largest rectangle nikalo, sabka max lo".

Height array kaise banega:

if (matrix[i][j] == 1) heights[j] += 1;
else                   heights[j]  = 0;   // reset — chain tooti

Ye Q27 (Common Substring) wala hi reset-on-zero pattern hai, columns pe.

Largest Rectangle in Histogram — monotonic stack

Har bar i ke liye do cheezein chahiye: uske left me pehla chhota bar (PSE) aur right me pehla chhota bar (NSE). Toh us bar ki poori width = NSE - PSE - 1, aur area = height[i] × width.

Monotonic increasing stack se ye ek hi pass me O(n) me ho jaata hai.

Ye DP nahi hai

Phase 8 me hone ke bawajood, Q55 ka core stack hai, DP nahi. Interview me isko "DP problem" kehna galat impression deta hai. Sahi baat: "matrix ko histograms me reduce karke, har histogram pe monotonic stack".

Code

1Largest rectangle in histogramO(m)
static int largestRectangleArea(int[] heights) {
    int m = heights.length;
    Stack<Integer> st = new Stack<>();
    int maxArea = 0;

    for (int i = 0; i <= m; i++) {

        int currHeight = (i == m) ? 0 : heights[i];   // sentinel

        while (!st.isEmpty() && heights[st.peek()] >= currHeight) {

            int height = heights[st.pop()];

            // width: stack khaali hai toh poora left available
            int width  = st.isEmpty() ? i : i - st.peek() - 1;

            maxArea = Math.max(maxArea, height * width);
        }

        st.push(i);
    }

    return maxArea;
}
2Maximal Rectangle — row by rowO(n × m)
static int maximalRectangle(char[][] matrix) {
    int n = matrix.length, m = matrix[0].length;

    int[] heights = new int[m];
    int maxArea = 0;

    for (int i = 0; i < n; i++) {

        // is row ke liye histogram update karo
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == '1') heights[j]++;
            else                     heights[j] = 0;   // reset
        }

        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }

    return maxArea;
}
Sentinel trick

Loop i <= m tak chalta hai aur aakhri iteration me currHeight = 0 maan leta hai. Isse stack me bache hue saare bars apne aap pop ho jaate hain — alag se cleanup loop likhne ki zaroorat nahi.

Dry Run

matrix upar wali. Row-by-row heights:

Rowmatrix rowheights[]Largest rect in histogram
01 0 1 0 0[1, 0, 1, 0, 0]1
11 0 1 1 1[2, 0, 2, 1, 1]3
21 1 1 1 1[3, 1, 3, 2, 2]6 ✅
31 0 0 1 0[4, 0, 0, 3, 0]4

Row 2 ka histogram — kahan se 6 aaya

heights = [3, 1, 3, 2, 2]

BarheightKitni door tak faila (width)Area
031 (bar 1 chhota hai)3
115 (poora)5
2313
323 (bars 2,3,4 ≥ 2)6 ✅
4236

Answer = 6 ✅

Matrix me wo rectangle kahan hai

Rows 1–2, columns 2–4 → 2 rows × 3 columns = 6:

row 1:  . . 1 1 1
row 2:  . . 1 1 1

Row 3 pe reset dekho

heights = [4, 0, 0, 3, 0] — columns 1, 2, 4 me 0 aaya toh height reset ho gayi. Yahi heights[j] = 0 wali line kar rahi hai.

🎉 Phase 8 complete

#SawaalTechniqueTime
54Count Square SubmatricesDP: 1 + min(3 padosi)O(n × m)
 Maximal Square (LC 221)same DP, max × maxO(n × m)
55Maximal Rectanglehistogram + stackO(n × m)

Khud try karo

  1. Pehle Largest Rectangle in Histogram (LeetCode 84) akela solve karo. Q55 uske bina samajh nahi aayega.
  2. Sentinel (i <= m) hata do aur alag cleanup loop likho — same answer aana chahiye, par code lamba ho jaayega.
  3. heights[j] = 0 ki jagah heights[j] waisa hi chhod do — kaunsa test case tootega?

Phase 9 · Q56–Q58

Advanced DP

Teen alag-alag techniques jo array/string ke bahar jaati hain: DP tree pe, DP subset pe (bitmask), aur DP digits pe. Ye aksar senior roles aur CP me aati hain. Har ek ka apna dhaancha hai — par soch wahi purani: "state kya hai, aur choices kya hain?"

Q56

DP on Trees — House Robber III

LeetCode 337 · Q5 (House Robber) ka tree version

Statenode, canRob
Returnpair [rob, skip]
Traversalpost-order

Problem

Binary tree ke har node me paisa hai. Do directly connected nodes (parent-child) ko ek saath loot nahi sakte. Maximum kitna loot sakte ho?

      3
     / \
    2   3
     \    \
      3    1

answer = 7   (3 + 3 + 1, root aur dono grandchildren)

Soch — Q5 ka hi dhaancha, tree pe

Q5 (House Robber) me array pe do choices thi: lo aur i-2 pe jao, ya chhodo aur i-1 pe jao.

Tree me wahi hai, bas "aage" ka matlab children hai:

  • Node ko loot lo → node.val + dono children ko chhodna padega (par grandchildren le sakte ho)
  • Node ko chhod do → 0 + dono children me se jo behtar ho wo lo
Pair return karne ka trick

Har node se ek do-value ka pair return karo:

  • res[0] = "is subtree ka max, agar ye node loota"
  • res[1] = "is subtree ka max, agar ye node chhoda"

Isse alag HashMap<TreeNode, Integer> memoization ki zaroorat hi nahi — har node ek hi baar visit hota hai. O(n) time, O(h) stack space.

Recurrence

left  = solve(node.left)
right = solve(node.right)

// node loota → children chhodne padenge
rob  = node.val + left[1] + right[1]

// node chhoda → children ka best lo
skip = max(left[0], left[1]) + max(right[0], right[1])

return [rob, skip]
skip me max kyun

Node chhoda hai toh children pe koi pabandi nahi — wo chahe toh loot lein, chahe toh na lein. Isliye dono options ka max. Yahan galti se sirf left[0] (rob) lena bahut common bug hai.

Code

→Post-order + pair returnO(n) / SC O(h)
static int[] solve(TreeNode node) {
    // [0] = ye node loota, [1] = ye node chhoda
    if (node == null) return new int[]{0, 0};

    int[] left  = solve(node.left);
    int[] right = solve(node.right);

    // loota → children chhodo
    int rob = node.val + left[1] + right[1];

    // chhoda → children ka best
    int skip = Math.max(left[0], left[1])
             + Math.max(right[0], right[1]);

    return new int[]{rob, skip};
}

static int rob(TreeNode root) {
    int[] ans = solve(root);
    return Math.max(ans[0], ans[1]);
}
Ye "post-order" kyun hai

Kyunki node ka answer nikalne se pehle dono children ka answer chahiye. Left → Right → Node — wahi post-order traversal. Poori Tree DP isi order me chalti hai.

Dry Run

        3  (root)
       / \
      2   3
       \    \
        3    1
Nodeleft pairright pairrob = val + l[1] + r[1]skip = max(l) + max(r)
3 (leaf, left ka child)[0,0][0,0]3 + 0 + 0 = 30 + 0 = 0
1 (leaf, right ka child)[0,0][0,0]1 + 0 + 0 = 10 + 0 = 0
2[0,0][3,0]2 + 0 + 0 = 20 + max(3,0) = 3
3 (right child)[0,0][1,0]3 + 0 + 0 = 30 + max(1,0) = 1
3 (root)[2,3][3,1]3 + 3 + 1 = 7max(2,3) + max(3,1) = 3+3 = 6

Answer = max(7, 6) = 7 ✅

Verify

rob = 7 ka matlab: root (3) + left ka skip (3) + right ka skip (1).

Left ka skip = 3 aaya uske right child (3) se. Right ka skip = 1 aaya uske right child (1) se.

Toh loota: root(3) + grandchild(3) + grandchild(1) = 7 ✅ — koi bhi do directly connected nahi hain.

Tree DP ka general dhaancha

Har tree DP problem me yahi teen kadam hain:

  1. Har node ke liye decide karo ki kya-kya information parent ko chahiye (yahan: rob/skip dono).
  2. Children ko recursively solve karo (post-order).
  3. Children ki information se apni banao aur return karo.

Khud try karo

  1. Diameter of Binary Tree (LC 543) — har node se height return karo aur global max update karo. Same dhaancha.
  2. Binary Tree Maximum Path Sum (LC 124, hard) — har node se "meri taraf se ek hi branch" wala sum return karo, aur global me "dono branch" wala consider karo.
  3. skip me max ki jagah sirf left[0] + right[0] likh do — kaunsa tree galat aayega?
Q57

Bitmask DP — Assign Tasks / TSP

CP classic · LeetCode 1349, 847, 943 family

Statemask (subset)
Size2ⁿ states
Limitn ≤ 20

Problem — Assign Tasks

n log aur n tasks hain. cost[i][j] = person i ko task j dene ka kharcha. Har person ko exactly ek task. Minimum total cost?

cost = 9 2 7 8
       6 4 3 7
       5 8 1 8
       7 6 9 4

answer = 13   (P0→T1=2, P1→T0=6, P2→T2=1, P3→T3=4)

Soch — subset ko integer me pack karo

Bitmask ka core idea

Ek n-bit integer ek subset represent kar sakta hai. Bit j set hai = task j assign ho chuka hai.

mask = 0101 (binary) = tasks 0 aur 2 done, tasks 1 aur 3 baaki.

Toh 2ⁿ possible states — aur n ≤ 20 tak ye manageable hai (2²⁰ ≈ 10⁶).

Ek chhota par bahut zaroori observation

mask me kitne bits set hain, wahi batata hai ki kitne log assign ho chuke hain. Toh agla person kaunsa hai, ye mask se hi nikal aata hai:

int person = Integer.bitCount(mask);

Alag se i state rakhne ki zaroorat hi nahi — ye bitmask DP ka classic optimization hai.

Recurrence

f(mask):
    person = bitCount(mask)
    if (person == n) return 0        // sab assign ho gaye

    mini = INF
    for task = 0 to n-1:
        if (task abhi free hai)      // bit set nahi hai
            mini = min(mini, cost[person][task] + f(mask | (1 << task)))

    return mini

Bit operations — cheat sheet

OperationCodeMatlab
Bit j check(mask & (1 << j)) != 0task j done hai?
Bit j setmask | (1 << j)task j ko done mark karo
Kitne setInteger.bitCount(mask)kitne tasks done
Sab donemask == (1 << n) - 1poora bhara hua

Code

1MemoizationO(2ⁿ × n)
static int f(int mask, int n, int[][] cost, int[] dp) {
    int person = Integer.bitCount(mask);

    if (person == n) return 0;

    if (dp[mask] != -1) return dp[mask];

    int mini = Integer.MAX_VALUE;

    for (int task = 0; task < n; task++) {

        if ((mask & (1 << task)) == 0) {           // task free hai

            int c = cost[person][task]
                  + f(mask | (1 << task), n, cost, dp);

            mini = Math.min(mini, c);
        }
    }

    return dp[mask] = mini;
}

// driver
int[] dp = new int[1 << n];
Arrays.fill(dp, -1);
System.out.println(f(0, n, cost, dp));
2TabulationO(2ⁿ × n)
static int assignTasks(int n, int[][] cost) {
    int full = (1 << n) - 1;

    int[] dp = new int[1 << n];
    Arrays.fill(dp, Integer.MAX_VALUE);

    dp[full] = 0;                              // base: sab done

    for (int mask = full - 1; mask >= 0; mask--) {

        int person = Integer.bitCount(mask);
        if (person >= n) continue;

        for (int task = 0; task < n; task++) {

            if ((mask & (1 << task)) == 0) {
                int next = mask | (1 << task);

                if (dp[next] != Integer.MAX_VALUE) {
                    dp[mask] = Math.min(dp[mask],
                                        cost[person][task] + dp[next]);
                }
            }
        }
    }

    return dp[0];
}
Ulta kyun chalte hain

dp[mask] ko dp[next] chahiye, aur next me zyada bits set hain — matlab next > mask. Toh bade masks pehle bharne padte hain. Isliye full se 0 tak ulta loop.

Dry Run

n = 4, cost matrix upar wali. Kuch important states:

mask (binary)Tasks doneperson = bitCountdp[mask]
1111sab40 (base)
01110,1,23cost[3][3] = 4
10110,1,33cost[3][2] = 9
00110,12min(cost[2][2]+dp[0111], cost[2][3]+dp[1011]) = min(1+4, 8+9) = 5
000101min over free tasks... = 11
0000—013

dp[0011] ka detail

mask = 0011 → tasks 0, 1 done → person = 2. Free tasks: 2, 3.

taskcost[2][task]+ dp[next]Total
21dp[0111] = 45 ✅
38dp[1011] = 917

Final path

PersonTaskCost
P0T12
P1T06
P2T21
P3T34
Total—13 ✅

Complexity aur limits

n2ⁿ2ⁿ × nChalega?
101,024~10⁴easily
1532,768~5×10⁵haan
201,048,576~2×10⁷borderline
2533 million~8×10⁸nahi
Interview signal

Agar constraints me n ≤ 20 ya n ≤ 16 dikhe, toh bitmask DP ka strong hint hai. Normal problems me n itna chhota nahi hota.

Khud try karo

  1. TSP — state (mask, lastCity). Yahan extra state chahiye kyunki cost "kahan se aaye" pe depend karta hai. dp[1<<n][n].
  2. LeetCode 1349 (Maximum Students Taking Exam) — row-by-row bitmask, valid seating masks.
  3. person ko alag state banao (dp[mask][person]) — kaam karega par memory waste hoga. Kyun? (Kyunki person mask se derive ho jaata hai — redundant state.)
Q58

Digit DP

CP classic · LeetCode 233, 357, 902, 1012 family — poore roadmap ka aakhri sawaal

Statepos, sum, tight
Iteratedigits, numbers nahi
Rangef(R) − f(L−1)

Problem

1 se N tak kitne numbers hain jinke digits ka sum exactly S hai?

N = 25, S = 7 → 3 (7, 16, 25)

Constraints me N 10¹⁸ tak ho sakta hai — toh loop chalana namumkin hai.

Soch — numbers nahi, digits pe chalo

Digit DP ka core idea

N tak loop O(N) hai — 10¹⁸ pe marega. Par N me sirf 18 digits hain.

Toh number ko left se right, ek-ek digit banao. Har position pe 0 se 9 tak koi bhi digit daal sakte ho — par ek shart ke saath.

Wo shart: "tight"

Maan lo N = 25. Number banate waqt:

Pehla digitDoosra digit kitna daal sakte hoKyun
2 (= N ka pehla digit)sirf 0 se 5abhi bhi N ki limit pe chipke hain
0 ya 1 (< N ka)0 se 9, poori azaadialready N se chhota ho chuka hai
tight = poore Digit DP ka dil

tight = true → ab tak ke saare digits N ke digits ke barabar the. Toh is position pe upper limit digits[pos] hai.

tight = false → kahin pehle chhota digit daal diya tha. Ab number pakka N se chhota hai, toh upper limit 9.

Ek baar tight false ho gaya toh phir kabhi true nahi hota — one-way door.

State aur recurrence

f(pos, sum, tight):
    if (pos == len) return (sum == S) ? 1 : 0;

    limit = tight ? digits[pos] : 9;

    count = 0
    for d = 0 to limit:
        newTight = tight && (d == limit)
        count += f(pos + 1, sum + d, newTight)

    return count
Memoize sirf tight == false wale states

tight = true wale states ka raasta unique hota hai — har pos pe sirf ek hi tight path hota hai (N ka prefix). Unko cache karne ka koi faayda nahi, aur agar galat cache kar diya toh alag tight-prefix ke liye galat value mil jaayegi.

Toh: if (!tight) dp[pos][sum] = count; — aur read bhi tabhi karo jab !tight ho.

Code

→MemoizationO(len × maxSum × 10)
static int[] digits;
static int S;
static int[][] dp;          // dp[pos][sum], sirf tight == false ke liye

static int f(int pos, int sum, boolean tight) {

    if (sum > S) return 0;                       // pruning

    if (pos == digits.length) {
        return (sum == S) ? 1 : 0;
    }

    if (!tight && dp[pos][sum] != -1) return dp[pos][sum];

    int limit = tight ? digits[pos] : 9;
    int count = 0;

    for (int d = 0; d <= limit; d++) {

        boolean newTight = tight && (d == limit);

        count += f(pos + 1, sum + d, newTight);
    }

    if (!tight) dp[pos][sum] = count;            // ⚠️ sirf yahan

    return count;
}

static int countNumbers(int N, int targetSum) {
    String s = String.valueOf(N);

    digits = new int[s.length()];
    for (int i = 0; i < s.length(); i++) {
        digits[i] = s.charAt(i) - '0';
    }

    S  = targetSum;
    dp = new int[s.length()][S + 1];
    for (int[] row : dp) Arrays.fill(row, -1);

    int ans = f(0, 0, true);

    if (S == 0) ans--;      // 0 khud count ho gaya tha, hata do

    return ans;
}

// Range [L, R] chahiye toh:
// countNumbers(R, S) - countNumbers(L - 1, S)
Leading zeros ka sawaal

Is problem me leading zeros se koi farak nahi padta — 07 ka digit sum 7 hi hai, aur wo 7 hi number hai. ✅

Par kuch problems me (jaise "no repeated digits" ya "count digits") leading zeros matter karte hain — tab ek chautha state started (boolean) add karna padta hai: "kya asli number shuru ho chuka hai?"

Dry Run

N = 25, S = 7. digits = [2, 5], len = 2

f(0, 0, true) — pehla digit

limit = digits[0] = 2, toh d chalega 0, 1, 2:

dnewTightRecursive callAndar kya huaReturn
0false (0 ≠ 2)f(1, 0, false)limit = 9, d=7 pe sum 7 ✅1
1false (1 ≠ 2)f(1, 1, false)limit = 9, d=6 pe sum 7 ✅1
2true (2 == 2)f(1, 2, true)limit = 5, d=5 pe sum 7 ✅1

Total = 1 + 1 + 1 = 3 ✅

Har raaste ka number

PathDigitsNumberDigit sum
d=0, then d=70, 777 ✅
d=1, then d=61, 6167 ✅
d=2, then d=52, 5257 ✅

tight ka asar saaf dekho

d=2 wale raaste me tight zinda raha, toh doosre digit ki limit 5 thi — 9 nahi. Isliye 26, 27, 28, 29 jaise numbers explore hi nahi hue. Sahi bhi hai — wo 25 se bade hain.

d=0 aur d=1 wale raston me tight mar gaya, toh poori 0–9 range khuli. Aur wahi se 7 aur 16 mile.

Complexity

States: len × maxSum × 2. Har state pe O(10) ka loop.

N = 10¹⁸, S ≤ 162 (18 digits × 9) → 18 × 163 × 2 × 10 ≈ 6 × 10⁴ operations. Instant.

Brute force 10¹⁸ hota — ye 10¹⁵ guna tez hai.

Digit DP ka general template

Har digit DP problem me yahi chaar cheezein decide karni hoti hain:

  1. pos — kaunsa digit bhar rahe ho (hamesha)
  2. tight — N ki limit pe chipke ho ya nahi (hamesha)
  3. problem-specific state — sum, remainder, last digit, used-digits mask, jo bhi chahiye
  4. started — sirf tab jab leading zeros matter karte hon

Khud try karo

  1. LeetCode 233 (Number of Digit One) — 1 se n tak kitne 1 aate hain. State: (pos, count, tight).
  2. Count numbers divisible by K — sum ki jagah remainder track karo: (rem * 10 + d) % K.
  3. if (!tight) wali condition hata ke sab memoize kar do — galat answer aayega. Kaunse N pe? Test karo, ye sabse zaroori exercise hai.
  4. Range version likho: [100, 500] me digit sum 5 wale kitne? (f(500) - f(99))
∑

Saat phases, ek cheatsheet

Interview se 15 minute pehle sirf ye padho

Har phase ka core recurrence

PhaseQStateCore recurrence
3 · Knapsack14–24(i, target)COMBINE( f(i−1, t), f(i/i−1, t−a[i]) )
4 · Strings25–34(i, j)match ? 1+f(i−1,j−1) : COMBINE(f(i−1,j), f(i,j−1))
5 · Stocks35–40(i, buy[, cap])max( ±price[i] + f(i+1, !buy), f(i+1, buy) )
6 · LIS41–47(i)dp[i] = 1 + max(dp[j]) for j < i where COND
7 · Partition48–53(i, j) ya (i)min/max over k of f(i,k) + f(k+1,j) + COST
8 · Squares54–55(i, j)1 + min(up, left, diag), warna 0
9 · Advanced56–58node / mask / pospost-order · bitmask · tight

Rule 1 — Combine operator sawaal se aata hai

Sawaal kya poochh raha haiOperatorInvalid pe return
kya possible hai?||false
kitne tareeke?+0
minimum?min1e9
maximum?max-1e9 / MIN_VALUE

Invalid wala column sabse zyada bugs deta hai — aur wo silently galat answer dete hain, crash nahi karte.

Rule 2 — Loop directions

SituationDirectionKahan
0/1 knapsack, single arrayulta (t = T → 0)Q15, Q19, Q32
Unbounded, single arrayseedha (t = 0 → T)Q20, Q22, Q23, Q24
Recursion i+1 pe jaati haitabulation ultaPhase 5, Q52, Q53
Interval DPi ulta, j seedhaQ48–Q51
Bitmaskmask ulta (full → 0)Q57

Rule 3 — Answer kahan milta hai

AnswerKabSawaal
aakhri cellstate poore input ko cover karti haiQ14, Q19, Q25, Q33
poori table ka max/sumdp[i] = "i pe khatam"Q27, Q41, Q46, Q54
row scansaare achievable values chahiyeQ16
answer − 1recursion ne ek extra ginaQ52

Doosri row sabse zyada bugs deti hai. Jab bhi dp[i] ka matlab "i pe khatam" ho, poori table scan karni padegi.

Rule 4 — Zyadatar sawaal disguise me hote hain

Dikhta haiAsal me hai
Equal Partition (Q15)Subset Sum, target = S/2
Target Sum (Q21)Count Partitions, D = target
Rod Cutting (Q24)Unbounded Knapsack, wt = i+1
LPS (Q28)LCS(s, reverse(s))
Min Insert Palindrome (Q29)n − LPS
Insert/Delete A→B (Q30)n + m − 2·LCS
Divisible Subset (Q44)sort + LIS, condition badli
String Chain (Q45)sort by length + LIS
Bitonic (Q46)LIS + LIS ulta, −1
Maximal Rectangle (Q55)n × histogram + stack
House Robber III (Q56)House Robber, post-order pe

Paintalees me se pandrah se zyada sawaalon me naya DP likhna hi nahi hai — sirf pehchanna hai ki kaunsa purana sawaal hai. Interview me asli skill yahi test hoti hai.

Debug checklist

Answer galat aa raha hai? Ye chhe cheezein order me check karo:

  1. Invalid pe kya return kar rahe ho? min me 0, max me bada number — sabse common.
  2. Answer aakhri cell me hai ya poori table me? Phase 6 aur Q27, Q54 me scan chahiye.
  3. Take me i hai ya i-1? 0/1 aur unbounded mix ho gaye?
  4. Single array me loop direction sahi hai? Ulta vs seedha.
  5. Base case explicit set kiya? Q33 (Edit Distance) ki pehli row/column zeros nahi hoti.
  6. Overflow? Counting problems me long/double lagao (Q32, Q22, Q51).

Ab bhi na mile: memoization version chalao, poori dp table print karwao, aur haath se banayi table se compare karo. Jis pehle cell pe farak dikhe, bug wahi hai.

Complexity summary

PhaseTimeSpace (optimized)Space opt possible?
3 · KnapsackO(n × target)O(target)haan
4 · StringsO(n × m)O(min(n,m))haan (print chhod ke)
5 · StocksO(n × 2 × k)O(k)haan
6 · LISO(n²) → O(n log n)O(n)already O(n)
7 · PartitionO(n³) / O(n×k)O(n²) / O(n)interval me nahi
8 · SquaresO(n × m)O(m)haan
9 · AdvancedO(n) / O(2ⁿ×n) / O(len×S×10)O(h) / O(2ⁿ) / O(len×S)—

Phases 3–9 · Q14–Q58 · Java · recursion → memoization → tabulation → space optimized