Longest Increasing Subsequence in DSA C# - Time & Space Complexity

Time Complexity: Longest Increasing Subsequence

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find the longest increasing subsequence changes as the input list grows.

How does the number of steps grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int LengthOfLIS(int[] nums) {
    int n = nums.Length;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.Max(dp[i], dp[j] + 1);
            }
        }
    }
    return dp.Max();
}
    

This code finds the length of the longest increasing subsequence by checking all previous elements for each element.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where for each element, we check all previous elements.
• How many times: Outer loop runs n times, inner loop runs up to i times, so roughly n x n = n² times.

How Execution Grows With Input

As the input size grows, the number of checks grows much faster because each new element compares with all before it.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The operations grow roughly by the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if the input size doubles, the time to run roughly quadruples.

Common Mistake

[X] Wrong: "Since we only loop through the list once, the time is O(n)."

[OK] Correct: Because inside the main loop, there is another loop that checks all previous elements, making it much slower than a single pass.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and shows you can analyze nested loops clearly.

Self-Check

"What if we used a binary search approach inside the loop? How would the time complexity change?"

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask you to find in a sequence of numbers?

easy

A. The shortest subsequence with increasing numbers

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

C. The longest subsequence where numbers are equal

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

Solution

1. Step 1: Understand the problem definition

   The LIS problem looks for a subsequence where every next number is bigger than the one before it.

2. Step 2: Compare options with the definition

   Only The longest subsequence where each number is larger than the previous one matches this definition exactly.

3. Final Answer:

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

4. Quick Check:

   LIS = increasing subsequence [OK]

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

Common Mistakes:

• Confusing increasing with decreasing subsequence
• Thinking LIS means contiguous elements
• Assuming equal numbers count as increasing

2. Which of the following C# code snippets correctly initializes an array to find LIS length?

easy

A. int[] dp = new int[n]; for(int i=0; i

B. int dp[] = new int[n]; for(int i=0; i

C. int[] dp = new int[n]; for(int i=0; i<=n; i++) dp[i] = 1;

D. int[] dp = new int[n+1]; for(int i=1; i<=n; i++) dp[i] = 1;

Solution

1. Step 1: Check array initialization syntax

   int[] dp = new int[n]; for(int i=0; i

2. Step 2: Identify errors in other options

   int dp[] = new int[n]; for(int i=0; i

3. Final Answer:

   int[] dp = new int[n]; for(int i=0; i -> Option A

4. Quick Check:

   Correct array init and loop range [OK]

Hint: Use zero-based indexing and initialize dp with 1 [OK]

Common Mistakes:

• Using wrong loop bounds causing index errors
• Initializing dp elements to 0 instead of 1
• Incorrect array declaration syntax

3. What is the output of the following C# code snippet?

int[] arr = {10, 22, 9, 33, 21, 50, 41, 60};
int n = arr.Length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) dp[i] = 1;
for (int i = 1; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
      dp[i] = dp[j] + 1;
    }
  }
}
int max = 0;
for (int i = 0; i < n; i++) {
  if (dp[i] > max) max = dp[i];
}
Console.WriteLine(max);

medium

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Trace dp array updates for LIS length

   Initial dp = [1,1,1,1,1,1,1,1]. Update dp as we find increasing subsequences: - i=1: arr[1]=22 > arr[0]=10, dp[1]=max(1, dp[0]+1)=2 - i=2: arr[2]=9 no update - i=3: arr[3]=33 > 22, dp[3]=max(1, dp[1]+1)=3 - i=4: arr[4]=21 > 10, dp[4]=2; also 21 < 22 no update - i=5: arr[5]=50 > 33, dp[5]=max(1, dp[3]+1)=4 - i=6: arr[6]=41 > 33, dp[6]=max(1, dp[3]+1)=4; also 41 > 21 dp[4]+1=3 no update - i=7: arr[7]=60 > 50 dp[5]+1=5, dp[7]=5 Final dp = [1,2,1,3,2,4,4,5]

2. Step 2: Find max value in dp

   Max dp value is 5, which is the length of the LIS.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   LIS length = 5 [OK]

Hint: Track dp updates for each element comparing previous smaller elements [OK]

Common Mistakes:

• Not updating dp[i] correctly inside nested loops
• Confusing max dp value with sum of elements
• Off-by-one errors in loops

4. Identify the bug in this LIS code snippet and choose the correct fix:

int[] arr = {3, 10, 2, 1, 20};
int n = arr.Length;
int[] dp = new int[n];
for (int i = 0; i <= n; i++) dp[i] = 1;  // Bug here
for (int i = 1; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
      dp[i] = dp[j] + 1;
    }
  }
}
int max = dp[0];
for (int i = 1; i < n; i++) {
  if (dp[i] > max) max = dp[i];
}
Console.WriteLine(max);

medium

A. Remove the initialization loop entirely

B. Change 'i <= n' to 'i < n' in the initialization loop

C. Change inner loop to 'for (int j = 1; j < i; j++)'

D. Initialize dp array with zeros instead of ones

Solution

1. Step 1: Identify the cause of runtime error

   The loop 'for (int i = 0; i <= n; i++)' tries to access dp[n], which is out of bounds since dp size is n (0 to n-1).

2. Step 2: Fix the loop condition

   Changing the loop condition to 'i < n' prevents out-of-range access and correctly initializes all dp elements to 1.

3. Final Answer:

   Change 'i <= n' to 'i < n' in the initialization loop -> Option B

4. Quick Check:

   Loop bounds must match array size [OK]

Hint: Check loop bounds carefully to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loops over arrays
• Initializing dp with zeros causing wrong LIS length
• Changing inner loop start incorrectly

5. Given the sequence {5, 7, 4, 8, 6, 9}, what is the length of the Longest Increasing Subsequence if you must also skip any number that is even?

hard

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Filter out even numbers from the sequence

   Original: 5, 7, 4, 8, 6, 9 Remove even: 5, 7, 9

2. Step 2: Find LIS length on filtered sequence

   Sequence is 5, 7, 9 which is strictly increasing. Length = 3. But question says "must also skip any number that is even" so 4,8,6 are removed. However, 7 is odd, so sequence is 5,7,9.

3. Step 3: Re-examine options and question carefully

   Wait, the question says "must also skip any number that is even" meaning we cannot include even numbers in LIS. So LIS is on 5,7,9 with length 3. But options do not have 3 as correct answer except 3. Check if 7 is odd? Yes. So LIS length is 3.

4. Final Answer:

   3 -> Option C

5. Quick Check:

   Filter evens, LIS length = 3 [OK]

Hint: Filter out evens first, then find LIS length [OK]

Common Mistakes:

• Including even numbers in LIS calculation
• Confusing subsequence with substring
• Miscounting length after filtering