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

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

Is page ko kaise use karein: Solution ko cover karo, problem try karo, phir reveal karo. Har level ek rung zyada hard hai — LIS ko recognize karne se lekar uske upar nayi algorithms banana tak. Yeh the parent LIS note ka exercise companion hai.

Shuru karne se pehle, ek one-screen refresher un do tools ka jo tum baar baar use karte rahoge:

Level 1 — Recognition

L1.1 — Subsequence hai ya nahi?

A = [3, 1, 4, 1, 5, 9, 2, 6] diya hai. Har candidate ke liye batao ki woh A ki valid increasing subsequence hai ya nahi: (a) [3,4,5,9], (b) [1,4,5,2,6], (c) [3,4,5,6], (d) [1,1,5,9].

Recall Solution

Ek valid increasing subsequence ke liye (1) original positions use karke same left-to-right order mein appear karna chahiye, aur (2) strictly increasing hona chahiye.

(a) [3,4,5,9] — positions 0,2,4,5, values badhti hain 3<4<5<9. ✅
(b) [1,4,5,2,6] — values increasing nahi hain (5 ke baad 2 neeche jaata hai). ❌
(c) [3,4,5,6] — positions 0,2,4,7, sab order mein hain, 3<4<5<6. ✅
(d) [1,1,5,9] — 1 is not < 1, equal values strict increase ko tod dete hain. ❌

Valid: (a) aur (c).

L1.2 — `dp` values padho

A = [2, 5, 3, 7] ke liye $O (n^{2})$ table $d p [0..3]$ fill karo aur answer do.

Recall Solution

i	A[i]	valid j (A[j]<A[i])	dp[i]
0	2	none	1
1	5	j=0 (2<5), dp0=1	2
2	3	j=0 (2<3), dp0=1	2
3	7	j=0,1,2 → max dp = 2	3

dp = [1,2,2,3], answer = 3 (e.g. [2,5,7] ya [2,3,7]).

Level 2 — Application

L2.1 — Full $O (n^{2})$ trace

A = [4, 10, 4, 3, 8, 9] par $O (n^{2})$ DP run karo. Poora dp array do aur ek optimal subsequence do.

Recall Solution

i	A[i]	predecessors j with A[j]<A[i] (dp)	dp[i]
0	4	—	1
1	10	j=0 (4<10, dp 1)	2
2	4	koi chhota nahi (4 not <4)	1
3	3	koi chhota nahi	1
4	8	j=0 (4,dp1), j=2 (4,dp1), j=3 (3,dp1) → max 1	2
5	9	j=0(4,1), j=2(4,1), j=3(3,1), j=4(8,dp2) → max 2	3

dp = [1,2,1,1,2,3], answer = 3. dp[5]=3 se trace back karo: 9 index 4 (8, dp 2) se aaya, jo index 0 ya 2 ya 3 (4 ya 3, dp 1) se aaya. Ek optimal: [4, 8, 9] (indices 0,4,5) ya [3,8,9].

L2.2 — Full patience-sorting trace

A = [7, 2, 8, 1, 3, 4, 10, 6] par patience sorting run karo. Har step ke baad tails dikhao aur final length do.

Recall Solution

lower_bound use karo (leftmost tails[k] >= x); replace karo, warna append karo.

x	search result	action	tails after
7	empty	append	`[7]`
2	tails[0]=7 ≥ 2	replace[0]	`[2]`
8	none ≥ 8	append	`[2,8]`
1	tails[0]=2 ≥ 1	replace[0]	`[1,8]`
3	tails[1]=8 ≥ 3	replace[1]	`[1,3]`
4	none ≥ 4	append	`[1,3,4]`
10	none ≥ 10	append	`[1,3,4,10]`
6	tails[3]=10 ≥ 6	replace[3]	`[1,3,4,6]`

Length = 4 (e.g. [2,3,4,10] ya [1,3,4,6]). Neeche pile figure dekho.

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

Level 3 — Analysis

L3.1 — Longest decreasing subsequence

A = [5, 1, 6, 2, 7, 3] diya hai, sabse lambi strictly decreasing subsequence ki length nikalo. Ek LIS engine reuse karo — nayi code mat banao.

Recall Solution

Key idea: A ki ek decreasing subsequence reversed comparison ki ek increasing subsequence hai. Do clean tricks hain, dono same length dete hain:

Har value ko negate karo: B = [-5,-1,-6,-2,-7,-3], phir B par LIS run karo.
Ya A ko reverse karo aur run karo longest decreasing = LIS of reversed if you flip sign; sabse simple negation trick hai.

B = [-5,-1,-6,-2,-7,-3] par LIS (patience) run karo:

x	tails
-5	`[-5]`
-1	`[-5,-1]`
-6	`[-6,-1]`
-2	`[-6,-2]`
-7	`[-7,-2]`
-3	`[-7,-3]`

Length = 2. Original par check karo: decreasing pairs jaise [5,1], [6,2], [7,3] — length 2, aur koi length-3 decreasing chain exist nahi karti (array baar baar upar jaata rehta hai). ✅

L3.2 — $O (n lo g n)$ kyun aur $O (n^{2})$ kyun nahi: kaam count karo

A ki length $n = 1, 000, 000$ ke liye, har method roughly kitne primitive comparisons karta hai? Batao kaunsa term dominate karta hai.

Recall Solution

$O (n^{2})$ : $j < i$ par inner loop lagbhag $\frac{n ( n - 1 )}{2} \approx \frac{n ^{2}}{2} = 5 \times 1 0^{11}$ comparisons karta hai. Ek second ke runtime ke liye bahut zyada hai.
$O (n lo g n)$ : $n$ elements mein se har ek tails par ek binary search trigger karta hai (length $\leq n$ ), jisme $⌈ lo g_{2} n ⌉$ comparisons lagte hain. Yahan $lo g_{2} (1 0^{6}) \approx 20$ , toh lagbhag $n lo g_{2} n \approx 2 \times 1 0^{7}$ comparisons.
Ratio $\approx \frac{5 \times 1 0 ^{11}}{2 \times 1 0 ^{7}} = 25, 000 \times$ faster. $n^{2}$ term dominate karta hai aur isliye hum predecessor ke liye linear scan ko binary search se replace karte hain.

Level 4 — Synthesis

L4.1 — LIS ki count (sirf length nahi)

A = [1, 3, 5, 4, 7] ke liye LIS length aur kitne distinct LIS use achieve karte hain, dono nikalo.

Recall Solution

DP ko ek doosre array cnt[i] se extend karo = i par khatam hone wale LIS ki count. Rule: har i ke liye, sab j<i ke liye jahan A[j]<A[i]:

agar dp[j]+1 > dp[i]: dp[i]=dp[j]+1 set karo, cnt[i]=cnt[j] (ek strictly longer tarika mila — count reset karo).
agar dp[j]+1 == dp[i]: cnt[i] += cnt[j] (same best length ka ek aur tarika).

i	A[i]	dp[i]	cnt[i]	reasoning
0	1	1	1	akela
1	3	2	1	0 se
2	5	3	1	1 se
3	4	3	1	1 se (3<4), dp 2+1=3, cnt=cnt[1]=1
4	7	4	2	2 se (dp3→4, cnt1) aur 3 se (dp3→4, cnt1) → total 2

Length = 4, LIS ki count = 2: [1,3,5,7] aur [1,3,4,7]. ✅

L4.2 — Sort karne ke liye minimum deletions

A = [4, 3, 6, 5, 8, 7] diya hai, kam se kam kitne elements delete karne honge taaki bacha hua array strictly increasing ho?

Recall Solution

Reframe: jo bhi rakhte ho woh strictly increasing subsequence hona chahiye, toh maximum rakhne ka matlab hai ek LIS rakhna. Minimum deletions $= n - LIS length$ . A = [4,3,6,5,8,7] par LIS run karo:

x	tails
4	`[4]`
3	`[3]`
6	`[3,6]`
5	`[3,5]`
8	`[3,5,8]`
7	`[3,5,7]`

LIS length = 3 (e.g. [3,5,7] ya [4,6,8]). $n = 6$ , toh minimum deletions $= 6 - 3 = 3$ . ✅

Level 5 — Mastery

L5.1 — Russian Doll Envelopes (2D LIS)

Envelopes [[5,4],[6,4],[6,7],[2,3]] (width, height). Ek envelope doosre ke andar tabhi fit hota hai jab dono width aur height strictly larger hon. Maximum kitne nest kar sakte ho? (Dekho Russian Doll Envelopes.)

Recall Solution

Trick: width ascending sort karo, aur equal widths ke liye height descending sort karo. Phir heights par plain LIS run karo.

Width asc kyun: nesting ke liye increasing width chahiye, toh envelopes ko width order mein left se right process karo.
Equal widths par height descending kyun: same width ke do envelopes kabhi nest nahi ho sakte (width strictly larger nahi). Unki heights ko descending sort karna guarantee karta hai ki height-LIS unme se zyada se zyada ek ko pick karega, kyunki ek descending run increasing subsequence nahi ho sakti.

Sort karo: widths 2,5,6,6. Do width-6 envelopes ki heights 7,4 descending sort hoti hain: [[2,3],[5,4],[6,7],[6,4]]. Heights sequence: [3, 4, 7, 4]. [3,4,7,4] par LIS run karo:

x	tails
3	`[3]`
4	`[3,4]`
7	`[3,4,7]`
4	tails[1]=4 ko 4 se replace karo → `[3,4,7]`

LIS = 3. Answer = 3: [2,3] ⊂ [5,4] ⊂ [6,7]. ✅

L5.2 — LCS ke zariye LIS (cross-check)

Parent claim karta hai $LIS (A) = LCS (A, sorted-unique (A))$ . Ise A = [3, 1, 2, 1, 3] par verify karo. (Dekho Longest Common Subsequence (LCS).)

Recall Solution

Kyun kaam karta hai: A ki ek increasing subsequence ek aisi subsequence hai jo A ke distinct values ki sorted list mein bhi same order mein appear karti hai. Dono mein sabse lambi common wahi LIS hai. Hum sorted-unique isliye use karte hain taaki equal values do baar match na ho sakein (yeh ise strictly increasing rakhta hai).

A = [3,1,2,1,3], sorted-unique(A) = [1,2,3].
[3,1,2,1,3] aur [1,2,3] ka LCS: common increasing run 1,2,3 — pehla 1 lo (index 1), 2 (index 2), 3 (index 4). Length 3.
A ka direct LIS: [1,2,3] → length 3. ✅ Dono match karte hain.

Connections

Dynamic Programming — L2, L4 direct DP-table drills hain.
Binary Search — har patience trace mein lower_bound.
Patience Sorting — L2.2 mein pile model (figure).
Longest Common Subsequence (LCS) — L5.2 reduction.
Greedy Algorithms — "keep smallest tails" exchange argument L2/L3 ke peeche.
Russian Doll Envelopes — L5.1 2D extension.

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

Level 1 — Recognition

L1.1 — Subsequence hai ya nahi?

L1.2 — `dp` values padho

Level 2 — Application

L2.1 — Full $O (n^{2})$ trace

L2.2 — Full patience-sorting trace

Level 3 — Analysis

L3.1 — Longest decreasing subsequence

L3.2 — $O (n lo g n)$ kyun aur $O (n^{2})$ kyun nahi: kaam count karo

Level 4 — Synthesis

L4.1 — LIS ki count (sirf length nahi)

L4.2 — Sort karne ke liye minimum deletions

Level 5 — Mastery

L5.1 — Russian Doll Envelopes (2D LIS)

L5.2 — LCS ke zariye LIS (cross-check)

Connections

Recap map