Skip to content

Volume ITechnology

4.23.11 — Longest Increasing Subsequence ​

LeetCode 300 · Medium · ★ Blind 75

The problem ​

Return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.

[10,9,2,5,3,7,101,18]   →  4     ([2,3,7,101])
[0,1,0,3,2,3]           →  4     ([0,1,2,3])
[7,7,7,7]               →  1     (strictly increasing, so no repeats)

Up to 2,500 elements. The follow-up asks for O(n \log n).

The brute force, and where it wastes work ​

The brute force way is to generate all possible subsequences of the array and check if they are strictly increasing. Since every element can either be included or excluded, there are 2^N possible subsequences. Generating them all and validating them takes O(N \cdot 2^N) time. For N=2500, 2^{2500} is an astronomically large number. We definitely need a polynomial time DP approach.

Subsequence, not subarray — gaps are allowed. That single word rules out sliding windows and rules in DP.

The O(n^2) DP ​

Let dp[i] be the length of the longest increasing subsequence that ends at index i.

The phrase "ends at" is doing all the work. Without it you cannot extend anything, because you would not know what the last element was.

To compute dp[i], look at every earlier index j. If nums[j] < nums[i], then the subsequence ending at j can be extended by nums[i]:

dp[i] = 1 + \max\{\,dp[j] \ :\ j < i,\ nums[j] < nums[i]\,\}

and dp[i] = 1 if no such j exists — the element alone.

The answer is the maximum over the whole table, not dp[n-1], because the best subsequence may end anywhere. That is the second most common mistake in this problem.

python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)                      # (1) every element alone is length 1

        for i in range(len(nums)):  # (2)
            for j in range(i):  # (3)
                if nums[j] < nums[i]:  # (4)
                    dp[i] = max(dp[i], dp[j] + 1)  # (5)

        return max(dp)  # (6)

O(n^2) time, O(n) space. Write this first. It is obviously correct and it is the answer if the follow-up never comes.

Line by line. Here dp[i] means "the length of the longest increasing subsequence that ends at nums[i]". (1) Every number on its own is an increasing subsequence of length 1. (2) For each position i, (3) look at every earlier position j. (4) If nums[j] is smaller, nums[i] can be added to the end of any increasing subsequence that ends at j. (5) That makes one of length dp[j] + 1, so keep the longest such option. (6) The longest subsequence can end anywhere, so the answer is the largest dp value. Two loops over n positions give O(n^2).

The O(n \log n) solution ​

This one is worth real attention, because the array it maintains is not what people assume.

Keep an array tails, where tails[k] is the smallest possible value that can end an increasing subsequence of length k + 1, among everything seen so far.

For each new number, find the first entry in tails that is greater than or equal to it, and overwrite that entry. If no entry qualifies, append.

python
import bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []  # (7)

        for n in nums:  # (8)
            i = bisect.bisect_left(tails, n)      # (9) first index with tails[i] >= n
            if i == len(tails):  # (10)
                tails.append(n)                   # extends the longest run
            else:
                tails[i] = n                      # (11) a smaller tail for that length

        return len(tails)  # (12)
ts
function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];  // (7)

  for (const n of nums) {  // (8)
    let lo = 0, hi = tails.length;  // (9)
    while (lo < hi) {                             // first index with tails[i] >= n
      const mid = (lo + hi) >> 1;
      if (tails[mid] < n) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(n);  // (10)
    else tails[lo] = n;  // (11)
  }

  return tails.length;  // (12)
}

Line by line ​

(7) tails[k] is the smallest number that can end an increasing subsequence of length k + 1, using the numbers seen so far. It is not an actual subsequence. Its numbers can come from different subsequences. But it is always sorted from small to large, which is what lets us binary search it.

(8) Take each number in turn.

(9) Find the first entry in tails that is at least n. bisect_left is Python's built-in binary search for exactly this. TypeScript writes the same search by hand: shape B from 4.11.1. (lo + hi) >> 1 is a quick way to halve and round down.

(10) Every entry is smaller than n, so n can extend the longest subsequence so far. Add it at the end. The longest length grows by one.

(11) Otherwise, n replaces that entry. There is now a subsequence of that length ending in a smaller number, n. A smaller ending is better, because it leaves more room for later numbers to extend it.

(12) The number of entries is the length of the longest increasing subsequence.

The two things people get wrong ​

tails is not the longest increasing subsequence. Its length is correct; its contents are usually not a real subsequence of the input. It is a set of best-possible endings, one per length. Do not return it as the answer to "give me the subsequence".

Why overwriting is safe. If you can end a length-3 subsequence with 7, and later you find you can end one with 5, then 5 is strictly better — every future number that could extend the 7 can also extend the 5, and some that could not extend 7 can extend 5. Keeping the smaller tail never loses an option.

Why tails stays sorted. A longer subsequence must end at a value at least as large as a shorter one's best ending, so the array is increasing by construction — which is what makes binary search legal.

bisect_left, not bisect_right. bisect_left finds the first entry ≥ n, so an equal value gets overwritten rather than appended, which is what "strictly increasing" requires. Switch to bisect_right and you get the longest non-decreasing subsequence — a one-word change in the problem, a one-function change in the code, and a good thing to point out.

Trace ​

[10, 9, 2, 5, 3, 7, 101, 18]

ntails beforeactiontails after
10[]append[10]
9[10]overwrite index 0[9]
2[9]overwrite index 0[2]
5[2]append[2,5]
3[2,5]overwrite index 1[2,3]
7[2,3]append[2,3,7]
101[2,3,7]append[2,3,7,101]
18[2,3,7,101]overwrite index 3[2,3,7,18]

Length 4 ✓. Note the final tails is [2,3,7,18], which is a valid subsequence here — but that is luck, not a guarantee.

O(n \log n) time, O(n) space.

Time Complexity Derivation: We loop through the N numbers exactly once. For each number, we do a binary search (bisect_left) over the tails array. The tails array has at most size N. Binary search on an array of size N takes O(\log N) time. So N iterations \times O(\log N) work per iteration = O(N \log N) total time.

Space Complexity Derivation: We maintain a tails array which in the worst case (a completely strictly increasing array) will store all N elements. Thus, space is O(N).

Edge cases ​

  • One number. The answer is 1.
  • Numbers that only go down. Each new number replaces the first entry, so tails stays length 1.
  • Repeated numbers, like [7, 7, 7]. "Increasing" means strictly bigger, so the answer is 1. Using bisect_left, which finds the first entry at least n, makes an equal number replace rather than extend.

Recovering the actual subsequence ​

If asked for the subsequence rather than its length, keep for each element the index it was placed at in tails, plus a parent pointer to whatever was at the previous position when it was placed. Then walk the parents backwards from the last append.

Say that reconstruction needs extra bookkeeping, because it is the natural follow-up and a lot of people assume tails already is the answer.

Where this goes next ​

  • Russian Doll Envelopes — sort by width ascending and by height descending within equal widths, then run LIS on the heights. The descending tie-break is what stops two envelopes of equal width being nested, and it is the whole trick.
  • Number of Longest Increasing Subsequences — count as well as measure, which needs a second table.
  • Longest Increasing Path in a Matrix — the grid version, solved with memoised DFS. 4.24.
  • Maximum Length of Pair Chain, Longest String Chain — sort first, then LIS.

The pattern to carry: "longest chain under some ordering" is LIS after a sort. Recognising it is what makes Russian Doll Envelopes a five-minute problem instead of a new one.

What the interviewer will push on ​

"What does dp[i] mean?" The longest increasing subsequence ending at i. The "ending at" is not optional.

"Why is the answer max(dp) and not dp[n-1]?" The best subsequence can end anywhere.

"What does tails hold?" The smallest possible tail for each length. Not an actual subsequence.

"Why is it safe to overwrite?" A smaller tail for the same length dominates a larger one — it can be extended by strictly more values.

"Why is tails sorted?" Longer subsequences need larger endings.

"Strictly increasing or non-decreasing?" bisect_left versus bisect_right.

"Can you return the subsequence itself?" Yes, with parent pointers.

One thing to volunteer: say clearly that tails is not the answer subsequence. It is the single most common misunderstanding of this algorithm, and correcting it unprompted shows you understand what the array is for.

Next: 4.23.12 Partition Equal Subset Sum — knapsack in disguise, and the loop direction that stops an item being reused.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet