Pattern Guide
Sequences — LIS, LCS & More
"LIS in O(n log n). LCS from DP. Every sequence has a structure."
Sequence problems — Longest Increasing Subsequence, Longest Common Subsequence, and arithmetic/geometric sequences — appear constantly. Master the 3 LIS approaches and the 2D LCS table.
18 min readsequences problems →
Problems you can solve with this pattern
8 problems · click any to start solving
LIS — O(n²) DP
// dp[i] = LIS ending at index i
// For each i, look at all j < i where nums[j] < nums[i]
function lis_n2(nums) {
const n = nums.length;
const dp = 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[i] = Math.max(dp[i], dp[j] + 1);
return Math.max(...dp);
}Sequence problems ask you to find a longest/shortest/optimal subsequence (elements in order but not necessarily contiguous). The two giants are LIS (Longest Increasing Subsequence) and LCS (Longest Common Subsequence). Both have three levels of solutions — brute force, DP, and optimized — and understanding each level gives insight into the structure.
LIS — Longest Increasing Subsequence
LIS — O(n²) DP
// dp[i] = LIS ending at index i
// For each i, look at all j < i where nums[j] < nums[i]
function lis_n2(nums) {
const n = nums.length;
const dp = 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[i] = Math.max(dp[i], dp[j] + 1);
return Math.max(...dp);
}LIS — O(n log n) patience sorting / binary search
// Maintain 'tails': tails[i] = smallest tail element of all increasing subsequences of length i+1
// Binary search for position where nums[i] should go:
// - If nums[i] > tails[-1]: extend, push
// - Else: replace first tail >= nums[i] (keeps tails minimal → more room for future)
function lis_nlogn(nums) {
const tails = [];
for (const num of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < num) lo = mid + 1;
else hi = mid;
}
tails[lo] = num; // replace or extend
}
return tails.length; // tails.length = LIS length
}
// Note: tails array does NOT contain the actual LIS — it's a auxiliary structure
// To reconstruct: track predecessors during the binary searchWhy patience sorting works: We're maintaining the minimum possible "tail" for each subsequence length. By replacing the first tail ≥ num (not > num), we keep tails strictly increasing. A smaller tail gives more future elements a chance to extend. The length of tails = LIS length, even though tails itself isn't the LIS.
LCS — Longest Common Subsequence
LCS — O(m×n) DP
// dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]
// Base case: dp[0][j] = dp[i][0] = 0 (empty string has LCS 0)
// If chars match: dp[i][j] = dp[i-1][j-1] + 1
// Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
function lcs(text1, text2) {
const m = text1.length, n = text2.length;
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = text1[i-1] === text2[j-1]
? dp[i-1][j-1] + 1
: Math.max(dp[i-1][j], dp[i][j-1]);
return dp[m][n];
}Subsequence vs Subarray — the key difference:
- Subsequence: characters can be non-contiguous → LCS dp[i][j] = max of skip or (match: dp[i-1][j-1]+1)
- Subarray (contiguous): reset to 0 on mismatch → longest common subarray
- Palindrome subsequence: dp[i][j] = whether s[i..j] is palindrome, expand from center
- Edit distance: both can skip (insert/delete) AND match/replace
- Count distinct subsequences: dp[i][j] = skip + (if match: use)
- Subsequence: characters can be non-contiguous → LCS dp[i][j] = max of skip or (match: dp[i-1][j-1]+1)
- Subarray (contiguous): reset to 0 on mismatch → longest common subarray
- Palindrome subsequence: dp[i][j] = whether s[i..j] is palindrome, expand from center
- Edit distance: both can skip (insert/delete) AND match/replace
- Count distinct subsequences: dp[i][j] = skip + (if match: use)