DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n): Visual walkthrough

3.7.11 · D2 · Coding › Algorithm Paradigms › DP problems — Longest Increasing Subsequence (LIS) — O(n²) a

Hum sab kuch ek running array pe banate hain: $A = [3, 1, 4, 1, 5, 9, 2, 6]$ Kuch aur assume nahi kiya. Pehle apne words define karte hain.

Figure — DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n)

Step 1 — Array ko heights ki tarah draw karo, aur ek increasing chain banao

KYA. Har value $A [i]$ ko horizontal position $i$ aur height $A [i]$ par ek dot ki tarah plot karo. Ek increasing subsequence koi bhi aisa set of dots hai jinhein tum arrows se connect kar sako jo hamesha right aur upar jaate hon.

KYUN. Height = value, position = index. "Increasing subsequence" ab ek aisi staircase ban jaati hai jo right move karte waqt sirf upar hi chadhti hai. Woh visual — ek path jo kabhi neeche nahi utarta — poora problem hai. Neeche sab kuch is baare mein hai ki sabse lambi aisi staircase kaise banayein bina kabhi bhi saare $2^{n}$ possible paths dekhein.

PICTURE. Upar Figure s01. Red arrows $3 \to 4 \to 5 \to 9$ ko connect karte hain (length 4). Notice karo ki har arrow upar-aur-right point karta hai; yahi ek matra rule hai.

Step 2 — Ek bookkeeping array: `tails`

KYA. Hum tails naam ka ek single array introduce karte hain. Hum ise aise padhte hain: $tails [k] = woh sabse chhoti value jo length (k + 1) ki increasing chain ko END kar sake.$ Yahan $k$ $0$ se shuru hota hai, isliye tails[0] length-1 chains ke baare mein hai, tails[1] length-2 chains ke baare mein, aur aise aage.

"Smallest" word KYUN. Ek given length ki chain future ke liye tab hi useful hoti hai jab use extend karna aasaan ho. Chain ko ek naye value $x$ se extend karne ke liye, $x$ ko chain ki last value se bada hona chahiye. Toh woh last value (yani "tail") jitni chhoti hogi, utne zyada future $x$ attach ho sakenge. Ek hi length ki saari chains mein, sabse chhoti tail wali chain baaki sabse dominate karti hai — woh sab kuch accept karti hai jo doosri karti hain, aur kuch zyada bhi. Isliye hum hamesha sirf minimum tail per length record karte hain.

PICTURE. Figure s02 mein do alag length-2 chains hain jo $4$ aur $2$ par khatam hoti hain. $2$ par khatam hone wali (red) clearly better hai: koi bhi future value jo $4$ ke upar fit ho sakti thi, woh $2$ ke upar bhi fit hogi, par ulta nahi.

Step 3 — `tails` automatically sorted rehta hai (yahi cheez binary search allow karti hai)

KYA. Claim: tails strictly increasing hai, matlab $tails [0] < tails [1] < tails [2] < \dots$ — hamesha, chahe hum koi bhi array feed karein.

KYUN. Koi bhi chain lo length $k + 1$ ki jo value $tails [k]$ par khatam hoti ho. Iska last element kaat do. Ab tumhare paas length $k$ ki chain hai jiska tail koi aisi value hai jo strictly less than $tails [k]$ hai (woh ek rising chain mein pehle aayi thi). Lekin $tails [k - 1]$ sabse chhota possible length- $k$ tail hai, isliye $tails [k - 1] \leq (woh kata hua tail) < tails [k] .$ Inequality chain karo: $tails [k - 1] < tails [k]$ . Ho gaya — array chadhta hai.

PICTURE. Figure s03: length-4 red chain; uska top element hatao aur bachi hui length-3 chain ka tail provably length-4 tail se neeche hai. Isse tails-ki-staircase ko rise karne par majboor hona padta hai.

Step 4 — Ek naya value $x$ process karna: dhundho yeh kahan fit hota hai

KYA. Har incoming value $x$ ke liye, hum poochhte hain: sabse leftmost position $k$ kaunsi hai jahan $tails [k] \geq x$ ho? Ise operation ==lower_bound== kehte hain — "pehla slot jo $x$ se chhota nahi."

KYUN. Do cheezein ho sakti hain aur dono us position se decide hoti hain:

Agar aisa $k$ exist karta hai, toh $x$ length- $(k + 1)$ chains ke liye ek better (chhoti) tail ban sakta hai, isliye hum $tails [k] = x$ overwrite karte hain. Humne koi chain lambi nahi ki — humne ek existing length ko baad mein extend karna sasta kar diya.
Agar koi slot $\geq x$ nahi hai (matlab $x$ har tail se bada hai), toh $x$ currently-longest chain ke upar chadh jaata hai aur hum use append karte hain, record length ek se badh jaati hai.

$\geq$ kyun, $>$ nahi. Hum strictly increasing subsequences chahte hain. Pehle tail ko equal to $x$ replace karna ek duplicate value ko extension ki tarah treat hone se rokta hai (tie koi increase nahi hai). Agar problem non-decreasing runs allow karti, toh hum first tail strictly $> x$ dhundhhte. Yeh ek comparison choice hi dono variants ka ek-matra difference hai.

PICTURE. Figure s04: sorted tails array ek number line ki tarah; red marker lower_bound ko pehle tail $\geq x$ par land karte dikhata hai, saath mein "replace here" arrow.

Step 5 — Dekhte hain yeh chalta kaise hai, frame by frame

KYA. Hum $A = [3, 1, 4, 1, 5, 9, 2, 6]$ ke saare elements rule se push karte hain aur har step ke baad tails record karte hain.

KYUN. Tracing abstract rule ko muscle memory mein badal deti hai, aur yeh do interesting moves surface karta hai — ek replace jo ek tail ko lower karta hai aur ek append jo length badhata hai.

$x$	leftmost tail $\geq x$ ?	action	`tails` baad mein
3	koi nahi	append	`[3]`
1	$3 \geq 1$ at $k = 0$	replace	`[1]`
4	koi nahi	append	`[1,4]`
1	$1 \geq 1$ at $k = 0$	replace	`[1,4]`
5	koi nahi	append	`[1,4,5]`
9	koi nahi	append	`[1,4,5,9]`
2	$4 \geq 2$ at $k = 1$	replace	`[1,2,5,9]`
6	$9 \geq 6$ at $k = 3$	replace	`[1,2,5,6]`

Final length $= len (tails) = 4$ . ✓

PICTURE. Figure s05 in saare frames mein baadhte tails staircase ko overlay karta hai; red segment woh value hai jo har moment mein replace/append ho rahi hai.

Step 6 — Edge aur degenerate cases (reader ko kabhi stranded mat chhodo)

KYA + KYUN + PICTURE, ek-ek row. Figure s06 mein saare chaar side by side hain.

Empty array []: loop kabhi chalta hi nahi, tails [] rehta hai, length $= 0$ . Sahi — koi elements nahi, koi subsequence nahi.
Strictly decreasing [5,4,3,2,1]: har $x$ , tails mein sab kuch se $\leq$ hai, isliye har step position $0$ replace karta hai. tails length $1$ se zyada kabhi nahi badhta → $L = 1$ . Sahi: sabse lambi rising chain koi bhi single element hai.
Strictly increasing [1,2,3,4,5]: koi bhi cheez kabhi $\geq x$ nahi hoti jo block kar sake, har $x$ append hota hai → tails har step mein badhta hai → $L = n$ . Sahi: poora array pehle se hi rise karta hai.
Sab equal [7,7,7,7]: strict LIS ke liye hum $\geq$ use karte hain, isliye har $7$ existing $7$ ko $k = 0$ par dhundhhta hai aur replace karta hai, kabhi append nahi → $L = 1$ . Sahi: equal values koi increase nahi hain. (Non-decreasing rules ke saath $>$ use karte toh, yeh $L = 4$ deta — exactly isliye $\geq$ vs $>$ choice matter karti hai.)

Recall Decreasing case mein kabhi append kyun nahi hoti?

Append tab hoti hai jab $x$ saare current tails se zyada ho. Decreasing array mein har naya $x$ saari dekhi gayi cheezein se chhota hota hai, isliye lower_bound hamesha position $0$ par land karti hai aur hum replace karte hain — length $1$ par rehti hai.

Ek-picture summary

Yeh final figure poori derivation ko fuse karta hai: raw array heights ki tarah (upar), sorted tails staircase jo hum maintain karte hain (beech mein, red = smallest-tail invariant), aur ek single decision box (neeche) — lower_bound, phir replace-or-append. Jitni baar hum kabhi append karte hain, woh count $L$ ke barabar hai, aur kyunki tails force-sorted hai (Step 3) isliye har decision sirf $O (lo g n)$ cost karta hai.

Recall Feynman: poora walkthrough kisi 12-saal ke bacche ko batao

Apne cards left to right line up karo. Tum piles ki ek row rakhte ho. Jab naya card aata hai, apni piles ko left se chalo aur card ko pehli aisi pile par daal do jiska top tumhare card se chhota nahi — tum us top ko apne (chhote-ya-barabar) card se cover karte ho. Agar koi pile nahi le sakti (tumhara card har top ko beat karta hai), right par ek bilkul naya pile shuru karo. Chhote card se kyun cover karte ho? Kyunki ek chhota top future cards ke liye beat karna aasaan hai, isliye zyada cards baad mein pile up ho sakte hain. Ant mein, apni piles gino — woh count hi tumhare deck mein chhipi hamesha-chadhhti cards ki line ki length hai. "Left se pehli pile" bas sorted row of pile-tops par Binary Search hai, aur yahi poora $O (n lo g n)$ trick hai — yeh card game Patience Sorting hai.

Connections

Binary Search — sorted-tails invariant (Step 3) woh cheez hai jo lower_bound ko legal banata hai.
Patience Sorting — Feynman retelling mein card-pile picture.
Dynamic Programming — woh $O (n^{2})$ cousin jise yeh fast method optimize karta hai.
Greedy Algorithms — "keep smallest tails" ek greedy exchange argument hai, Step 2 mein prove kiya gaya.
Longest Common Subsequence (LCS) — ek related subsequence problem.
Russian Doll Envelopes — LIS ke upar layered ek 2D application.