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.

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 each number is larger than the previous one

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

C. The longest subsequence where numbers are equal

D. The shortest subsequence with increasing numbers

Solution

1. Step 1: Understand the LIS definition

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with definition

   The longest subsequence where each number is larger than the previous one matches this definition exactly, others describe different or incorrect sequences.

3. Final Answer:

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

4. Quick Check:

   LIS means strictly increasing subsequence [OK]

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

Common Mistakes:

• Confusing increasing with decreasing subsequence
• Thinking LIS means contiguous sequence
• Assuming equal numbers count as increasing

2. Which of the following TypeScript function signatures correctly represents a function to find the length of the Longest Increasing Subsequence in an array of numbers?

easy

A. function lengthOfLIS(nums: number): string

B. function lengthOfLIS(nums: string): number

C. function lengthOfLIS(nums: number[]): number

D. function lengthOfLIS(nums: any): void

Solution

1. Step 1: Check parameter type

   The input should be an array of numbers, so type must be number[].

2. Step 2: Check return type

   The function returns the length of LIS, which is a number.

3. Final Answer:

   function lengthOfLIS(nums: number[]): number -> Option C

4. Quick Check:

   Input array of numbers, output number length [OK]

Hint: Input is number array, output is number length [OK]

Common Mistakes:

• Using string type for input instead of number array
• Returning string instead of number
• Using void return type when output is needed

3. What is the output of the following TypeScript code?

function lengthOfLIS(nums: number[]): number {
  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);
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));

medium

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Understand the DP array construction

   dp[i] stores length of LIS ending at index i. Initialize all to 1.

2. Step 2: Trace dp updates for input

   For input [10,9,2,5,3,7,101,18], dp becomes [1,1,1,2,2,3,4,4]. Max is 4.

3. Step 3: Re-check the dp array

   Actually, dp updates to [1,1,1,2,2,3,5,5] because 101 extends the subsequence ending at 7 (length 4), and 18 extends subsequence ending at 7 (length 4) as well.

4. Final Answer:

   5 -> Option A

5. Quick Check:

   LIS length for given array is 5 [OK]

Hint: DP array max value gives LIS length [OK]

Common Mistakes:

• Confusing LIS length with subsequence elements count
• Forgetting to update dp[i] with max value
• Misreading nested loops indices

4. Identify the bug in this TypeScript function for LIS and select the fix:

function lengthOfLIS(nums: number[]): number {
  const dp = new Array(nums.length).fill(0);
  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);
}

medium

A. Remove inner loop and use single loop

B. Initialize dp array with 1 instead of 0

C. Return Math.min(...dp) instead of Math.max(...dp)

D. Change loop to start i from 0 instead of 1

Solution

1. Step 1: Check dp initialization

   dp should start with 1 because each element alone is an LIS of length 1.

2. Step 2: Understand impact of zero initialization

   Starting with 0 causes dp values to be underestimated, leading to wrong max LIS length.

3. Final Answer:

   Initialize dp array with 1 instead of 0 -> Option B

4. Quick Check:

   dp starts at 1 for correct LIS length [OK]

Hint: dp array must start with 1 for each element [OK]

Common Mistakes:

• Initializing dp with 0 causing wrong results
• Changing loop start incorrectly
• Returning min instead of max

5. Given the array [3, 10, 2, 1, 20], what is the length of the Longest Increasing Subsequence if you must also return the subsequence itself? Which subsequence is correct?

hard

A. Length: 2, Subsequence: [10, 20]

B. Length: 4, Subsequence: [2, 3, 10, 20]

C. Length: 3, Subsequence: [1, 2, 20]

D. Length: 3, Subsequence: [3, 10, 20]

Solution

1. Step 1: Find LIS length and subsequence

   Possible LIS are [3,10,20] and [1,20], length 3 and 2 respectively. The longest is length 3.

2. Step 2: Verify subsequence correctness

   [3,10,20] is strictly increasing and length 3, matching the longest LIS length.

3. Final Answer:

   Length: 3, Subsequence: [3, 10, 20] -> Option D

4. Quick Check:

   LIS length 3 with subsequence [3,10,20] [OK]

Hint: Trace LIS and pick longest strictly increasing subsequence [OK]

Common Mistakes:

• Choosing subsequence with wrong order
• Confusing length with subsequence elements
• Assuming non-strictly increasing sequences