Longest Increasing Subsequence in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LIS length calculation

What is the output of the following TypeScript code that calculates the length of the Longest Increasing Subsequence (LIS) for the given array?

DSA Typescript

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

A 4

B 3

C 6

D 5

💡 Hint

Trace the dp array updates for each element comparing with previous elements.

The longest increasing subsequence in the array [10, 9, 2, 5, 3, 7, 101, 18] has length 4. One such subsequence is [2, 3, 7, 101]. The dp array stores the length of LIS ending at each index, and the maximum value in dp is the answer.

🧠 Conceptual

intermediate

Understanding LIS subsequence reconstruction

Which data structure is commonly used to reconstruct the actual Longest Increasing Subsequence after computing its length using dynamic programming?

A Set to keep unique elements of the subsequence

B Queue to store all subsequences during computation

C Hash map to store frequency of elements

D Stack to trace back indices from dp array

💡 Hint

Think about how to backtrack from the dp array to find the sequence.

After computing the dp array for LIS lengths, a stack is often used to trace back the indices of elements forming the LIS by moving from the maximum dp value backward.

🔧 Debug

advanced

Identify the error in LIS length code

What error will the following TypeScript code produce when trying to compute the LIS length?

DSA Typescript

function lengthOfLIS(nums: number[]): number {
  const dp: number[] = 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([3, 4, 2, 8, 10]));

A Runtime error: Index out of bounds

B Returns incorrect LIS length 1

C Syntax error due to missing semicolon

D Returns correct LIS length 4

💡 Hint

Check the loop boundary conditions carefully.

The outer loop uses i <= nums.length which causes nums[i] and dp[i] to access an index equal to nums.length, which is out of bounds and causes a runtime error.

🚀 Application

advanced

Find LIS length with binary search optimization

What is the output of the following TypeScript code that uses binary search to find the length of the Longest Increasing Subsequence?

DSA Typescript

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const num of nums) {
    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;
    }
    if (right < tails.length) tails[right] = num;
    else tails.push(num);
  }
  return tails.length;
}

console.log(lengthOfLIS([0, 8, 4, 12, 2, 10, 6, 14, 1, 9]));

A 7

B 5

C 6

D 4

💡 Hint

The tails array stores the smallest possible tail for increasing subsequences of different lengths.

The binary search method efficiently finds the length of LIS. For the input, the LIS length is 5, for example [0, 2, 6, 9, 14].

🧠 Conceptual

expert

Time complexity of LIS algorithms

Which of the following statements correctly describes the time complexity of the classic dynamic programming LIS algorithm and the binary search optimized LIS algorithm?

A Classic DP: O(n log n), Binary Search optimized: O(n^2)

B Both algorithms have O(n^2) time complexity

C Classic DP: O(n^2), Binary Search optimized: O(n log n)

D Both algorithms have O(n log n) time complexity

💡 Hint

Consider nested loops vs binary search usage.

The classic DP approach uses two nested loops resulting in O(n^2) time. The binary search optimized approach uses a tails array and binary search, reducing time to O(n log n).

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