Longest Increasing Subsequence in DSA Javascript - Deep Dive

Overview - Longest Increasing Subsequence

What is it?

The Longest Increasing Subsequence (LIS) is a sequence of numbers from a given 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 consecutive numbers from the list, but the order must stay the same. For example, in the list [3, 10, 2, 1, 20], the LIS is [3, 10, 20]. This concept helps us find patterns and order in data.

Why it matters

Without the ability to find the longest increasing subsequence, many problems involving order and growth would be harder to solve. For example, in stock prices, finding the longest period of increasing prices helps investors. In computer science, it helps optimize tasks like scheduling and data analysis. Without LIS, we would miss important trends and efficient solutions.

Where it fits

Before learning LIS, you should understand arrays and basic loops. After LIS, you can explore dynamic programming deeply and learn related problems like Longest Common Subsequence or Patience Sorting. LIS is a key step in mastering sequence analysis.

Mental Model

Core Idea

The Longest Increasing Subsequence is the longest chain you can build by picking numbers in order, each bigger than the last.

Think of it like...

Imagine climbing a staircase where each step is higher than the previous one, but you can skip some steps. The longest path you can climb without going down is like the LIS.

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

Possible subsequences:
 3 -> 10 -> 20
 3 -> 10
 2 -> 20
 1 -> 20

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 [1, 2, 3, 4], subsequences include [1, 3, 4], [2, 4], and [1, 2, 3, 4]. Unlike substrings or subarrays, subsequences do not require elements to be consecutive.

Result

You can identify subsequences by skipping elements but keeping the order intact.

Understanding subsequences is crucial because LIS is about finding the longest increasing subsequence, not necessarily consecutive elements.

2

Foundation

Defining Increasing Sequences

Concept: Learn what makes a sequence increasing and how to check it.

An increasing sequence is one where each number is strictly greater than the previous one. For example, [2, 5, 7] is increasing, but [2, 5, 5] is not because 5 is not greater than 5. To check if a sequence is increasing, compare each element with the one before it.

Result

You can verify if a sequence is increasing by comparing neighbors.

Knowing how to check increasing sequences helps in validating candidate subsequences for LIS.

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: Explore the simplest method: checking every subsequence to find the longest increasing one.

The brute force way is to generate all subsequences of the array and check which ones are increasing. Then pick the longest. For an array of length n, there are 2^n subsequences, so this method is very slow and impractical for large inputs.

Result

Brute force works but is too slow for big arrays.

Understanding brute force shows why we need smarter methods like dynamic programming.

4

Intermediate

Dynamic Programming for LIS

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

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

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] = Math.max(dp[i], dp[j] + 1). Finally, the answer is the maximum value in dp. This reduces time complexity to O(n^2).

Result

Dynamic programming finds LIS length efficiently for moderate input sizes.

Knowing how to break down LIS into subproblems and reuse results is key to efficient algorithms.

5

Intermediate

Reconstructing the LIS Sequence

🤔Before reading on: do you think dp alone gives the sequence or just its length? Commit to your answer.

Concept: Learn how to retrieve the actual LIS, not just its length, using extra tracking.

Along with dp, keep a parent array to remember the index of the previous element in the LIS. After filling dp, find the index of the maximum dp value and follow parents backward to reconstruct the LIS sequence in reverse order.

Result

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

Tracking parents helps convert length information into the actual sequence, which is often needed.

6

Advanced

Optimized O(n log n) LIS Algorithm

🤔Before reading on: do you think binary search can help speed up LIS? Commit to yes or no.

Concept: Use a clever method with binary search to improve LIS time complexity to O(n log n).

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 to find where it fits in tails and update tails accordingly. The length of tails is the LIS length. This method does not directly give the sequence but is very fast.

Result

LIS length is found in O(n log n) time, suitable for large inputs.

Combining binary search with dynamic programming ideas leads to a powerful optimization.

7

Expert

Recovering LIS from Optimized Method

🤔Before reading on: do you think the O(n log n) method can reconstruct the LIS sequence easily? Commit to yes or no.

Concept: Learn how to reconstruct the LIS sequence from the optimized tails array using extra bookkeeping.

To reconstruct the sequence, keep track of indices and predecessors while updating tails. Store the index of the element that tails[k] represents and the predecessor index for each element. After processing, backtrack from the last index to build the LIS. This adds complexity but recovers the sequence efficiently.

Result

You can get the actual LIS sequence in O(n log n) time with extra memory.

Understanding this reconstruction reveals the full power of the optimized LIS algorithm beyond just length calculation.

Under the Hood

The LIS problem is solved by exploring subsequences and using memory to avoid repeated work. Dynamic programming stores the best solutions for smaller parts of the array, building up to the full solution. The optimized method uses a tails array to keep track of potential sequence ends, applying binary search to quickly update and maintain these ends. Internally, this reduces redundant comparisons and leverages sorted properties.

Why designed this way?

Early solutions were brute force and slow. Dynamic programming was introduced to reuse results and improve speed. Later, the tails method was designed to optimize further by focusing on sequence ends and using binary search. This design balances time complexity and memory use, making LIS practical for large data.

Input array: [10, 9, 2, 5, 3, 7, 101, 18]

DP approach:
Index: 0  1  2  3  4  5   6    7
Value:10  9  2  5  3  7  101  18
DP:   1  1  1  2  2  3   4    4

Tails array (optimized):
Step  Value  Tails
0     10     [10]
1     9      [9]
2     2      [2]
3     5      [2,5]
4     3      [2,3]
5     7      [2,3,7]
6     101    [2,3,7,101]
7     18     [2,3,7,18]

Myth Busters - 4 Common Misconceptions

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

Common Belief: The longest increasing subsequence must be made of consecutive elements in the array.

Reality: The LIS can skip elements; it only needs to keep the original order, not consecutiveness.

Why it matters: Believing this limits solutions and leads to incorrect answers, missing longer subsequences.

Quick: Is the LIS always unique? Commit 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 confusion when reconstructing sequences or comparing results.

Quick: Does the O(n log n) method directly give the LIS sequence? Commit yes or no.

Common Belief: The optimized O(n log n) algorithm directly returns the LIS sequence.

Reality: It only returns the length; reconstructing the sequence requires extra steps and memory.

Why it matters: Expecting the sequence immediately can lead to incomplete implementations and bugs.

Quick: Is the LIS problem the same as sorting the array? Commit yes or no.

Common Belief: Finding the LIS is the same as sorting the array in increasing order.

Reality: LIS finds the longest increasing order within the original sequence without rearranging elements.

Why it matters: Confusing LIS with sorting leads to wrong approaches and misunderstanding the problem.

Expert Zone

1

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

2

Reconstructing the LIS from the O(n log n) method requires careful bookkeeping of predecessors and indices, which is non-trivial and easy to get wrong.

3

The LIS problem can be extended to variations like longest non-decreasing subsequence or multidimensional sequences, requiring adaptations of the core algorithms.

When NOT to use

If the input size is very small, brute force or simple dynamic programming may be simpler and sufficient. For sequences where elements can be equal and non-decreasing subsequences are needed, LIS algorithms must be adjusted. For real-time or streaming data, LIS algorithms may not be suitable without modifications.

Production Patterns

LIS is used in bioinformatics to find ordered patterns in DNA sequences, in finance to analyze stock trends, and in version control systems to detect longest common subsequences. Optimized LIS algorithms are integrated into libraries for sequence analysis and competitive programming platforms.

Connections

Longest Common Subsequence

Related problem that finds the longest sequence common to two sequences.

Understanding LIS helps grasp LCS because both involve subsequence concepts and dynamic programming.

Binary Search

Used inside the optimized LIS algorithm to find positions quickly.

Knowing binary search enables understanding how LIS optimization reduces time complexity.

Evolutionary Biology

LIS concepts relate to finding longest increasing traits or gene sequences over time.

Recognizing LIS patterns helps analyze evolutionary progressions and ordered changes in biology.

Common Pitfalls

#1 Trying to find LIS by sorting the array and picking elements.

Wrong approach:

const arr = [3, 10, 2, 1, 20];
const sorted = arr.slice().sort((a,b) => a - b);
console.log(sorted); // Incorrect LIS

Correct approach:

Use dynamic programming or optimized methods to find LIS without sorting the original array.

Root cause:

Confusing LIS with sorting ignores the original order constraint.

#2 Assuming dp array stores the LIS sequence directly.

Wrong approach:

const dp = [1, 2, 3];
console.log(dp); // Trying to print LIS sequence directly

Correct approach:

Use a parent array to reconstruct the LIS sequence from dp values.

Root cause:

Misunderstanding dp as sequence storage rather than length storage.

#3 Using the O(n log n) method without tracking predecessors, expecting the sequence.

Wrong approach:

Implement tails array only and return tails as LIS sequence.

Correct approach:

Add arrays to track indices and predecessors to reconstruct the LIS sequence properly.

Root cause:

Overlooking the need for extra bookkeeping in optimized LIS reconstruction.

Key Takeaways

The Longest Increasing Subsequence finds the longest ordered chain of increasing numbers in a sequence without requiring consecutive elements.

Dynamic programming reduces the problem from exponential to polynomial time by storing solutions to smaller subproblems.

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

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

Understanding LIS is foundational for many sequence analysis problems and has applications beyond computer science.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask you to find in a sequence of numbers?

easy

A. The longest subsequence where numbers are all equal

B. The longest subsequence where each number is smaller than the previous one

C. The longest subsequence with alternating increasing and decreasing numbers

D. The longest subsequence where each number is larger than the previous one

Solution

1. Step 1: Understand the definition of LIS and compare options

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one. The longest subsequence where each number is larger than the previous one matches the definition exactly, others describe different patterns.

2. Final Answer:

   The longest subsequence where each number is larger than the previous one -> Option D

3. Quick Check:

   LIS = strictly increasing subsequence [OK]

Hint: LIS means strictly increasing numbers in order [OK]

Common Mistakes:

• Confusing increasing with decreasing subsequence
• Thinking LIS means contiguous elements only
• Assuming equal numbers are allowed in LIS

2. Which of the following JavaScript code snippets correctly initializes an array to store LIS lengths for each element in the input array arr?

easy

A. const lis = Array(arr.length).fill(0);

B. const lis = new Array(arr.length).fill(null);

C. const lis = new Array(arr.length).fill(1);

D. const lis = new Array(arr.length).fill(undefined);

Solution

1. Step 1: Understand LIS initialization and check syntax

   Each element starts with LIS length 1 because each element alone is a subsequence. const lis = new Array(arr.length).fill(1); correctly creates an array of length arr.length filled with 1s.

2. Final Answer:

   const lis = new Array(arr.length).fill(1); -> Option C

3. Quick Check:

   Initialize LIS array with 1s [OK]

Hint: LIS array starts with 1 for each element [OK]

Common Mistakes:

• Filling with 0 instead of 1
• Using fill(null) or fill(undefined) which are incorrect for LIS
• Not matching array length to input array

3. What is the length of the Longest Increasing Subsequence for the array [10, 22, 9, 33, 21, 50, 41, 60]?

medium

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Identify increasing subsequences and confirm no longer exists

   Possible LIS includes [10, 22, 33, 50, 60] which has length 5. Checking other subsequences shows none longer than 5.

2. Final Answer:

   5 -> Option B

3. Quick Check:

   LIS length for given array = 5 [OK]

Hint: Trace increasing numbers, pick longest chain [OK]

Common Mistakes:

• Counting non-increasing sequences
• Confusing subsequence with subarray
• Missing longer subsequences by skipping elements

4. Consider this JavaScript code snippet to find LIS length:

function lengthOfLIS(arr) {
  const lis = new 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]) {
        lis[i] = Math.max(lis[i], lis[j] + 1);
      }
    }
  }
  return lis[arr.length];
}

What is the error in this code?

medium

A. Returns lis[arr.length] which is undefined, should return max value in lis array

B. Incorrect initialization of lis array with 1s

C. The inner loop should start from i instead of 0

D. The comparison should be arr[i] < arr[j] instead of arr[i] > arr[j]

Solution

1. Step 1: Check return statement and correct return logic

   Returning lis[arr.length] accesses out-of-bounds index (undefined). Should return the maximum value in lis array, e.g., Math.max(...lis).

2. Final Answer:

   Returns lis[arr.length] which is undefined, should return max value in lis array -> Option A

3. Quick Check:

   Return max LIS length, not out-of-bounds element [OK]

Hint: Return max value in lis array, not lis[arr.length] [OK]

Common Mistakes:

• Returning wrong index from lis array
• Misunderstanding loop ranges
• Reversing comparison operators

5. Given the array [3, 10, 2, 1, 20], which of the following code snippets correctly finds the length of the Longest Increasing Subsequence using binary search optimization?

hard

A. function lengthOfLIS(arr) {
const tails = [];
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;
}

B. function lengthOfLIS(arr) {
const tails = [];
for (const num of arr) {
let left = 0, right = tails.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] <= num) left = mid + 1;
else right = mid - 1;
}
tails[left] = num;
}
return tails.length;
}

C. function lengthOfLIS(arr) {
const tails = [];
for (const num of arr) {
let left = 0, right = tails.length;
while (left < right) {
const mid = Math.ceil((left + right) / 2);
if (tails[mid] > num) right = mid - 1;
else left = mid + 1;
}
tails[left] = num;
}
return tails.length;
}

D. function lengthOfLIS(arr) {
const tails = [];
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) right = mid;
else left = mid + 1;
}
tails[left] = num;
}
return tails.length;
}

Solution

1. Step 1: Understand binary search in tails array and check boundaries/conditions

   We find the position to replace or append the current number to keep tails sorted. function lengthOfLIS(arr) { const tails = []; 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; } uses correct boundaries and conditions: left < right, mid floor, tails[mid] < num moves left up.

2. Final Answer:

   function lengthOfLIS(arr) { const tails = []; 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; } -> Option A

3. Quick Check:

   Binary search with left < right and tails[mid] < num [OK]

Hint: Use binary search with left < right and tails[mid] < num [OK]

Common Mistakes:

• Using wrong binary search boundaries (<= instead of <)
• Incorrect mid calculation (ceil instead of floor)
• Wrong comparison operators in binary search