Longest Increasing Subsequence in DSA Javascript

Mental Model

Find the longest sequence of numbers that keeps going up without skipping order. We want the biggest chain where each number is bigger than the one before.

Analogy: Imagine climbing stairs where each step is higher than the last. You want to find the longest path going up without stepping down or sideways.

Array: [10] -> [22] -> [9] -> [33] -> [21] -> [50] -> [41] -> [60]
LIS lengths:  1      2      1      3      2      4      4      5

Dry Run Walkthrough

Input: array: [10, 22, 9, 33, 21, 50, 41, 60]

Goal: Find the length of the longest increasing subsequence in the array

Step 1: Start with first element 10, LIS length is 1

LIS lengths: [1] -> [] -> [] -> [] -> [] -> [] -> [] -> []

Why: Every single number alone is an increasing subsequence of length 1

Step 2: Check 22: it is bigger than 10, so LIS length at 22 is 1 + LIS at 10 = 2

LIS lengths: [1] -> [2] -> [] -> [] -> [] -> [] -> [] -> []

Why: 22 can extend the subsequence ending at 10

Step 3: Check 9: smaller than 10 and 22, so LIS length is 1

LIS lengths: [1] -> [2] -> [1] -> [] -> [] -> [] -> [] -> []

Why: 9 cannot extend any previous increasing subsequence

Step 4: Check 33: bigger than 10, 22, and 9; max LIS before is 2 (at 22), so LIS at 33 is 3

LIS lengths: [1] -> [2] -> [1] -> [3] -> [] -> [] -> [] -> []

Why: 33 extends the longest subsequence ending at 22

Step 5: Check 21: bigger than 10 and 9 but smaller than 22 and 33; max LIS before is 1 (at 10 or 9), so LIS at 21 is 2

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [] -> [] -> []

Why: 21 extends subsequence ending at 10 or 9 but not 22 or 33

Step 6: Check 50: bigger than all before; max LIS before is 3 (at 33), so LIS at 50 is 4

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [4] -> [] -> []

Why: 50 extends the longest subsequence ending at 33

Step 7: Check 41: bigger than 10, 22, 9, 33, 21 but smaller than 50; max LIS before is 3 (at 33), so LIS at 41 is 4

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [4] -> [4] -> []

Why: 41 extends the longest subsequence ending at 33

Step 8: Check 60: bigger than all before; max LIS before is 4 (at 50 or 41), so LIS at 60 is 5

LIS lengths: [1] -> [2] -> [1] -> [3] -> [2] -> [4] -> [4] -> [5]

Why: 60 extends the longest subsequence ending at 50 or 41

Result:

Longest Increasing Subsequence length is 5

Annotated Code

DSA Javascript

class LIS {
  static lengthOfLIS(nums) {
    if (nums.length === 0) return 0;
    const dp = new Array(nums.length).fill(1);
    for (let i = 1; i < nums.length; i++) {
      for (let j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
    }
    return Math.max(...dp);
  }
}

// Driver code
const arr = [10, 22, 9, 33, 21, 50, 41, 60];
console.log(LIS.lengthOfLIS(arr));

const dp = new Array(nums.length).fill(1);

Initialize dp array where each element starts with LIS length 1

for (let i = 1; i < nums.length; i++) {

Traverse each element to find LIS ending at i

for (let j = 0; j < i; j++) {

Check all previous elements before i

if (nums[i] > nums[j]) {

If current number is bigger, it can extend LIS ending at j

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

Update dp[i] with the longest subsequence length found so far

return Math.max(...dp);

Return the maximum LIS length found in dp array

Output

5

Complexity Analysis

Time: O(n^2) because for each element we check all previous elements to find the longest subsequence

Space: O(n) because we use an array dp of the same size as input to store LIS lengths

vs Alternative: A naive approach tries all subsequences with exponential time; this dynamic programming approach is much faster but still quadratic

Edge Cases

empty array

returns 0 because there are no elements to form a subsequence

DSA Javascript

if (nums.length === 0) return 0;

array with all equal elements

returns 1 because the longest increasing subsequence can only be one element

DSA Javascript

dp initialized with 1 for all elements, no updates since no element is greater than previous

strictly decreasing array

returns 1 because no element can extend previous, so LIS length is 1 for any single element

DSA Javascript

dp remains all 1s as no nums[i] > nums[j] condition is true

When to Use This Pattern

When you need to find the longest ordered sequence inside an array where order matters but elements don't have to be next to each other, use the Longest Increasing Subsequence pattern.

Common Mistakes

Mistake: Updating dp[i] without checking if nums[i] > nums[j], causing incorrect subsequence lengths
Fix: Add condition to update dp[i] only if nums[i] > nums[j]

Mistake: Returning dp[nums.length - 1] instead of the maximum value in dp array
Fix: Return Math.max(...dp) to get the longest subsequence anywhere in the array

Summary

Finds the length of the longest increasing subsequence in an array.

Use when you want the longest chain of increasing numbers that may not be next to each other.

The key is to build up solutions for smaller parts and use them to solve bigger parts.

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