Longest Increasing Subsequence in DSA Go - 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.

func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    maxLen := 0
    for i := 0; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
            }
        }
        if dp[i] > maxLen {
            maxLen = dp[i]
        }
    }
    return maxLen
}

This code finds the length of the longest increasing subsequence in an integer slice using dynamic programming.

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 times n.

How Execution Grows With Input

As the input size grows, the number of comparisons grows roughly by the square of the size.

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

Pattern observation: Doubling the input size roughly quadruples the work needed.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the input size, so bigger lists take much more time.

Common Mistake

[X] Wrong: "The inner loop runs a fixed number of times, so the algorithm is O(n)."

[OK] Correct: The inner loop depends on the current position i, so it grows with input size, making the total work grow like n squared.

Interview Connect

Understanding this time complexity helps you explain why some solutions are slower and shows your grasp of nested loops and dynamic programming patterns.

Self-Check

"What if we used a binary search approach to find the position to update instead of the inner loop? How would the time complexity change?"

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask for in a given sequence of numbers?

easy

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

B. The longest contiguous subarray with equal elements

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

D. The sum of all increasing numbers in the sequence

Solution

1. Step 1: Understand the LIS definition

   The LIS is a subsequence (not necessarily contiguous) where every next number is strictly greater than the previous.

2. Step 2: Compare options with definition

   The longest subsequence where each number is larger than the previous one matches the LIS definition exactly. Other options describe different concepts.

3. Final Answer:

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

4. Quick Check:

   LIS = strictly increasing subsequence [OK]

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

Common Mistakes:

• Confusing subsequence with subarray
• Thinking LIS requires contiguous elements
• Mixing increasing with decreasing sequences

2. Which of the following Go code snippets correctly initializes a slice to store LIS lengths for each element in an input array nums?

easy

A. lis := make([]int, 0, len(nums))

B. lis := []int{}

C. var lis [len(nums)]int

D. lis := make([]int, len(nums))

Solution

1. Step 1: Understand slice initialization for fixed length

   We need a slice with length equal to input length to store LIS lengths at each index.

2. Step 2: Check each option

   lis := make([]int, len(nums)) creates a slice with length len(nums), ready to store values. lis := []int{} creates empty slice with length 0. var lis [len(nums)]int is invalid syntax for arrays with dynamic length. lis := make([]int, 0, len(nums)) creates slice with length 0 but capacity len(nums), so cannot index directly.

3. Final Answer:

   lis := make([]int, len(nums)) -> Option D

4. Quick Check:

   Slice with length = len(nums) for LIS storage [OK]

Hint: Use make with length for direct indexing [OK]

Common Mistakes:

• Using empty slice without length
• Trying to declare array with variable length
• Confusing capacity with length

3. What is the output of the following Go code that calculates the length of the LIS for nums := []int{10, 9, 2, 5, 3, 7, 101, 18}?

func lengthOfLIS(nums []int) int {
    lis := make([]int, len(nums))
    for i := range lis {
        lis[i] = 1
    }
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && lis[i] < lis[j]+1 {
                lis[i] = lis[j] + 1
            }
        }
    }
    maxLen := 0
    for _, length := range lis {
        if length > maxLen {
            maxLen = length
        }
    }
    return maxLen
}

fmt.Println(lengthOfLIS(nums))

medium

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Initialize LIS array with 1s

   Each element starts with LIS length 1 (itself).

2. Step 2: Update LIS values by checking previous elements

   Check pairs (i,j) where nums[i] > nums[j], update lis[i] = max(lis[i], lis[j]+1).

3. Step 3: Calculate max LIS length

   For given nums, LIS is [2,3,7,101] length 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   LIS length for example = 4 [OK]

Hint: Trace LIS updates for each element [OK]

Common Mistakes:

• Confusing subsequence with subarray
• Not updating lis[i] correctly
• Forgetting to initialize lis with 1

4. Identify the bug in this Go function that attempts to compute the LIS length:

func lengthOfLIS(nums []int) int {
    lis := make([]int, len(nums))
    for i := 0; i < len(nums); i++ {
        lis[i] = 0
    }
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && lis[i] < lis[j] + 1 {
                lis[i] = lis[j] + 1
            }
        }
    }
    maxLen := 0
    for _, length := range lis {
        if length > maxLen {
            maxLen = length
        }
    }
    return maxLen
}

medium

A. lis slice is initialized with zeros instead of ones

B. The outer loop should start from 0 instead of 1

C. The condition nums[i] > nums[j] is incorrect

D. maxLen should be initialized to 1 instead of 0

Solution

1. Step 1: Check lis initialization

   lis should start with 1 for each element because each element alone is a subsequence of length 1.

2. Step 2: Effect of zero initialization

   Starting with 0 causes maxLen to be zero if no updates happen, giving wrong result.

3. Final Answer:

   lis slice is initialized with zeros instead of ones -> Option A

4. Quick Check:

   Initialize lis with 1, not 0 [OK]

Hint: Initialize LIS array elements to 1 [OK]

Common Mistakes:

• Starting lis values at 0
• Wrong loop start index
• Misunderstanding LIS condition

5. Given the sequence nums := []int{3, 10, 2, 1, 20}, which of the following is the correct longest increasing subsequence returned by a function that reconstructs the LIS (not just its length)?

hard

A. [2, 10, 20]

B. [3, 10, 20]

C. [1, 2, 20]

D. [3, 2, 20]

Solution

1. Step 1: Identify increasing subsequences

   Check subsequences where each next number is bigger than previous.

2. Step 2: Find longest valid subsequence

   Possible LIS are [3,10,20] and [1,20], but [3,10,20] is longer with length 3.

3. Step 3: Verify options

   [3, 10, 20] matches the longest increasing subsequence. [2, 10, 20] and C start with smaller numbers but 2 is after 10 in original, so invalid subsequence. [3, 2, 20] is not increasing.

4. Final Answer:

   [3, 10, 20] -> Option B

5. Quick Check:

   Longest increasing subsequence = [3, 10, 20] [OK]

Hint: Check order and increasing property carefully [OK]

Common Mistakes:

• Choosing subsequences not in original order
• Picking non-increasing sequences
• Confusing length with actual subsequence