Longest Increasing Subsequence in DSA Javascript - Execution Trace

Concept Flow - Longest Increasing Subsequence

Start with array

↓

Initialize dp array with 1s

↓

For each element i

↓

Check all elements j < i

↓

If arr[j

↓

Repeat for all i

↓

Find max value in dp

↓

Longest Increasing Subsequence length found

We start with the input array, create a dp array to store LIS lengths, update dp by checking previous smaller elements, and finally find the maximum LIS length.

Execution Sample

DSA Javascript

const arr = [10, 9, 2, 5, 3, 7, 101, 18];
const dp = Array(arr.length).fill(1);
for(let i=1; i<arr.length; i++) {
  for(let j=0; j<i; j++) {
    if(arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
  }
}
const result = Math.max(...dp);
console.log(result);

This code calculates the length of the longest increasing subsequence in the array.

Execution Table

Step	Operation	i	j	Condition arr[j]<arr[i]	dp Array State	Action Taken
1	Initialize dp	-	-	-	[1,1,1,1,1,1,1,1]	All dp values set to 1
2	i=1, j=0	1	0	arr[0]=10 < arr[1]=9? No	[1,1,1,1,1,1,1,1]	No update
3	i=2, j=0	2	0	arr[0]=10 < arr[2]=2? No	[1,1,1,1,1,1,1,1]	No update
4	i=2, j=1	2	1	arr[1]=9 < arr[2]=2? No	[1,1,1,1,1,1,1,1]	No update
5	i=3, j=0	3	0	arr[0]=10 < arr[3]=5? No	[1,1,1,1,1,1,1,1]	No update
6	i=3, j=1	3	1	arr[1]=9 < arr[3]=5? No	[1,1,1,1,1,1,1,1]	No update
7	i=3, j=2	3	2	arr[2]=2 < arr[3]=5? Yes	[1,1,1,2,1,1,1,1]	dp[3] = max(1, dp[2]+1)=2
8	i=4, j=0	4	0	arr[0]=10 < arr[4]=3? No	[1,1,1,2,1,1,1,1]	No update
9	i=4, j=1	4	1	arr[1]=9 < arr[4]=3? No	[1,1,1,2,1,1,1,1]	No update
10	i=4, j=2	4	2	arr[2]=2 < arr[4]=3? Yes	[1,1,1,2,2,1,1,1]	dp[4] = max(1, dp[2]+1)=2
11	i=4, j=3	4	3	arr[3]=5 < arr[4]=3? No	[1,1,1,2,2,1,1,1]	No update
12	i=5, j=0	5	0	arr[0]=10 < arr[5]=7? No	[1,1,1,2,2,1,1,1]	No update
13	i=5, j=1	5	1	arr[1]=9 < arr[5]=7? No	[1,1,1,2,2,1,1,1]	No update
14	i=5, j=2	5	2	arr[2]=2 < arr[5]=7? Yes	[1,1,1,2,2,2,1,1]	dp[5] = max(1, dp[2]+1)=2
15	i=5, j=3	5	3	arr[3]=5 < arr[5]=7? Yes	[1,1,1,2,2,3,1,1]	dp[5] = max(2, dp[3]+1)=3
16	i=5, j=4	5	4	arr[4]=3 < arr[5]=7? Yes	[1,1,1,2,2,3,1,1]	dp[5] = max(3, dp[4]+1)=3 (no change)
17	i=6, j=0	6	0	arr[0]=10 < arr[6]=101? Yes	[1,1,1,2,2,3,2,1]	dp[6] = max(1, dp[0]+1)=2
18	i=6, j=1	6	1	arr[1]=9 < arr[6]=101? Yes	[1,1,1,2,2,3,2,1]	dp[6] = max(2, dp[1]+1)=2 (no change)
19	i=6, j=2	6	2	arr[2]=2 < arr[6]=101? Yes	[1,1,1,2,2,3,2,1]	dp[6] = max(2, dp[2]+1)=2 (no change)
20	i=6, j=3	6	3	arr[3]=5 < arr[6]=101? Yes	[1,1,1,2,2,3,3,1]	dp[6] = max(2, dp[3]+1)=3
21	i=6, j=4	6	4	arr[4]=3 < arr[6]=101? Yes	[1,1,1,2,2,3,3,1]	dp[6] = max(3, dp[4]+1)=3 (no change)
22	i=6, j=5	6	5	arr[5]=7 < arr[6]=101? Yes	[1,1,1,2,2,3,4,1]	dp[6] = max(3, dp[5]+1)=4
23	i=7, j=0	7	0	arr[0]=10 < arr[7]=18? Yes	[1,1,1,2,2,3,4,2]	dp[7] = max(1, dp[0]+1)=2
24	i=7, j=1	7	1	arr[1]=9 < arr[7]=18? Yes	[1,1,1,2,2,3,4,2]	dp[7] = max(2, dp[1]+1)=2 (no change)
25	i=7, j=2	7	2	arr[2]=2 < arr[7]=18? Yes	[1,1,1,2,2,3,4,2]	dp[7] = max(2, dp[2]+1)=2 (no change)
26	i=7, j=3	7	3	arr[3]=5 < arr[7]=18? Yes	[1,1,1,2,2,3,4,3]	dp[7] = max(2, dp[3]+1)=3
27	i=7, j=4	7	4	arr[4]=3 < arr[7]=18? Yes	[1,1,1,2,2,3,4,3]	dp[7] = max(3, dp[4]+1)=3 (no change)
28	i=7, j=5	7	5	arr[5]=7 < arr[7]=18? Yes	[1,1,1,2,2,3,4,4]	dp[7] = max(3, dp[5]+1)=4
29	i=7, j=6	7	6	arr[6]=101 < arr[7]=18? No	[1,1,1,2,2,3,4,4]	No update
30	Find max in dp	-	-	-	[1,1,1,2,2,3,4,4]	Max dp value is 4
31	End	-	-	-	[1,1,1,2,2,3,4,4]	Longest Increasing Subsequence length = 4

💡 All elements processed; dp array fully updated; maximum dp value found as LIS length.

Variable Tracker

Variable	Start	After Step 7	After Step 11	After Step 16	After Step 22	After Step 29	Final
dp	[1,1,1,1,1,1,1,1]	[1,1,1,2,1,1,1,1]	[1,1,1,2,2,1,1,1]	[1,1,1,2,2,3,1,1]	[1,1,1,2,2,3,4,1]	[1,1,1,2,2,3,4,4]	[1,1,1,2,2,3,4,4]
i	0	3	4	5	6	7	End
j	-	2	4	5	6	7	-

Key Moments - 3 Insights

Why do we initialize all dp values to 1 at the start?

Each element alone is an increasing subsequence of length 1, so dp starts with all 1s as shown in step 1 of the execution_table.

Why do we only update dp[i] when arr[j] < arr[i]?

Because the subsequence must be strictly increasing, so only previous smaller elements can extend the subsequence. This is checked in the condition column in the execution_table.

How do we know the final answer is the maximum value in dp?

dp[i] stores the length of the longest increasing subsequence ending at i, so the overall LIS length is the maximum dp value, found at step 30.

Visual Quiz - 3 Questions

Look at the execution_table at step 15, what is the dp array state?

A [1,1,1,2,2,3,3,1]

B [1,1,1,2,2,3,4,1]

C [1,1,1,2,2,3,1,1]

D [1,1,1,2,2,2,3,1]

💡 Hint

Check the dp Array State column at step 15 in the execution_table.

At which step does dp[6] first become 4?

A Step 22

B Step 20

C Step 18

D Step 26

💡 Hint

Look at the dp Array State and Action Taken columns for i=6 in the execution_table.

If the input array was strictly decreasing, what would be the dp array after initialization and processing?

A dp values become zero

B dp values increase progressively

C All dp values remain 1

D dp values alternate between 1 and 2

💡 Hint

Refer to the initialization step and condition checks in the execution_table where no updates happen if arr[j] < arr[i] is false.

Concept Snapshot

Longest Increasing Subsequence (LIS):
- Use dp array where dp[i] = length of LIS ending at i
- Initialize dp with 1 (each element alone)
- For each i, check all j < i:
  if arr[j] < arr[i], dp[i] = max(dp[i], dp[j] + 1)
- Result is max value in dp
- Time complexity: O(n^2)

Full Transcript

Longest Increasing Subsequence finds the longest strictly increasing sequence inside an array. We create a dp array where each position starts at 1, meaning the smallest subsequence is the element itself. For each element, we look back at all previous elements. If a previous element is smaller, we try to extend the subsequence ending there by updating dp[i]. After processing all elements, the maximum value in dp is the length of the longest increasing subsequence. This process is shown step-by-step in the execution_table, tracking dp updates and conditions. Key points include initializing dp with 1, only updating when previous elements are smaller, and taking the maximum dp value at the end.

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