Longest Increasing Subsequence in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the dp array with 1s for each element.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A0

B1

Cnums.length

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp with 0 instead of 1

Using nums.length as fill value

Each element starts with a subsequence length of 1 (the element itself).

2fill in blank

medium

Complete the code to check if nums[j] is less than nums[i] to extend the subsequence.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A<

B>=

C===

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of <

Using >= which allows equal values

We extend the subsequence only if nums[j] is smaller than nums[i].

3fill in blank

hard

Fix the error in updating dp[i] to the maximum length found so far.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Afloor

Bround

Cmax

Dmin

Attempts:

3 left

💡 Hint

Common Mistakes

Using Math.min which gives the shortest length

Using Math.floor or Math.round which are unrelated

We want the longest subsequence, so use Math.max to update dp[i].

4fill in blank

hard

Fill both blanks to find the maximum length in dp array after processing.

DSA Typescript

const maxLength = dp.[1]((a, b) => a [2] b ? a : b);

Drag options to blanks, or click blank then click option'

Areduce

Bmax

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using max as a method (not valid on arrays)

Using < which finds minimum

Use reduce with > to find the maximum value in dp.

5fill in blank

hard

Fill all three blanks to complete the LIS function that returns the length of the longest increasing subsequence.

DSA Typescript

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[j] [2] nums[i]) {
        dp[i] = Math.[3](dp[i], dp[j] + 1);
      }
    }
  }
  return dp.reduce((a, b) => a > b ? a : b);
}

Drag options to blanks, or click blank then click option'

A1

B<

Cmax

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1 for dp initialization

Using > instead of < in condition

Using Math.min instead of Math.max

Initialize dp with 1, check if nums[j] < nums[i], and update dp[i] with Math.max.

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