How do you find the longest increasing subsequence?

Q: How do you find the longest increasing subsequence?

**Target Audience:** Beginners preparing for coding interviews — you need loops, lists and the idea of binary search. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First You are hiking and you write down the altitude every hour: 10, 9, 2, 5, 3, 7, 101, 18. Later a friend asks: "What is the longest climb you could describe by picking readings in order, each one higher than the last?" You may skip readings, but you may not reorder them. 2 → 5 → 7 → 101 works, and so does 2 → 3 → 7 → 18. Both have four readings, and no five-reading climb exists. That is the **

The problem

Question presented to candidate: "Given an array of integers, return the length of its longest strictly increasing subsequence. Start with whatever works, then make it faster, and tell me how you would return the subsequence itself. Please code it in Python."

What a strong answer should cover:

The O(n²) DP: dp[i] = LIS length ending at i, dp[i] = 1 + max(dp[j]) over earlier smaller nums[j], answer = max(dp) (not dp[-1]).
The O(n log n) idea: tails[k] = smallest possible tail of an increasing subsequence of length k + 1; tails stays sorted, so each number is placed with one binary search.
That tails is not itself an LIS, and how parent pointers rebuild a real one.
Strict vs non-decreasing: bisect_left vs bisect_right.
Python details: the bisect module, max(dp) raising ValueError on an empty list, and why the O(n²) double loop is slow in pure Python for n in the tens of thousands.

Clarifying questions expected:

Strictly increasing or non-decreasing?
Length only, or the subsequence too?
How large can n be?

Code / implementation expected: Yes — the O(n log n) tails solution with bisect_left in Python; the O(n²) DP is a good first step to mention or write.

dp
subsequence

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you need loops, lists and the idea of binary search.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

You are hiking and you write down the altitude every hour: 10, 9, 2, 5, 3, 7, 101, 18. Later a friend asks: "What is the longest climb you could describe by picking readings in order, each one higher than the last?" You may skip readings, but you may not reorder them. 2 → 5 → 7 → 101 works, an

The solution is hidden so you can try first

10 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonLIS by O(n^2) DP and by the O(n log n) tails array, with the subsequence rebuilt