Appearance
Longest Increasing Subsequence
Introduction and Purpose
The Longest Increasing Subsequence (LIS) is a classic problem that asks: given a list of numbers in any order, what is the longest sequence you can form by picking numbers — not necessarily consecutive — that are strictly increasing?
For example, in [10, 9, 2, 5, 3, 7, 101, 18], one valid increasing subsequence is [2, 5, 7, 101] — length 4. Another is [2, 3, 7, 18], also length 4. Both are optimal answers.
Understanding LIS opens the door to a broad family of optimization problems that appear frequently in software engineering interviews and in real systems.
Problems Addressed
Think of LIS as a "growth streak detector." You're not looking for the longest run of consecutive growth — that's a simpler problem. You're finding the optimal selection of elements that always go up, even when scattered.
Real-world scenarios this maps to:
- Stock prices: Find the longest period of strictly increasing closing prices in a historical dataset, even picking non-consecutive days.
- Task scheduling: Given a list of jobs with numeric priorities, find the longest chain of jobs that escalate in priority.
- Data versioning: Some diff algorithms use LIS to identify the longest stable portion between two versions of a file.
- Card game strategy (Patience sorting): The number of piles in the Patience card game equals the LIS length of the deck — this connection leads to the most efficient algorithm.
Subsequence vs. Substring
A key distinction: a subsequence is not the same as a substring.
- A substring must be contiguous: from
[3, 1, 4, 1, 5], the substring at index 2 is[4, 1, 5]. - A subsequence can skip elements:
[3, 4, 5]is valid from[3, 1, 4, 1, 5], even though the 1s are skipped.
Common Approaches
Approach 1: Dynamic Programming — O(n²)
This is the most intuitive approach. For each position i, ask: "What is the longest increasing subsequence that ends at this element?"
The core insight: the LIS ending at i equals 1 (just nums[i] itself) plus the longest LIS ending at any previous position j where nums[j] < nums[i].
Tracing through [10, 9, 2, 5, 3, 7, 101, 18]:
| Index | Value | dp[i] | Reasoning |
|---|---|---|---|
| 0 | 10 | 1 | No previous elements |
| 1 | 9 | 1 | 10 > 9, nothing extends it |
| 2 | 2 | 1 | 10 > 2, 9 > 2 |
| 3 | 5 | 2 | 2 < 5 → dp[2]+1=2 |
| 4 | 3 | 2 | 2 < 3 → dp[2]+1=2 |
| 5 | 7 | 3 | 5 < 7 → dp[3]+1=3 |
| 6 | 101 | 4 | 7 < 101 → dp[5]+1=4 |
| 7 | 18 | 4 | 7 < 18 → dp[5]+1=4 |
Answer: 4 (e.g., [2, 5, 7, 101]).
javascript
function lisDP(nums) {
const n = nums.length;
if (n === 0) return 0;
const dp = new Array(n).fill(1); // Each element alone is length 1
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}
console.log(lisDP([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lisDP([0, 1, 0, 3, 2, 3])); // 4
console.log(lisDP([7, 7, 7, 7])); // 1 (strictly increasing, so all equal = length 1)Time complexity: O(n²) — two nested loops.
Space complexity: O(n) — the dp array.
Approach 2: Binary Search — O(n log n)
This approach is inspired by Patience sorting, a card game. The trick is to maintain a list called tails where tails[i] holds the smallest possible ending value of any increasing subsequence of length i+1 found so far.
The card game analogy: you deal cards face-up into piles, placing each card on the leftmost pile whose top card is ≥ your card, or starting a new pile if none qualifies. The number of piles equals the LIS length.
Tracing [10, 9, 2, 5, 3, 7, 101, 18]:
| Number | tails after | What happened |
|---|---|---|
| 10 | [10] | First element |
| 9 | [9] | Replaces 10 (smaller tail for length 1) |
| 2 | [2] | Replaces 9 |
| 5 | [2, 5] | Extends — LIS length grows to 2 |
| 3 | [2, 3] | Replaces 5 (better tail for length 2) |
| 7 | [2, 3, 7] | Extends — LIS length grows to 3 |
| 101 | [2, 3, 7, 101] | Extends — LIS length grows to 4 |
| 18 | [2, 3, 7, 18] | Replaces 101 (better tail for length 4) |
Final answer: tails.length = 4.
javascript
function lisBinarySearch(nums) {
const tails = [];
for (const num of nums) {
let lo = 0, hi = tails.length;
// Find the first index in tails where tails[mid] >= num
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (tails[mid] < num) {
lo = mid + 1;
} else {
hi = mid;
}
}
tails[lo] = num; // Replace an existing tail or append a new one
}
return tails.length;
}
console.log(lisBinarySearch([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lisBinarySearch([1, 3, 6, 7, 9, 4, 10, 5, 6])); // 6Time complexity: O(n log n) — one loop with a binary search inside.
Space complexity: O(n) — the tails array.
Approach 3: Reconstructing the actual subsequence
The above functions return only the length. To recover the actual sequence, track which element each step extended from.
javascript
function lisWithPath(nums) {
const n = nums.length;
const dp = new Array(n).fill(1);
const parent = new Array(n).fill(-1);
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j; // Remember where we came from
}
}
}
let maxLen = 0, endIdx = 0;
for (let i = 0; i < n; i++) {
if (dp[i] > maxLen) {
maxLen = dp[i];
endIdx = i;
}
}
// Walk parent pointers backwards to reconstruct the path
const lis = [];
let idx = endIdx;
while (idx !== -1) {
lis.unshift(nums[idx]);
idx = parent[idx];
}
return { length: maxLen, sequence: lis };
}
const result = lisWithPath([10, 9, 2, 5, 3, 7, 101, 18]);
console.log(result); // { length: 4, sequence: [2, 5, 7, 101] }Real-world example: finding stock growth streaks
javascript
function longestGrowthStreak(prices) {
const { length, sequence } = lisWithPath(prices);
console.log(`Longest growth streak: ${length} days`);
console.log(`Prices: ${sequence.join(' → ')}`);
return sequence;
}
const closingPrices = [150, 148, 152, 149, 155, 160, 158, 162, 170, 165];
longestGrowthStreak(closingPrices);
// Longest growth streak: 6 days
// Prices: 148 → 149 → 155 → 160 → 162 → 170Complexity Comparison
In practice: for most interview problems and moderate inputs, the O(n²) DP solution is fine and easier to explain. Use the O(n log n) binary search approach when the input is large or when an interviewer asks you to optimize.
Related Algorithms and Data Structures
LIS sits within the broader family of dynamic programming problems. Understanding it makes the following much more approachable:
- Longest Common Subsequence (LCS): Given two sequences, find their longest common subsequence. Uses the same "compare and extend" DP pattern but with a 2D table instead of 1D.
- Edit Distance (Levenshtein): Count the minimum insertions, deletions, or replacements to convert one string into another. Foundational for spell checkers and
git diff. - Russian Doll Envelopes (LeetCode 354): Sort envelopes by width, then find the LIS of their heights. A clean two-dimensional extension of LIS.
- Patience Sorting: The card-game algorithm from which the O(n log n) LIS solution is derived. Worth a quick read — it makes the
tailsarray intuitive. Search for "Patience sorting algorithm" for good visual explanations.
For a structured study path across DP problems, NeetCode and Blind 75 are widely recommended resources.
Tests and Challenges
Practice is essential for LIS to stick. These problems cover the concept progressively:
| Difficulty | Problem | Platform | What it tests |
|---|---|---|---|
| Medium | Longest Increasing Subsequence | LeetCode #300 | Core LIS |
| Medium | Longest Increasing Subsequent | HackerRank | Classic formulation |
| Medium | Number of Longest Increasing Subsequences | LeetCode #673 | Count all LIS, not just the length |
| Hard | Russian Doll Envelopes | LeetCode #354 | LIS in 2D |
| Hard | Maximum Height by Stacking Cuboids | LeetCode #1691 | LIS on 3D sorted data |
Start with LeetCode #300. It's the canonical problem and appears in interview rounds at many top companies. Implement both the O(n²) and O(n log n) solutions and be ready to explain the tradeoff.
Related Concepts
- Big O Notation — Understanding O(n²) vs O(n log n) is key to knowing when the binary search optimization matters in practice.
- Dynamic Programming — LIS is a textbook DP problem; the concepts of optimal substructure and overlapping subproblems explained there are exactly what drives the O(n²) solution.
- Binary Search — The O(n log n) LIS solution (Approach 2) is built entirely on the left-boundary binary search variant; the two articles are best read together.