mediumDSA

How do you find the longest increasing subsequence?

Q: How do you find the longest increasing subsequence?

**Intuition.** Maintain a tails array where tails[i] is the **smallest possible tail** of any increasing subsequence of length i + 1 . For each number, binary-search the first tail ≥ it: replace it (a better, smaller tail for that length) or append it (a brand-new longest length). The array's length is the LIS length. tails holds smallest tail per length; binary-search each x [10,9,2,5,3,7,101,18] <rect x="

269 views

Understand the problem

Explain LIS.

dpsubsequence

Attempt it yourself

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

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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)

Join the discussion

Discussion (0)

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

How do you merge two sorted arrays?

How do you clone a graph?