Problem link ও উৎস
- **Original source:** Classic patience-sorting / binary-search LIS exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming + binary search
- **Difficulty:** Hard
- **Pattern:** LIS family + binary search
- **Basic idea inherited from:** #15 LIS in O(n²) — একই problem, কিন্তু inner `max`-search-কে binary search দিয়ে replace করে complexity নামানো; binary search এসেছে folder 03/04 থেকে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `nums` দেওয়া। সবচেয়ে লম্বা **strictly increasing subsequence**-এর length বের করো — subsequence মানে order রেখে কিছু element বাদ দিয়ে যা পাও (contiguous লাগে না)। এটা ঠিক #15-এর problem, কিন্তু এবার লক্ষ্য O(n²) নয়, **O(n log n)** — patience sorting আর binary search দিয়ে।
```text
nums = [10, 9, 2, 5, 3, 7, 101, 18]
সবচেয়ে লম্বা increasing: [2, 3, 7, 101] (বা [2, 3, 7, 18]) -> length 4
```
### Input ও output {#8-example-input-and-output}
```text
Input : [10, 9, 2, 5, 3, 7, 101, 18] -> Output: 4
Input : [0, 1, 0, 3, 2, 3] -> Output: 4 ([0,1,2,3])
Input : [7, 7, 7, 7] -> Output: 1 (strictly increasing)
Edge case 1: [5] -> Output: 1
Edge case 2: [5, 4, 3, 2, 1] -> Output: 1 (decreasing)
Edge case 3: [1, 2, 3, 4, 5] -> Output: 5 (already increasing)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
Patience (একধরনের তাস-খেলা) ভাবো: তাস একে একে আসছে, তুমি pile বানাচ্ছ। নতুন তাস এমন বাঁ-দিকের pile-এ রাখো যার উপরের তাস তার চেয়ে বড়-বা-সমান; এমন pile না থাকলে নতুন pile খোলো ডানে। শেষে pile-এর সংখ্যাই LIS-length। প্রতিটা pile-এর উপরের তাস হলো `tails[k]` — আর "সঠিক pile" খোঁজাটাই binary search।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি #15 LIS in O(n²)। সেখানে `dp[i]` = "ঠিক i-তে শেষ হওয়া" LIS-length, আর প্রতিটা `i`-এর জন্য সব আগের `j` ঘেঁটে `max` নিতাম — সেটাই O(n) per element, মোট O(n²)। এখানে problem অপরিবর্তিত, কিন্তু আমরা একটা চতুর data structure ("tails" array) রাখি, যাতে ওই linear search একটা binary search হয়ে যায় — প্রতি element O(log n), মোট O(n log n)। ভালো tool দিয়ে একই problem আবার solve করা নিজেই একটা skill।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা `tails` array রাখা: `tails[k]` = length `(k+1)`-এর সব increasing subsequence-এর মধ্যে সবচেয়ে **ছোট সম্ভব শেষ-element**। মূল গাণিতিক সত্য: `tails` সবসময় **strictly increasing** থাকে। তাই নতুন একটা `x`-এর জন্য আমরা `tails`-এ binary search করে প্রথম `>= x` element খুঁজি; সেটা থাকলে overwrite করি (একই length, ছোট tail = ভবিষ্যতের জন্য বেশি জায়গা), না থাকলে শেষে append করি (LIS এক বাড়ল)। `tails`-এর length-ই উত্তর।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **array** `tails` (Python-এ list), যেখানে binary search চালানো হয় — `bisect_left`। এটা সত্যিকারের subsequence ধরে রাখে না, শুধু প্রতি length-এর সবচেয়ে ভালো (ছোট) tail। আকার সর্বোচ্চ `n`, কিন্তু সাধারণত LIS-length-এর সমান।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`tails` strictly increasing থাকে — এই invariant-টাই binary search-কে বৈধ করে। আমরা প্রতি length-এর জন্য শুধু একটা সংখ্যা (সেরা tail) মনে রাখি, কারণ future decision-এ এটুকুই দরকার: "x কি কোনো subsequence extend করতে পারে?" পুরো subsequence বহন করা অপ্রয়োজনীয় ভার — তাই minimal state-এ চলি, ঠিক doctrine যা বলে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা subsequence enumerate করে increasing-গুলোর মধ্যে সবচেয়ে লম্বাটা নাও।
```text
সব 2^n subsequence দেখো:
প্রতিটার জন্য check strictly increasing কি না
increasing হলে length track করো
answer = max length
```
(O(n²) DP version #15-এ আছে; এখানে আমরা তার চেয়েও দ্রুত যেতে চাই।)
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সব subsequence enumerate করা **O(2^n)** — exponential, ছোট array-তেও অচল। #15-এর O(n²) DP অনেক ভালো, কিন্তু প্রতি element-এ সব আগের element ঘাঁটার linear search-টাই bottleneck: n বড় (যেমন 10^5) হলে n² = 10^10 — সেটাও ধীর। তাই ওই inner search-কে binary search দিয়ে log করতে হবে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একই length-এর subsequence-গুলোর মধ্যে শুধু **সবচেয়ে ছোট tail-টাই** মনে রাখা যথেষ্ট, কারণ ছোট tail ভবিষ্যতে বেশি element-কে extend করতে দেয়। আর সেই tail-গুলো length-এর সাথে strictly increasing — তাই সঠিক জায়গা binary search-এ পাওয়া যায়, পুরো scan লাগে না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `tails[k]` = length `(k+1)`-এর যেকোনো strictly increasing subsequence-এর সম্ভব সবচেয়ে ছোট শেষ-element। (এটাই "patience" view — DP state কিন্তু array-আকারে compressed।)
**Transition (প্রতি `x`-এর জন্য):**
```text
pos = bisect_left(tails, x) # প্রথম index যেখানে tails[index] >= x
if pos == len(tails):
tails.append(x) # x সব tail-এর চেয়ে বড় -> LIS এক বাড়ল
else:
tails[pos] = x # একই length, কিন্তু ছোট tail
```
**Base case:** `tails = []` (শুরুতে কোনো subsequence নেই)।
**Answer location:** `len(tails)` — সব element process করার পরে।
এটা O(n²) DP-র সাথে সম্পর্কিত: `bisect_left`-এর `pos` আসলে "x-এ শেষ হওয়া LIS-এর length − 1"। তাই চাইলে `dp[i] = pos + 1` রেখে আগের anchor-চিন্তার সাথেও মেলানো যায়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা element-এ আগের সব কিছু ঘাঁটব" — এর বদলে length-অনুযায়ী **শুধু সেরা tail** ধরে রাখো। তাহলে নতুন `x`-এর জন্য প্রশ্নটা হয় "কোন length পর্যন্ত subsequence-কে x extend করতে পারে?" — আর যেহেতু tails increasing, এর উত্তর binary search। O(n) search → O(log n) search, এটুকুই পুরো গতি-লাফ।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [10, 9, 2, 5, 3, 7, 101, 18]`, `tails` ধাপে ধাপে:
```text
x = 10 : tails empty -> append -> [10]
x = 9 : 9 replaces 10 (first >=9) -> [9]
x = 2 : 2 replaces 9 -> [2]
x = 5 : 5 > all -> append -> [2, 5]
x = 3 : 3 replaces 5 (first >=3) -> [2, 3]
x = 7 : 7 > all -> append -> [2, 3, 7]
x = 101: 101 > all -> append -> [2, 3, 7, 101]
x = 18 : 18 replaces 101 -> [2, 3, 7, 18]
len(tails) = 4 <- answer
```
লক্ষ্য করো `tails` সবসময় increasing; replace হলে length একই থাকে (শুধু tail ছোট হয়), append হলে length বাড়ে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`nums = [4, 2, 3, 1, 5]`, `tails` শুরু `[]`:
1. x=4: empty, `pos=0=len` → append → `[4]`
2. x=2: `bisect_left([4],2)=0` → `tails[0]=2` → `[2]`
3. x=3: `bisect_left([2],3)=1=len` → append → `[2,3]`
4. x=1: `bisect_left([2,3],1)=0` → `tails[0]=1` → `[1,3]`
5. x=5: `bisect_left([1,3],5)=2=len` → append → `[1,3,5]`
6. `len(tails) = 3` → answer
হাতে মিলিয়ে: LIS যেমন `[2,3,5]` — length 3. ✔ (`tails`-এর `[1,3,5]` নিজে কোনো সত্যিকারের subsequence নাও হতে পারে; শুধু length-টাই অর্থবহ।)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from bisect import bisect_left
# ---- way 1: O(n log n) patience + binary search ----
def lis_fast(nums):
tails = []
for x in nums:
pos = bisect_left(tails, x) # প্রথম index, tails[index] >= x
if pos == len(tails):
tails.append(x) # LIS এক বাড়ল
else:
tails[pos] = x # একই length, ছোট tail
return len(tails)
# ---- way 2: same idea, manual binary search (bisect ছাড়া) ----
def lis_manual(nums):
tails = []
for x in nums:
lo, hi = 0, len(tails) # প্রথম index >= x খুঁজি
while lo < hi:
mid = (lo + hi) // 2
if tails[mid] < x:
lo = mid + 1
else:
hi = mid
if lo == len(tails):
tails.append(x)
else:
tails[lo] = x
return len(tails)
# ---- way 3: O(n^2) reference (#15) -- দ্রুত version মেলানোর জন্য ----
def lis_n2(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# ---- tests ----
cases = [
([10, 9, 2, 5, 3, 7, 101, 18], 4),
([0, 1, 0, 3, 2, 3], 4),
([7, 7, 7, 7], 1),
([5], 1),
([5, 4, 3, 2, 1], 1),
([1, 2, 3, 4, 5], 5),
([4, 2, 3, 1, 5], 3),
([], 0),
]
for nums, want in cases:
assert lis_fast(nums) == want, (nums, lis_fast(nums))
assert lis_manual(nums) == want, (nums, lis_manual(nums))
assert lis_n2(nums) == want, (nums, lis_n2(nums)) # দুই version মেলে
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `lis_fast`: প্রতি `x`-এ `bisect_left` প্রথম `>= x` index দেয়; index শেষে হলে append (LIS বাড়ল), নয়তো ওই জায়গায় overwrite (tail ছোট করো); answer `len(tails)`।
- `lis_manual`: একই algorithm, কিন্তু binary search নিজে হাতে লেখা — `tails[mid] < x` হলে ডানে যাও, নয়তো বাঁয়ে; দেখায় `bisect` ভেতরে কী করছে।
- `lis_n2`: #15-এর O(n²) reference; প্রতি `i`-তে সব আগের `j` ঘেঁটে `dp[i]` বাড়ায়। দুই দ্রুত version যে ঠিক, তা এর সাথে মিলিয়ে নিশ্চিত করা হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ আটটা input: classic mixed, `[0,1,0,3,2,3]` (4), সব-সমান `[7,7,7,7]` (strictly বলে 1), single, সম্পূর্ণ decreasing (1), already-increasing (5), small `[4,2,3,1,5]` (3), আর খালি array (0)। প্রতিটার জন্য তিন function-ই (দুই দ্রুত + এক O(n²) reference) একই উত্তর দিতে হবে — এটাই দ্রুত version-এর correctness-এর প্রমাণ। সব pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
- `lis_fast` / `lis_manual`: **O(n log n)** — প্রতি element-এ একটা binary search।
- `lis_n2`: **O(n²)** — reference।
### অতিরিক্ত জায়গা {#19-space-complexity}
- তিন version-ই **O(n)** — `tails` (বা `dp`) array; recursion নেই।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- strictly বনাম non-strictly গুলিয়ে ফেলা: strictly increasing-এ `bisect_left` (প্রথম `>= x`); non-strictly (≤) চাইলে `bisect_right` লাগবে। `[7,7,7,7]`-এর উত্তর strictly-তে 1, non-strictly-তে 4 — তাই function-টাই বদলে যায়।
- `tails`-কে সত্যিকারের subsequence ভেবে ফেলা — এটা শুধু per-length সেরা tail; length-টাই অর্থবহ, ভেতরের sequence নয়।
- empty array-তে `max(dp)` crash (#15-এ); দ্রুত version-এ `len([]) = 0` নিরাপদ, কিন্তু reference-এ আলাদা guard লাগে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #15 LIS in O(n²)-এর "ends-at-i" anchor। [../patterns.md](../patterns.md)-এর "LIS family" section বলে দেয় যে O(n log n) version binary search বা Fenwick tree দিয়ে আসে; binary search-এর যন্ত্রটা folder 03/04-এ শেখা।
### পরের অনুশীলন {#22-similar-harder-problems}
- Russian Doll Envelopes (এক dimension sort, অন্যটায় LIS) —