Longest Increasing Subsequence in DSA Go - Execution Trace

Concept Flow - Longest Increasing Subsequence

Start with empty LIS array

↓

For each element in input array

↓

Find position in LIS to place element

↓

If element > all in LIS, append

↓

Else replace element in LIS to keep it minimal

↓

Repeat for all elements

↓

Length of LIS array is result

We build a list representing the smallest possible last elements of increasing subsequences of different lengths. For each input element, we find where it fits to keep this list minimal and increasing.

Execution Sample

DSA Go

arr := []int{10, 9, 2, 5, 3, 7, 101, 18}
LIS := []int{}
for _, num := range arr {
  pos := binarySearch(LIS, num)
  if pos == len(LIS) {
    LIS = append(LIS, num)
  } else {
    LIS[pos] = num
  }
}
fmt.Println(len(LIS))

This code finds the length of the longest increasing subsequence by maintaining a list LIS and updating it using binary search.

Execution Table

Step	Operation	Current Number	LIS Before	Binary Search Position	LIS After	Visual State
1	Start	-	[]	-	[]	[]
2	Process element	10	[]	0 (empty)	[10]	[10]
3	Process element	9	[10]	0 (replace 10)	[9]	[9]
4	Process element	2	[9]	0 (replace 9)	[2]	[2]
5	Process element	5	[2]	1 (append)	[2,5]	[2 -> 5]
6	Process element	3	[2,5]	1 (replace 5)	[2,3]	[2 -> 3]
7	Process element	7	[2,3]	2 (append)	[2,3,7]	[2 -> 3 -> 7]
8	Process element	101	[2,3,7]	3 (append)	[2,3,7,101]	[2 -> 3 -> 7 -> 101]
9	Process element	18	[2,3,7,101]	3 (replace 101)	[2,3,7,18]	[2 -> 3 -> 7 -> 18]
10	End	-	[2,3,7,18]	-	-	Length of LIS = 4

💡 All elements processed; LIS length is 4

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
LIS	[]	[10]	[9]	[2]	[2,5]	[2,3]	[2,3,7]	[2,3,7,101]	[2,3,7,18]	[2,3,7,18]
Current Number	-	10	9	2	5	3	7	101	18	-
Binary Search Position	-	0	0	0	1	1	2	3	3	-

Key Moments - 3 Insights

Why do we replace elements in LIS instead of always appending?

Replacing elements keeps LIS minimal at each length, allowing longer increasing subsequences later. See steps 3, 4, 6, and 9 in execution_table where replacement happens.

Why does the binary search position sometimes equal the length of LIS?

When the current number is greater than all elements in LIS, binary search returns position equal to LIS length, so we append. See steps 5, 7, and 8.

Does LIS array always represent a real subsequence from input?

No, LIS stores minimal last elements for subsequences of each length, not the actual subsequence. It helps find length efficiently.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the LIS after processing number 3?

A [2,3]

B [2,5]

C [3,5]

D [2,3,7]

💡 Hint

Check the 'LIS After' column at step 6 in execution_table.

At which step does the LIS length first become 3?

A Step 5

B Step 7

C Step 8

D Step 9

💡 Hint

Look at the 'LIS After' column and count elements at each step.

If the input number at step 9 was 102 instead of 18, what would happen to LIS?

A Replace 101 with 102

B Append 102 to LIS

C Replace 18 with 102

D No change to LIS

💡 Hint

Binary search position would be equal to LIS length, so append instead of replace.

Concept Snapshot

Longest Increasing Subsequence (LIS):
- Maintain an array LIS storing smallest possible tail for subsequences of each length.
- For each number, use binary search to find position in LIS.
- If number > all LIS elements, append it.
- Else replace element at found position to keep LIS minimal.
- Length of LIS array is length of longest increasing subsequence.

Full Transcript

Longest Increasing Subsequence finds the longest sequence of increasing numbers in an array. We keep a list called LIS that stores the smallest possible last numbers for increasing subsequences of different lengths. For each number in the input, we find where it fits in LIS using binary search. If it is bigger than all, we add it to the end. Otherwise, we replace the element in LIS to keep it minimal. This way, LIS length at the end gives the length of the longest increasing subsequence. The actual LIS array may not be a real subsequence but helps find the length efficiently.

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