কনটেন্টে যান

019 — LIS in O(n log n)

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: Classic patience-sorting / binary-search LIS exercise
  • Platform: LeetCode — https://leetcode.com/problems/longest-increasing-subsequence/
  • 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 থেকে

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা array nums দেওয়া। সবচেয়ে লম্বা strictly increasing subsequence-এর length বের করো — subsequence মানে order রেখে কিছু element বাদ দিয়ে যা পাও (contiguous লাগে না)। এটা ঠিক #15-এর problem, কিন্তু এবার লক্ষ্য O(n²) নয়, O(n log n) — patience sorting আর binary search দিয়ে।

উদাহরণ
nums = [10, 9, 2, 5, 3, 7, 101, 18]
সবচেয়ে লম্বা increasing: [2, 3, 7, 101] (বা [2, 3, 7, 18]) -> length 4

Input ও output

উদাহরণ
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)

চেনা উদাহরণে বোঝা

Patience (একধরনের তাস-খেলা) ভাবো: তাস একে একে আসছে, তুমি pile বানাচ্ছ। নতুন তাস এমন বাঁ-দিকের pile-এ রাখো যার উপরের তাস তার চেয়ে বড়-বা-সমান; এমন pile না থাকলে নতুন pile খোলো ডানে। শেষে pile-এর সংখ্যাই LIS-length। প্রতিটা pile-এর উপরের তাস হলো tails[k] — আর "সঠিক pile" খোঁজাটাই binary search।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি #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।

ভেতরের যুক্তি

লুকানো 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-ই উত্তর।

কী দিয়ে তথ্য রাখব

একটা array tails (Python-এ list), যেখানে binary search চালানো হয় — bisect_left। এটা সত্যিকারের subsequence ধরে রাখে না, শুধু প্রতি length-এর সবচেয়ে ভালো (ছোট) tail। আকার সর্বোচ্চ n, কিন্তু সাধারণত LIS-length-এর সমান।

এটি কেন উপযুক্ত

tails strictly increasing থাকে — এই invariant-টাই binary search-কে বৈধ করে। আমরা প্রতি length-এর জন্য শুধু একটা সংখ্যা (সেরা tail) মনে রাখি, কারণ future decision-এ এটুকুই দরকার: "x কি কোনো subsequence extend করতে পারে?" পুরো subsequence বহন করা অপ্রয়োজনীয় ভার — তাই minimal state-এ চলি, ঠিক doctrine যা বলে।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা subsequence enumerate করে increasing-গুলোর মধ্যে সবচেয়ে লম্বাটা নাও।

উদাহরণ
সব 2^n subsequence দেখো:
    প্রতিটার জন্য check strictly increasing কি না
    increasing হলে length track করো
answer = max length

(O(n²) DP version #15-এ আছে; এখানে আমরা তার চেয়েও দ্রুত যেতে চাই।)

কোথায় বেশি কাজ হচ্ছে

সব 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 করতে হবে।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একই length-এর subsequence-গুলোর মধ্যে শুধু সবচেয়ে ছোট tail-টাই মনে রাখা যথেষ্ট, কারণ ছোট tail ভবিষ্যতে বেশি element-কে extend করতে দেয়। আর সেই tail-গুলো length-এর সাথে strictly increasing — তাই সঠিক জায়গা binary search-এ পাওয়া যায়, পুরো scan লাগে না।

আরও কম কাজে সমাধান

State (শব্দে): tails[k] = length (k+1)-এর যেকোনো strictly increasing subsequence-এর সম্ভব সবচেয়ে ছোট শেষ-element। (এটাই "patience" view — DP state কিন্তু array-আকারে compressed।)

Transition (প্রতি x-এর জন্য):

উদাহরণ
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-চিন্তার সাথেও মেলানো যায়।

ভাবনার পরিবর্তন

মোচড়: "প্রতিটা element-এ আগের সব কিছু ঘাঁটব" — এর বদলে length-অনুযায়ী শুধু সেরা tail ধরে রাখো। তাহলে নতুন x-এর জন্য প্রশ্নটা হয় "কোন length পর্যন্ত subsequence-কে x extend করতে পারে?" — আর যেহেতু tails increasing, এর উত্তর binary search। O(n) search → O(log n) search, এটুকুই পুরো গতি-লাফ।

ছবিতে বোঝা

nums = [10, 9, 2, 5, 3, 7, 101, 18], tails ধাপে ধাপে:

উদাহরণ
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-এ ধাপে ধাপে

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-টাই অর্থবহ।)

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

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!।

খরচ ও সাধারণ ভুল

সময়

  • lis_fast / lis_manual: O(n log n) — প্রতি element-এ একটা binary search।
  • lis_n2: O(n²) — reference।

অতিরিক্ত জায়গা

  • তিন version-ই O(n) — tails (বা dp) array; recursion নেই।

যে ভুলগুলো এড়াতে হবে

  • 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 লাগে।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: #15 LIS in O(n²)-এর "ends-at-i" anchor। ../patterns.md-এর "LIS family" section বলে দেয় যে O(n log n) version binary search বা Fenwick tree দিয়ে আসে; binary search-এর যন্ত্রটা folder 03/04-এ শেখা।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Patience + binary search: length-অনুযায়ী সবচেয়ে ছোট tail-গুলো একটা strictly increasing array-তে রাখো; নতুন element-এর সঠিক জায়গা binary search-এ বের করে append বা overwrite করো; array-র length-ই উত্তর। এই trick যেকোনো "longest chain by binary search" problem-এ ফেরে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "LIS O(n log n) = patience piles + binary search।" State tails[k] = length (k+1)-এর সবচেয়ে ছোট সম্ভব tail, transition: bisect_left করে append (LIS বাড়ল) বা overwrite (tail ছোট), answer len(tails)। মনে রেখো: per-length শুধু সেরা tail রাখলেই inner search binary হয়ে যায় — এটাই O(n²) থেকে O(n log n)-এর লাফ।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।