Longest Increasing Subsequence (LeetCode 300)
You're given an integer array nums. Deleting any subset of its elements (possibly none) while keeping the rest in their original order produces a subsequence.
Find the length of the longest subsequence you can produce this way whose values keep strictly increasing from left to right.
Worked Examples
nums = [10,9,2,5,3,7,101,18]4nums = [0,1,0,3,2,3]40, 1, 2, 3 is strictly increasing and has length 4.nums = [7,7,7,7,7,7,7]1⚖️Formal Constraints & Bounds
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Core Insight
For every length, keep only the smallest value an increasing subsequence of that length can end with; each new number replaces the first such tail that is not smaller than it, or extends the list, so the list length is the answer.
Real-World Scenario & Production Applications
Version control DAG(Directed Acyclic Graph) sequence alignment, tournament streak tracking.
Subproblems & Recurrence Decomposition3 Phases
tails[k] is the smallest value that can end an increasing subsequence of length k + 1 among the numbers read so far. It starts empty, and it stays sorted.
tails = []Step-by-Step Execution Trace Table
| x | bisect_left(tails, x) | Action | tails after |
|---|---|---|---|
| 10 | 0 | append | [10] |
| 9 | 0 | replace 10 | [9] |
| 2 | 0 | replace 9 | [2] |
| 5 | 1 | append | [2, 5] |
| 3 | 1 | replace 5 | [2, 3] |
| 7 | 2 | append | [2, 3, 7] |
| 101 | 3 | append | [2, 3, 7, 101] |
| 18 | 3 | replace 101 | [2, 3, 7, 18] → 4 |
| 1 | tails = [] |
| 2 | for x in nums: |
| 3 | idx = bisect_left(tails, x) |
| 4 | idx == len(tails) ? tails.append(x) : tails[idx] = x |
| 5 | return len(tails) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the length of the longest strictly increasing subsequence can be solved in $O(N^2)$ via quadratic DP or in $O(N \log N)$ via Patience Sorting. We maintain an array `tails` where `tails[i]` stores the smallest tail element among all valid subsequences of length $i + 1$. For each number $x$, binary search (`bisect_left`) finds the first tail $\ge x$ and replaces it. If $x$ is larger than all tails, it appends to `tails`, increasing the maximum subsequence length. 🃏 The Analogy: Dealing Cards onto Piles
Deal the numbers left to right as cards. Each card goes on the leftmost pile whose top card is at least as big as it; if no pile qualifies, it starts a new pile on the right. The pile tops, read left to right, always climb, and the number of piles is the length of the longest increasing subsequence. tails is exactly the row of pile tops.
🔑 The Key Idea in the Code
The answer is len(tails), not tails itself: after [3, 4, 1] the tops are [1, 4], which is not a subsequence of the input, even though the length 2 is right.
Strictly increasing vs non-decreasing: Using
nums[j] <= nums[i]instead ofnums[j] < nums[i]. The problem specifies strictly increasing; duplicate values cannot extend the subsequence.Assuming the answer is
dp[-1]: The LIS does not necessarily end at the last element of the array; the global maximum can end anywhere. The result must bemax(dp).Defaulting to when is expected: For , DP gets TLE. Use patience sorting with binary search (
bisect_lefton a tails array).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Longest strictly increasing subsequence over arbitrary jump distances.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: tails is sorted, and tails[k] is the smallest last value of any increasing subsequence of length k + 1 seen so far.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Reading
tailsas the answer: it has the right length but is usually not a real subsequence ofnums, so store each element's predecessor index if you must rebuild the sequence.Using
bisect_rightinstead ofbisect_left: an equal value would then be appended and counted as increasing, so[7, 7, 7, 7, 7]would return 5 instead of 1.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use the LIS tails trick. I keep
tails[k], the smallest last value of any increasing run of length k + 1 seen so far. For each number I binary-search the first tail that is at least it. If there is none, the number extends the longest run and I append it; otherwise I replace that tail with it. A smaller tail can only help, because it leaves more room for the numbers that come later, and replacing keepstailssorted, so its length is always the longest length so far. Searching for the first tail that is at least the number, not greater than it, keeps the runs strictly increasing. The trap is readingtailsas the answer: it has the right length but is usually not a real subsequence, so I store predecessors if I must rebuild it. N binary searches giveO(N log N)time andO(N)space."
Complexity & Mathematical Proof
O(N log N)
Look at the execution steps: Maintains tails array where tails[i] is the smallest tail of all increasing subsequences of length i+1. Binary search finds insertion position in tails in O(log N) per element. Total N * log N.
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. tails array of length at most N.
T(N) = N · O(log N) = O(N log N)
Derivation Progression
tails[i] < tails[i+1]
tails array is strictly sorted, enabling binary search.
O(log(len(tails))) per element
Replaces earliest tail >= x or extends tails if x is strictly larger.
N × O(log N) = O(N log N)
Optimal time for LIS length.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(N) tails array
O(1) LIS length integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest strictly increasing subsequence". While coordinate DP tabulates , an experienced engineer utilizes Patience Sorting with Binary Search to solve this in !
. runs in ms.
Streams: each value costs one binary search, and tails never grows longer than the answer itself, so the loop runs on a stream of values that never fits in memory, as long as only the length is needed.
Longest Increasing Subsequence (LeetCode 300)
You're given an integer array nums. Deleting any subset of its elements (possibly none) while keeping the rest in their original order produces a subsequence.
Find the length of the longest subsequence you can produce this way whose values keep strictly increasing from left to right.
Worked Examples
nums = [10,9,2,5,3,7,101,18]4nums = [0,1,0,3,2,3]40, 1, 2, 3 is strictly increasing and has length 4.nums = [7,7,7,7,7,7,7]1⚖️Formal Constraints & Bounds
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Core Insight
For every length, keep only the smallest value an increasing subsequence of that length can end with; each new number replaces the first such tail that is not smaller than it, or extends the list, so the list length is the answer.
Real-World Scenario & Production Applications
Version control DAG(Directed Acyclic Graph) sequence alignment, tournament streak tracking.
Subproblems & Recurrence Decomposition3 Phases
tails[k] is the smallest value that can end an increasing subsequence of length k + 1 among the numbers read so far. It starts empty, and it stays sorted.
tails = []Step-by-Step Execution Trace Table
| x | bisect_left(tails, x) | Action | tails after |
|---|---|---|---|
| 10 | 0 | append | [10] |
| 9 | 0 | replace 10 | [9] |
| 2 | 0 | replace 9 | [2] |
| 5 | 1 | append | [2, 5] |
| 3 | 1 | replace 5 | [2, 3] |
| 7 | 2 | append | [2, 3, 7] |
| 101 | 3 | append | [2, 3, 7, 101] |
| 18 | 3 | replace 101 | [2, 3, 7, 18] → 4 |
| 1 | tails = [] |
| 2 | for x in nums: |
| 3 | idx = bisect_left(tails, x) |
| 4 | idx == len(tails) ? tails.append(x) : tails[idx] = x |
| 5 | return len(tails) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the length of the longest strictly increasing subsequence can be solved in $O(N^2)$ via quadratic DP or in $O(N \log N)$ via Patience Sorting. We maintain an array `tails` where `tails[i]` stores the smallest tail element among all valid subsequences of length $i + 1$. For each number $x$, binary search (`bisect_left`) finds the first tail $\ge x$ and replaces it. If $x$ is larger than all tails, it appends to `tails`, increasing the maximum subsequence length. 🃏 The Analogy: Dealing Cards onto Piles
Deal the numbers left to right as cards. Each card goes on the leftmost pile whose top card is at least as big as it; if no pile qualifies, it starts a new pile on the right. The pile tops, read left to right, always climb, and the number of piles is the length of the longest increasing subsequence. tails is exactly the row of pile tops.
🔑 The Key Idea in the Code
The answer is len(tails), not tails itself: after [3, 4, 1] the tops are [1, 4], which is not a subsequence of the input, even though the length 2 is right.
Strictly increasing vs non-decreasing: Using
nums[j] <= nums[i]instead ofnums[j] < nums[i]. The problem specifies strictly increasing; duplicate values cannot extend the subsequence.Assuming the answer is
dp[-1]: The LIS does not necessarily end at the last element of the array; the global maximum can end anywhere. The result must bemax(dp).Defaulting to when is expected: For , DP gets TLE. Use patience sorting with binary search (
bisect_lefton a tails array).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Longest strictly increasing subsequence over arbitrary jump distances.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: tails is sorted, and tails[k] is the smallest last value of any increasing subsequence of length k + 1 seen so far.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Reading
tailsas the answer: it has the right length but is usually not a real subsequence ofnums, so store each element's predecessor index if you must rebuild the sequence.Using
bisect_rightinstead ofbisect_left: an equal value would then be appended and counted as increasing, so[7, 7, 7, 7, 7]would return 5 instead of 1.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use the LIS tails trick. I keep
tails[k], the smallest last value of any increasing run of length k + 1 seen so far. For each number I binary-search the first tail that is at least it. If there is none, the number extends the longest run and I append it; otherwise I replace that tail with it. A smaller tail can only help, because it leaves more room for the numbers that come later, and replacing keepstailssorted, so its length is always the longest length so far. Searching for the first tail that is at least the number, not greater than it, keeps the runs strictly increasing. The trap is readingtailsas the answer: it has the right length but is usually not a real subsequence, so I store predecessors if I must rebuild it. N binary searches giveO(N log N)time andO(N)space."
Complexity & Mathematical Proof
O(N log N)
Look at the execution steps: Maintains tails array where tails[i] is the smallest tail of all increasing subsequences of length i+1. Binary search finds insertion position in tails in O(log N) per element. Total N * log N.
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. tails array of length at most N.
T(N) = N · O(log N) = O(N log N)
Derivation Progression
tails[i] < tails[i+1]
tails array is strictly sorted, enabling binary search.
O(log(len(tails))) per element
Replaces earliest tail >= x or extends tails if x is strictly larger.
N × O(log N) = O(N log N)
Optimal time for LIS length.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(N) tails array
O(1) LIS length integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "longest strictly increasing subsequence". While coordinate DP tabulates , an experienced engineer utilizes Patience Sorting with Binary Search to solve this in !
. runs in ms.
Streams: each value costs one binary search, and tails never grows longer than the answer itself, so the loop runs on a stream of values that never fits in memory, as long as only the length is needed.