Longest Increasing Subsequence in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LIS length calculation

What is the output of this Go code that calculates the length of the Longest Increasing Subsequence (LIS) for the given array?

DSA Go

package main
import "fmt"
func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    dp := make([]int, len(nums))
    for i := range dp {
        dp[i] = 1
    }
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && dp[i] < dp[j]+1 {
                dp[i] = dp[j] + 1
            }
        }
    }
    maxLen := 0
    for _, v := range dp {
        if v > maxLen {
            maxLen = v
        }
    }
    return maxLen
}
func main() {
    arr := []int{10, 9, 2, 5, 3, 7, 101, 18}
    fmt.Println(lengthOfLIS(arr))
}

A 4

B 5

C 3

D 6

💡 Hint

Trace the dp array updates for each element comparing with previous elements.

The code uses dynamic programming to find the length of the longest increasing subsequence. The longest increasing subsequence in the array [10, 9, 2, 5, 3, 7, 101, 18] is of length 4, for example: [2, 3, 7, 101].

🧠 Conceptual

intermediate

Understanding LIS subsequence reconstruction

Which data structure is most suitable to reconstruct the actual Longest Increasing Subsequence after computing its length using dynamic programming?

A A queue to store elements in insertion order

B A stack to store elements in reverse order

C A hash map to store element counts

D A linked list to store elements in sorted order

💡 Hint

Think about how you can backtrack from the end to the start of the subsequence.

After computing the LIS length, we often backtrack from the last element of the LIS to the first. Using a stack helps reverse the order so the subsequence is output in correct order.

❓ Predict Output

advanced

Output of LIS length using binary search optimization

What is the output of this Go code that uses binary search to find the length of the Longest Increasing Subsequence?

DSA Go

package main
import (
    "fmt"
    "sort"
)
func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, num := range nums {
        i := sort.Search(len(tails), func(i int) bool { return tails[i] >= num })
        if i == len(tails) {
            tails = append(tails, num)
        } else {
            tails[i] = num
        }
    }
    return len(tails)
}
func main() {
    arr := []int{0, 8, 4, 12, 2, 10, 6, 14, 1, 9}
    fmt.Println(lengthOfLIS(arr))
}

A 5

B 6

C 7

D 4

💡 Hint

The tails array length represents the LIS length.

This code uses a binary search approach to maintain a tails array where each element is the smallest possible tail of an increasing subsequence of a given length. The length of tails at the end is the LIS length. For the input, the LIS length is 4.

🔧 Debug

advanced

Identify the error in LIS length calculation code

What error will this Go code produce when trying to calculate the LIS length?

DSA Go

package main
import "fmt"
func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    for i := 0; i < len(nums); i++ {
        dp[i] = 1
    }
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && dp[i] < dp[j]+1 {
                dp[i] = dp[j] + 1
            }
        }
    }
    maxLen := 0
    for _, v := range dp {
        if v > maxLen {
            maxLen = v
        }
    }
    return maxLen
}
func main() {
    arr := []int{3, 4, 1, 2}
    fmt.Println(lengthOfLIS(arr))
}

A output: 4

B compilation error: missing return statement

C runtime error: index out of range

D output: 3

💡 Hint

Check the loop bounds when initializing dp array.

The loop initializing dp uses i <= len(nums), which tries to access dp[len(nums)] causing an index out of range runtime error.

🚀 Application

expert

Minimum removals to make array strictly increasing

Given an integer array, what is the minimum number of elements to remove to make the array strictly increasing? The code below uses LIS length to find the answer. What is the output for the input array?

DSA Go

package main
import "fmt"
func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    for i := range dp {
        dp[i] = 1
    }
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && dp[i] < dp[j]+1 {
                dp[i] = dp[j] + 1
            }
        }
    }
    maxLen := 0
    for _, v := range dp {
        if v > maxLen {
            maxLen = v
        }
    }
    return maxLen
}
func main() {
    arr := []int{5, 1, 6, 2, 3, 4}
    lisLen := lengthOfLIS(arr)
    fmt.Println(len(arr) - lisLen)
}

A 2

B 3

C 4

D 1

💡 Hint

Minimum removals = total length - LIS length.

The longest increasing subsequence length is 4 ([1, 2, 3, 4]). So minimum removals = 6 - 4 = 2.

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