Longest Increasing Subsequence in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Increasing Subsequence (LIS) in an array?

The Longest Increasing Subsequence is the longest sequence of numbers in the array where each number is strictly greater than the previous one, and the sequence does not need to be contiguous.

intermediate

What is the time complexity of the classic dynamic programming approach to find LIS?

The classic dynamic programming approach to find LIS has a time complexity of O(n²), where n is the length of the array.

beginner

In LIS problem, what does the DP array represent in the dynamic programming solution?

The DP array stores the length of the longest increasing subsequence ending at each index of the input array.

advanced

What is the optimized time complexity to find LIS using binary search?

Using binary search with a patience sorting technique, the LIS can be found in O(n log n) time.

beginner

Why does the LIS not require the subsequence to be contiguous?

Because the problem asks for a subsequence, which means elements can be taken from the array in order but not necessarily next to each other, allowing skipping elements to form a strictly increasing sequence.

What does the Longest Increasing Subsequence represent in an array?

A The longest sequence of equal numbers

B The longest contiguous increasing subarray

C The shortest increasing subsequence

D The longest sequence of strictly increasing numbers, not necessarily contiguous

LIS is about the longest strictly increasing sequence that can skip elements, so it is not necessarily contiguous.

What is the time complexity of the naive dynamic programming solution for LIS?

A O(n log n)

B O(n²)

C O(n)

D O(log n)

The classic DP solution compares each element with all previous ones, resulting in O(n²) time.

Which data structure or technique helps optimize LIS to O(n log n)?

A Binary Search

B Stack

C Queue

D Hash Map

Binary search is used on a helper array to efficiently find positions, reducing complexity to O(n log n).

In the DP approach, what does dp[i] represent?

A Length of LIS ending at index i

B Length of LIS starting at index i

C Value of the element at index i

D Index of the next element in LIS

dp[i] stores the length of the longest increasing subsequence that ends exactly at index i.

Can the LIS include elements that are not next to each other in the original array?

A Only if elements are decreasing

B No, it must be contiguous

C Yes, because it is a subsequence

D Only if elements are equal

A subsequence allows skipping elements, so LIS can include non-adjacent elements.

Explain how the dynamic programming approach finds the Longest Increasing Subsequence.

Think about building solutions for smaller parts and combining them.

Describe the optimization that reduces LIS time complexity from O(n²) to O(n log n).

Consider how binary search helps find positions quickly.

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