Sign in
Skip to solution
mediumDSA

How do you find the longest increasing subsequence?

269 views
01

Understand the problem

Explain LIS.

dpsubsequence
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

The O(n²) DP sets dp[i] = longest LIS ending at i. The optimal O(n log n) approach keeps a tails array of the smallest possible tail for each length, binary-searching where each element fits — the array's length is the LIS length.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Patience sort (binary search)
Run Playground
import bisect

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)       # x extends the longest run
        else:
            tails[i] = x          # x is a smaller tail for that length
    return len(tails)


# --- demo ---
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))   # 4  (e.g. 2,3,7,18)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 84 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track