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).