Skip to content

019 — LIS in O(n log n)

Source

  • 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 থেকে

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 দিয়ে।

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

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 যা বলে।

6. Real-life analogy

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

7. Visual explanation

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 বাড়ে।

8. Example input and 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)

9. Brute force thinking

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

সব 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-এর জন্য):

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, এটুকুই পুরো গতি-লাফ।

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

15. Python solution

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 যে ঠিক, তা এর সাথে মিলিয়ে নিশ্চিত করা হয়।

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

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

21. Which basic problem this inherits from

ভিত্তি: #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-এ শেখা।

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "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।