Longest Increasing Subsequence in DSA Typescript

Mental Model

Find the longest sequence of numbers that keeps going up without breaking order. We want the biggest chain where each number is bigger than the one before.

Analogy: Imagine climbing stairs where each step is higher than the last. You want to find the longest path going up without stepping down or sideways.

Array: [10] -> [22] -> [9] -> [33] -> [21] -> [50] -> [41] -> [60]
Longest Increasing Subsequence example: 10 -> 22 -> 33 -> 50 -> 60

Dry Run Walkthrough

Input: array: [10, 22, 9, 33, 21, 50, 41, 60]

Goal: Find the longest increasing subsequence in the array

Step 1: Start with first element 10, LIS length is 1

LIS lengths: [1, _, _, _, _, _, _, _]

Why: Each element alone is a subsequence of length 1

Step 2: Check 22: 22 > 10, so LIS at 22 is LIS at 10 + 1 = 2

LIS lengths: [1, 2, _, _, _, _, _, _]

Why: 22 can extend the subsequence ending at 10

Step 3: Check 9: 9 is not greater than 10 or 22, so LIS at 9 is 1

LIS lengths: [1, 2, 1, _, _, _, _, _]

Why: 9 starts a new subsequence

Step 4: Check 33: 33 > 10 (LIS=1), 33 > 22 (LIS=2), 33 > 9 (LIS=1), max LIS before 33 is 2, so LIS at 33 is 3

LIS lengths: [1, 2, 1, 3, _, _, _, _]

Why: 33 extends the longest subsequence ending before it

Step 5: Check 21: 21 > 10 (LIS=1), 21 < 22, 21 > 9 (LIS=1), max LIS before 21 is 2 (from 10 or 9?), so LIS at 21 is 3

LIS lengths: [1, 2, 1, 3, 3, _, _, _]

Why: 21 extends subsequence ending at 10 or 9

Step 6: Check 50: 50 > 10 (1), 50 > 22 (2), 50 > 9 (1), 50 > 33 (3), 50 > 21 (3), max LIS before 50 is 3, so LIS at 50 is 4

LIS lengths: [1, 2, 1, 3, 3, 4, _, _]

Why: 50 extends the longest subsequence ending before it

Step 7: Check 41: 41 > 10 (1), 41 > 22 (2), 41 > 9 (1), 41 > 33 (3), 41 > 21 (3), 41 < 50, max LIS before 41 is 3, so LIS at 41 is 4

LIS lengths: [1, 2, 1, 3, 3, 4, 4, _]

Why: 41 extends subsequence ending at 33 or 21

Step 8: Check 60: 60 > all previous elements, max LIS before 60 is 4 (from 50 or 41), so LIS at 60 is 5

LIS lengths: [1, 2, 1, 3, 3, 4, 4, 5]

Why: 60 extends the longest subsequence ending before it

Result:

Longest Increasing Subsequence length is 5

Annotated Code

DSA Typescript

class LongestIncreasingSubsequence {
  static findLIS(arr: number[]): number {
    const n = arr.length;
    if (n === 0) return 0;
    const lis = new Array(n).fill(1);

    for (let i = 1; i < n; i++) {
      for (let j = 0; j < i; j++) {
        if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
          lis[i] = lis[j] + 1; // update LIS length at i
        }
      }
    }

    return Math.max(...lis);
  }
}

const input = [10, 22, 9, 33, 21, 50, 41, 60];
const result = LongestIncreasingSubsequence.findLIS(input);
console.log(result);

const lis = new Array(n).fill(1);

Initialize LIS lengths to 1 for each element

for (let i = 1; i < n; i++) {

Traverse array from second element to end

for (let j = 0; j < i; j++) {

Check all elements before i

if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {

If current element can extend LIS ending at j

lis[i] = lis[j] + 1; // update LIS length at i

Update LIS length at i to longer subsequence

return Math.max(...lis);

Return the maximum LIS length found

Output

5

Complexity Analysis

Time: O(n^2) because for each element we check all previous elements

Space: O(n) for the array that stores LIS lengths for each element

vs Alternative: This is better than checking all subsequences (which is exponential), but slower than advanced O(n log n) methods that use binary search

Edge Cases

Empty array

Returns 0 because there are no elements

DSA Typescript

if (n === 0) return 0;

All elements equal

LIS length is 1 because no element is greater than previous

DSA Typescript

if (arr[i] > arr[j] && lis[i] < lis[j] + 1)

Strictly decreasing array

LIS length is 1 because no increasing pairs

DSA Typescript

if (arr[i] > arr[j] && lis[i] < lis[j] + 1)

When to Use This Pattern

When you need to find the longest sequence of increasing numbers in order, use the Longest Increasing Subsequence pattern because it helps find the longest chain without rearranging elements.

Common Mistakes

Mistake: Updating LIS length without checking if it is longer than current value
Fix: Add condition lis[i] < lis[j] + 1 before updating to avoid overwriting longer subsequences

Summary

Finds the length of the longest increasing subsequence in an array.

Use when you want the longest ordered chain of increasing numbers without changing order.

Remember to build LIS lengths by extending previous smaller elements and keep track of the maximum.

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