Longest Increasing Subsequence in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LIS length calculation

What is the output of the following JavaScript code that calculates the length of the Longest Increasing Subsequence (LIS) in the array?

DSA Javascript

function lengthOfLIS(nums) {
  const dp = 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 5

B 6

C 3

D 4

💡 Hint

Think about the longest increasing subsequence in the array [10,9,2,5,3,7,101,18].

The longest increasing subsequence is [2,3,7,101,18] but 18 is less than 101 so the actual LIS is [2,3,7,101] which has length 4. However, 18 is less than 101 so the LIS is actually [2,3,7,18] which has length 4. The correct LIS length is 4.

❓ Predict Output

intermediate

Output of LIS reconstruction code

What is the output of the following code that reconstructs one Longest Increasing Subsequence from the array?

DSA Javascript

function findLIS(nums) {
  const dp = Array(nums.length).fill(1);
  const prev = Array(nums.length).fill(-1);
  let maxIndex = 0;

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
        prev[i] = j;
      }
    }
    if (dp[i] > dp[maxIndex]) maxIndex = i;
  }

  const lis = [];
  for (let i = maxIndex; i >= 0; i = prev[i]) {
    lis.push(nums[i]);
    if (prev[i] === -1) break;
  }
  return lis.reverse();
}

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

A [0, 8, 12, 14]

B [0, 2, 6, 9]

C [0, 4, 6, 9, 14]

D [0, 4, 6, 9]

💡 Hint

Trace the dp and prev arrays to find the LIS path.

The longest increasing subsequence found by the code is [0, 8, 12, 14]. It is one valid LIS of length 4 in the array.

🧠 Conceptual

advanced

Time complexity of LIS dynamic programming approach

What is the time complexity of the classic dynamic programming solution to find the length of the Longest Increasing Subsequence in an array of length n?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

💡 Hint

Consider the nested loops in the DP approach.

The classic DP approach uses two nested loops over the array, resulting in O(n^2) time complexity.

❓ Predict Output

advanced

Output of LIS length using binary search optimization

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

DSA Javascript

function lengthOfLIS(nums) {
  const tails = [];
  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;
    }
    tails[left] = num;
  }
  return tails.length;
}

console.log(lengthOfLIS([3,5,7,1,2,8]));

A 5

B 4

C 3

D 6

💡 Hint

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

The LIS length is 4 for the subsequence [3,5,7,8] or [1,2,8]. The code returns tails.length which is 4.

🔧 Debug

expert

Identify the error in LIS reconstruction code

The following code attempts to reconstruct the Longest Increasing Subsequence but produces incorrect output. What is the cause of the error?

DSA Javascript

function reconstructLIS(nums) {
  const dp = Array(nums.length).fill(1);
  const prev = Array(nums.length).fill(-1);
  let maxLen = 1, maxIndex = 0;

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
        prev[i] = j;
      }
    }
    if (dp[i] > maxLen) {
      maxLen = dp[i];
      maxIndex = i;
    }
  }

  const lis = [];
  let current = maxIndex;
  while (current !== -1) {
    lis.push(nums[current]);
    current = prev[current];
  }
  return lis;
}

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

A The LIS array is not reversed before returning, so output is reversed.

B The dp array is not initialized correctly with zeros instead of ones.

C The prev array is not updated inside the inner loop.

D The maxLen variable is never updated.

💡 Hint

Check how the LIS array is built and returned.

The code builds the LIS array from the end to the start but does not reverse it before returning, so the output is reversed.

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 numbers are all equal

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

C. The longest subsequence with alternating increasing and decreasing numbers

D. The longest subsequence where each number is larger than the previous one

Solution

1. Step 1: Understand the definition of LIS and compare options

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one. The longest subsequence where each number is larger than the previous one matches the definition exactly, others describe different patterns.

2. Final Answer:

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

3. Quick Check:

   LIS = strictly increasing subsequence [OK]

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

Common Mistakes:

• Confusing increasing with decreasing subsequence
• Thinking LIS means contiguous elements only
• Assuming equal numbers are allowed in LIS

2. Which of the following JavaScript code snippets correctly initializes an array to store LIS lengths for each element in the input array arr?

easy

A. const lis = Array(arr.length).fill(0);

B. const lis = new Array(arr.length).fill(null);

C. const lis = new Array(arr.length).fill(1);

D. const lis = new Array(arr.length).fill(undefined);

Solution

1. Step 1: Understand LIS initialization and check syntax

   Each element starts with LIS length 1 because each element alone is a subsequence. const lis = new Array(arr.length).fill(1); correctly creates an array of length arr.length filled with 1s.

2. Final Answer:

   const lis = new Array(arr.length).fill(1); -> Option C

3. Quick Check:

   Initialize LIS array with 1s [OK]

Hint: LIS array starts with 1 for each element [OK]

Common Mistakes:

• Filling with 0 instead of 1
• Using fill(null) or fill(undefined) which are incorrect for LIS
• Not matching array length to input array

3. What is the length of the Longest Increasing Subsequence for the array [10, 22, 9, 33, 21, 50, 41, 60]?

medium

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Identify increasing subsequences and confirm no longer exists

   Possible LIS includes [10, 22, 33, 50, 60] which has length 5. Checking other subsequences shows none longer than 5.

2. Final Answer:

   5 -> Option B

3. Quick Check:

   LIS length for given array = 5 [OK]

Hint: Trace increasing numbers, pick longest chain [OK]

Common Mistakes:

• Counting non-increasing sequences
• Confusing subsequence with subarray
• Missing longer subsequences by skipping elements

4. Consider this JavaScript code snippet to find LIS length:

function lengthOfLIS(arr) {
  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[i] > arr[j]) {
        lis[i] = Math.max(lis[i], lis[j] + 1);
      }
    }
  }
  return lis[arr.length];
}

What is the error in this code?

medium

A. Returns lis[arr.length] which is undefined, should return max value in lis array

B. Incorrect initialization of lis array with 1s

C. The inner loop should start from i instead of 0

D. The comparison should be arr[i] < arr[j] instead of arr[i] > arr[j]

Solution

1. Step 1: Check return statement and correct return logic

   Returning lis[arr.length] accesses out-of-bounds index (undefined). Should return the maximum value in lis array, e.g., Math.max(...lis).

2. Final Answer:

   Returns lis[arr.length] which is undefined, should return max value in lis array -> Option A

3. Quick Check:

   Return max LIS length, not out-of-bounds element [OK]

Hint: Return max value in lis array, not lis[arr.length] [OK]

Common Mistakes:

• Returning wrong index from lis array
• Misunderstanding loop ranges
• Reversing comparison operators

5. Given the array [3, 10, 2, 1, 20], which of the following code snippets correctly finds the length of the Longest Increasing Subsequence using binary search optimization?

hard

A. function lengthOfLIS(arr) {
const tails = [];
for (const num of arr) {
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;
}
tails[left] = num;
}
return tails.length;
}

B. function lengthOfLIS(arr) {
const tails = [];
for (const num of arr) {
let left = 0, right = tails.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] <= num) left = mid + 1;
else right = mid - 1;
}
tails[left] = num;
}
return tails.length;
}

C. function lengthOfLIS(arr) {
const tails = [];
for (const num of arr) {
let left = 0, right = tails.length;
while (left < right) {
const mid = Math.ceil((left + right) / 2);
if (tails[mid] > num) right = mid - 1;
else left = mid + 1;
}
tails[left] = num;
}
return tails.length;
}

D. function lengthOfLIS(arr) {
const tails = [];
for (const num of arr) {
let left = 0, right = tails.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] > num) right = mid;
else left = mid + 1;
}
tails[left] = num;
}
return tails.length;
}

Solution

1. Step 1: Understand binary search in tails array and check boundaries/conditions

   We find the position to replace or append the current number to keep tails sorted. function lengthOfLIS(arr) { const tails = []; for (const num of arr) { 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; } tails[left] = num; } return tails.length; } uses correct boundaries and conditions: left < right, mid floor, tails[mid] < num moves left up.

2. Final Answer:

   function lengthOfLIS(arr) { const tails = []; for (const num of arr) { 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; } tails[left] = num; } return tails.length; } -> Option A

3. Quick Check:

   Binary search with left < right and tails[mid] < num [OK]

Hint: Use binary search with left < right and tails[mid] < num [OK]

Common Mistakes:

• Using wrong binary search boundaries (<= instead of <)
• Incorrect mid calculation (ceil instead of floor)
• Wrong comparison operators in binary search