Longest Increasing Subsequence in DSA Typescript - Execution Trace

Concept Flow - Longest Increasing Subsequence

Start with array

↓

Initialize LIS array with 1s

↓

For each element i from 1 to end

↓

For each element j before i

↓

If arr[j

↓

Update LIS[i

↓

Repeat until all elements processed

↓

Find max value in LIS array

↓

Result: length of longest increasing subsequence

We start with the array and build an LIS array that stores the longest increasing subsequence length ending at each index. We update LIS values by checking previous elements smaller than current. Finally, we find the maximum LIS value.

Execution Sample

DSA Typescript

const arr = [10, 22, 9, 33, 21, 50, 41, 60];
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[j] < arr[i] && LIS[i] < LIS[j] + 1) LIS[i] = LIS[j] + 1;
  }
}
const maxLIS = Math.max(...LIS);

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

Execution Table

Step	Operation	i	j	Condition arr[j]<arr[i]	Condition LIS[i]<LIS[j]+1	LIS Array State	Visual State
1	Initialize LIS	-	-	-	-	[1, 1, 1, 1, 1, 1, 1, 1]	10(1) 22(1) 9(1) 33(1) 21(1) 50(1) 41(1) 60(1)
2	i=1, j=0	1	0	10 < 22: true	1 < 1+1: true	[1, 2, 1, 1, 1, 1, 1, 1]	10(1) 22(2) 9(1) 33(1) 21(1) 50(1) 41(1) 60(1)
3	i=2, j=0	2	0	10 < 9: false	-	[1, 2, 1, 1, 1, 1, 1, 1]	10(1) 22(2) 9(1) 33(1) 21(1) 50(1) 41(1) 60(1)
4	i=2, j=1	2	1	22 < 9: false	-	[1, 2, 1, 1, 1, 1, 1, 1]	10(1) 22(2) 9(1) 33(1) 21(1) 50(1) 41(1) 60(1)
5	i=3, j=0	3	0	10 < 33: true	1 < 1+1: true	[1, 2, 1, 2, 1, 1, 1, 1]	10(1) 22(2) 9(1) 33(2) 21(1) 50(1) 41(1) 60(1)
6	i=3, j=1	3	1	22 < 33: true	2 < 2+1: true	[1, 2, 1, 3, 1, 1, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(1) 50(1) 41(1) 60(1)
7	i=3, j=2	3	2	9 < 33: true	3 < 1+1: false	[1, 2, 1, 3, 1, 1, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(1) 50(1) 41(1) 60(1)
8	i=4, j=0	4	0	10 < 21: true	1 < 1+1: true	[1, 2, 1, 3, 2, 1, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(1) 41(1) 60(1)
9	i=4, j=1	4	1	22 < 21: false	-	[1, 2, 1, 3, 2, 1, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(1) 41(1) 60(1)
10	i=4, j=2	4	2	9 < 21: true	2 < 1+1: false	[1, 2, 1, 3, 2, 1, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(1) 41(1) 60(1)
11	i=4, j=3	4	3	33 < 21: false	-	[1, 2, 1, 3, 2, 1, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(1) 41(1) 60(1)
12	i=5, j=0	5	0	10 < 50: true	1 < 1+1: true	[1, 2, 1, 3, 2, 2, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(2) 41(1) 60(1)
13	i=5, j=1	5	1	22 < 50: true	2 < 2+1: true	[1, 2, 1, 3, 2, 3, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(3) 41(1) 60(1)
14	i=5, j=2	5	2	9 < 50: true	3 < 1+1: false	[1, 2, 1, 3, 2, 3, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(3) 41(1) 60(1)
15	i=5, j=3	5	3	33 < 50: true	3 < 3+1: true	[1, 2, 1, 3, 2, 4, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(1) 60(1)
16	i=5, j=4	5	4	21 < 50: true	4 < 2+1: false	[1, 2, 1, 3, 2, 4, 1, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(1) 60(1)
17	i=6, j=0	6	0	10 < 41: true	1 < 1+1: true	[1, 2, 1, 3, 2, 4, 2, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(2) 60(1)
18	i=6, j=1	6	1	22 < 41: true	2 < 2+1: true	[1, 2, 1, 3, 2, 4, 3, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(3) 60(1)
19	i=6, j=2	6	2	9 < 41: true	3 < 1+1: false	[1, 2, 1, 3, 2, 4, 3, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(3) 60(1)
20	i=6, j=3	6	3	33 < 41: true	3 < 3+1: true	[1, 2, 1, 3, 2, 4, 4, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(1)
21	i=6, j=4	6	4	21 < 41: true	4 < 2+1: false	[1, 2, 1, 3, 2, 4, 4, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(1)
22	i=6, j=5	6	5	50 < 41: false	-	[1, 2, 1, 3, 2, 4, 4, 1]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(1)
23	i=7, j=0	7	0	10 < 60: true	1 < 1+1: true	[1, 2, 1, 3, 2, 4, 4, 2]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(2)
24	i=7, j=1	7	1	22 < 60: true	2 < 2+1: true	[1, 2, 1, 3, 2, 4, 4, 3]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(3)
25	i=7, j=2	7	2	9 < 60: true	3 < 1+1: false	[1, 2, 1, 3, 2, 4, 4, 3]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(3)
26	i=7, j=3	7	3	33 < 60: true	3 < 3+1: true	[1, 2, 1, 3, 2, 4, 4, 4]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(4)
27	i=7, j=4	7	4	21 < 60: true	4 < 2+1: false	[1, 2, 1, 3, 2, 4, 4, 4]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(4)
28	i=7, j=5	7	5	50 < 60: true	4 < 4+1: true	[1, 2, 1, 3, 2, 4, 4, 5]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(5)
29	i=7, j=6	7	6	41 < 60: true	5 < 4+1: false	[1, 2, 1, 3, 2, 4, 4, 5]	10(1) 22(2) 9(1) 33(3) 21(2) 50(4) 41(4) 60(5)
30	Find max LIS	-	-	-	-	[1, 2, 1, 3, 2, 4, 4, 5]	Longest Increasing Subsequence length = 5

💡 All elements processed, maximum LIS value found as 5

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
i	-	1	2	3	4	5	6	-
j	-	0	1	2	3	4	5	-
LIS	[1,1,1,1,1,1,1,1]	[1,2,1,1,1,1,1,1]	[1,2,1,1,1,1,1,1]	[1,2,1,3,1,1,1,1]	[1,2,1,3,2,1,1,1]	[1,2,1,3,2,4,1,1]	[1,2,1,3,2,4,4,1]	[1,2,1,3,2,4,4,5]

Key Moments - 3 Insights

Why do we initialize the LIS array with all 1s?

Because each element alone is an increasing subsequence of length 1. This is shown in execution_table row 1 where LIS starts as all 1s.

Why do we check both conditions arr[j] < arr[i] and LIS[i] < LIS[j] + 1 before updating LIS[i]?

We only update LIS[i] if arr[j] is smaller (to keep increasing order) and if extending the subsequence ending at j makes LIS[i] longer. This is clear in rows 2 and 6 where both conditions are true before updating.

Why does the LIS value sometimes not change even if arr[j] < arr[i]?

Because LIS[i] is already greater or equal to LIS[j] + 1, so no longer subsequence is formed. For example, in row 7, condition LIS[i]<LIS[j]+1 is false, so no update.

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What is the LIS array state after this step?

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

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

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

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

💡 Hint

Check the LIS Array State column in row 6 of execution_table.

At which step does the LIS value for index 7 first become 4 or more?

A Step 28

B Step 23

C Step 26

D Step 30

💡 Hint

Look at the LIS Array State and Visual State columns for index 7 in execution_table rows 23 to 28.

If the input array was strictly decreasing, how would the LIS array look after initialization and processing?

A All values remain 1

B Values increase from 1 to n

C Values alternate between 1 and 2

D Values become zero

💡 Hint

Refer to the initialization step and condition arr[j]

Concept Snapshot

Longest Increasing Subsequence (LIS):
- Initialize LIS array with 1s (each element alone)
- For each element i, check all j < i
- If arr[j] < arr[i] and LIS[i] < LIS[j] + 1, update LIS[i]
- Result is max value in LIS array
- Time complexity: O(n^2)

Full Transcript

Longest Increasing Subsequence finds the longest sequence of increasing numbers in an array. We start by creating an array LIS filled with 1s, meaning each element is a subsequence of length 1. Then, for each element, we look back at all previous elements. If a previous element is smaller and extending its subsequence makes a longer subsequence, we update the current LIS value. After processing all elements, the maximum value in LIS is the length of the longest increasing subsequence. This process is shown step-by-step in the execution table, tracking how LIS changes. Key points include why LIS starts with 1s, why both conditions must be true to update, and why sometimes LIS does not change even if the previous element is smaller.