Longest Increasing Subsequence in DSA Typescript - Deep Dive

Overview - Longest Increasing Subsequence

What is it?

The Longest Increasing Subsequence (LIS) is a sequence of numbers from a list where each number is bigger than the one before it, and the sequence is as long as possible. It does not have to be made of numbers next to each other in the original list, but the order must stay the same. For example, in the list [3, 10, 2, 1, 20], the LIS is [3, 10, 20]. It helps us find patterns and trends in data.

Why it matters

Without the LIS concept, we would struggle to find the longest pattern of growth or improvement in data, like stock prices or student scores. This would make it harder to analyze trends or optimize decisions. LIS helps in many fields like computer science, biology, and finance to understand sequences and improve algorithms.

Where it fits

Before learning LIS, you should understand arrays and basic loops. After LIS, you can learn more complex sequence problems like Longest Common Subsequence or Dynamic Programming techniques for optimization.

Mental Model

Core Idea

The Longest Increasing Subsequence is the longest chain of numbers in order where each number is bigger than the one before, skipping some if needed.

Think of it like...

Imagine climbing a staircase where you can skip some steps but must always go up. The longest path you can climb without stepping down is like the LIS.

Input: [3, 10, 2, 1, 20]

Possible subsequences:
 3 -> 10 -> 20 (length 3)
 3 -> 10 (length 2)
 2 -> 20 (length 2)
 1 -> 20 (length 2)

Longest Increasing Subsequence: 3 -> 10 -> 20

Build-Up - 7 Steps

1

Foundation

Understanding Subsequences

Concept: Learn what a subsequence is and how it differs from a substring or subarray.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, from [3, 10, 2, 1, 20], [3, 2, 20] is a subsequence but not a substring because the elements are not contiguous.

Result

You can identify subsequences by skipping elements but keeping order.

Understanding subsequences is key because LIS is about finding the longest increasing subsequence, not necessarily contiguous.

2

Foundation

What Makes a Sequence Increasing?

Concept: Define what it means for a sequence to be strictly increasing.

A sequence is strictly increasing if every next number is greater than the previous one. For example, [3, 10, 20] is strictly increasing because 3 < 10 < 20. But [3, 10, 10] is not strictly increasing because 10 is not greater than 10.

Result

You can check if a sequence is increasing by comparing each pair of neighbors.

Knowing the strictness of increase helps avoid confusion with equal or decreasing numbers.

3

Intermediate

Brute Force Approach to LIS

🤔Before reading on: do you think checking all subsequences is efficient or inefficient? Commit to your answer.

Concept: Try all subsequences to find the longest increasing one.

The brute force method generates all possible subsequences and checks which are strictly increasing, then picks the longest. This is done by recursion or bitmasking. However, the number of subsequences grows exponentially with input size.

Result

Brute force works but is very slow for large inputs.

Understanding brute force shows why we need better methods and the problem's complexity.

4

Intermediate

Dynamic Programming Solution

🤔Before reading on: do you think storing results of smaller problems helps solve LIS faster? Commit to your answer.

Concept: Use dynamic programming to build solutions from smaller subproblems.

We create an array dp where dp[i] stores the length of the LIS ending at index i. For each element, we look back at all previous elements smaller than it and update dp[i] = max(dp[i], dp[j] + 1). The answer is the max value in dp after processing all elements.

Result

This method runs in O(n^2) time and finds the LIS length efficiently.

Dynamic programming reduces repeated work by remembering past results, making LIS practical for medium-sized inputs.

5

Intermediate

Reconstructing the LIS Sequence

🤔Before reading on: do you think knowing the length of LIS is enough to find the actual sequence? Commit to your answer.

Concept: Track the actual LIS elements, not just its length.

Along with dp, keep a parent array to remember the previous index for each dp[i]. After filling dp, find the index with max dp[i], then follow parents backward to reconstruct the LIS sequence in reverse order.

Result

You get the actual longest increasing subsequence, not just its length.

Knowing how to reconstruct the sequence is crucial for applications needing the actual pattern, not just its size.

6

Advanced

Optimized O(n log n) LIS Algorithm

🤔Before reading on: do you think we can do better than O(n^2) for LIS? Commit to your answer.

Concept: Use a clever method with binary search to improve performance.

Maintain an array tails where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. For each number, use binary search on tails to find where it fits or replaces an element. The length of tails is the LIS length.

Result

This algorithm runs in O(n log n) time, much faster for large inputs.

Using binary search with tails array cleverly tracks potential LIS ends, drastically improving efficiency.

7

Expert

Handling Equal Elements and Variations

🤔Before reading on: do you think LIS always requires strictly increasing sequences? Commit to your answer.

Concept: Explore variations like non-decreasing subsequences and how to adapt algorithms.

Sometimes, problems ask for longest non-decreasing subsequence where equal elements are allowed. The binary search condition changes from strictly greater to greater or equal. Also, LIS can be extended to multidimensional data or combined with other constraints.

Result

You can adapt LIS algorithms to different problem variants and constraints.

Knowing variations and how to adjust algorithms prepares you for real-world and contest challenges.

Under the Hood

The LIS dynamic programming approach builds solutions by storing the length of the longest increasing subsequence ending at each position. The optimized method uses a tails array to keep track of the smallest possible last element for subsequences of different lengths. Binary search quickly finds where to place each new element in tails, ensuring the array remains sorted and minimal. This process simulates building multiple candidate subsequences efficiently.

Why designed this way?

Early LIS solutions were brute force and slow. Dynamic programming improved speed but was still quadratic. The tails and binary search method was designed to reduce time complexity by avoiding checking all previous elements explicitly. This design balances simplicity and performance, making LIS practical for large datasets.

Input array: [3, 10, 2, 1, 20]

DP approach:
Index: 0  1   2  3  4
Value:3 10   2  1 20
DP:   1  2   1  1  3

Tails array during optimized method:
Step 1: tails = [3]
Step 2: tails = [3, 10]
Step 3: tails = [2, 10]
Step 4: tails = [1, 10]
Step 5: tails = [1, 10, 20]

Length of tails = 3 (LIS length)

Myth Busters - 4 Common Misconceptions

Quick: Does the LIS have to be made of consecutive elements? Commit to yes or no.

Common Belief: LIS must be a continuous part of the array.

Reality: LIS is a subsequence, so elements can be skipped as long as order is preserved.

Why it matters: Believing LIS is continuous limits solutions and causes wrong answers in problems.

Quick: Is the LIS always unique? Commit to yes or no.

Common Belief: There is only one longest increasing subsequence for any array.

Reality: Multiple different LIS sequences can exist with the same maximum length.

Why it matters: Assuming uniqueness can cause errors when reconstructing or counting LIS.

Quick: Can LIS include equal numbers if the problem says 'increasing'? Commit to yes or no.

Common Belief: Equal numbers can be part of LIS if they appear in order.

Reality: Strictly increasing means each next number must be greater, not equal.

Why it matters: Misunderstanding strictness leads to incorrect LIS length and sequences.

Quick: Does the O(n log n) LIS algorithm find the actual sequence easily? Commit to yes or no.

Common Belief: The optimized LIS algorithm directly gives the LIS sequence.

Reality: It only gives the length; reconstructing the sequence requires extra tracking.

Why it matters: Expecting the sequence directly can cause confusion and incomplete solutions.

Expert Zone

1

The tails array in the O(n log n) method does not represent an actual subsequence but helps track potential ends, which is subtle and often misunderstood.

2

Reconstructing the LIS from the optimized method requires additional arrays to track predecessors, which is not obvious from the basic algorithm.

3

In some cases, LIS algorithms can be adapted to multidimensional sequences by defining custom comparison rules, a non-trivial extension.

When NOT to use

LIS algorithms are not suitable when the problem requires contiguous increasing sequences (use Longest Increasing Substring instead) or when sequences have complex constraints like weights or multiple dimensions without adaptation.

Production Patterns

LIS is used in version control systems to find minimal changes, in bioinformatics to analyze DNA sequences, and in finance to detect longest growth trends. Professionals often combine LIS with other algorithms like binary indexed trees or segment trees for enhanced performance.

Connections

Longest Common Subsequence

Both find longest subsequences but with different matching criteria.

Understanding LIS helps grasp LCS since both use dynamic programming and subsequence concepts.

Binary Search

The optimized LIS algorithm uses binary search to improve efficiency.

Mastering binary search is essential to implement the O(n log n) LIS solution.

Evolutionary Biology

LIS concepts relate to finding longest chains of traits or mutations increasing over time.

Recognizing LIS patterns helps analyze evolutionary sequences and understand biological progressions.

Common Pitfalls

#1 Trying to find LIS by checking only contiguous elements.

Wrong approach:

function lisContiguous(arr: number[]): number {
let maxLen = 1, currLen = 1;
for (let i = 1; i < arr.length; i++) {
if (arr[i] > arr[i - 1]) currLen++;
else currLen = 1;
if (currLen > maxLen) maxLen = currLen;
}
return maxLen;
}

Correct approach:

function lisDP(arr: number[]): number {
const dp = Array(arr.length).fill(1);
for (let i = 1; i < arr.length; i++) {
for (let j = 0; j < i; j++) {
if (arr[i] > arr[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
return Math.max(...dp);
}

Root cause:

Confusing subsequence with substring leads to wrong assumptions about continuity.

#2 Assuming equal elements can be part of LIS when problem requires strictly increasing.

Wrong approach:

if (arr[i] >= arr[j]) dp[i] = Math.max(dp[i], dp[j] + 1);

Correct approach:

if (arr[i] > arr[j]) dp[i] = Math.max(dp[i], dp[j] + 1);

Root cause:

Misunderstanding strict inequality condition in LIS definition.

#3 Using the O(n log n) tails array as the actual LIS sequence.

Wrong approach:

function lisLength(arr: number[]): number {
const tails: number[] = [];
for (const num of arr) {
let left = 0, right = tails.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < num) left = mid + 1;
else right = mid;
}
tails[left] = num;
}
return tails.length;
}
// Trying to return tails as LIS sequence directly

Correct approach:

Use additional arrays to track predecessors and reconstruct LIS after computing length with tails.

Root cause:

Misinterpreting tails array as the actual subsequence rather than a helper structure.

Key Takeaways

The Longest Increasing Subsequence finds the longest ordered chain of increasing numbers, not necessarily contiguous.

Dynamic programming solves LIS efficiently by building on smaller subproblems and remembering results.

The optimized O(n log n) method uses binary search and a tails array to speed up LIS length calculation.

Reconstructing the actual LIS sequence requires extra tracking beyond just computing its length.

Understanding LIS variations and pitfalls prepares you for real-world problems and advanced algorithm challenges.