Longest Increasing Subsequence in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LIS length calculation

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

DSA Rust

fn length_of_lis(nums: Vec<i32>) -> usize {
    let mut dp = vec![1usize; nums.len()];
    for i in 1..nums.len() {
        for j in 0..i {
            if nums[i] > nums[j] {
                dp[i] = dp[i].max(dp[j] + 1usize);
            }
        }
    }
    *dp.iter().max().unwrap_or(&0usize)
}

fn main() {
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    println!("{}", length_of_lis(nums));
}

A 6

B 3

C 5

D 4

💡 Hint

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

The longest increasing subsequence is [2, 3, 7, 101], which has length 4.

❓ Predict Output

intermediate

Output of LIS reconstruction code

What is the printed output of this Rust code that reconstructs one Longest Increasing Subsequence from the input array?

DSA Rust

fn lis_sequence(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut dp = vec![1; n];
    let mut prev = vec![None; n];
    for i in 1..n {
        for j in 0..i {
            if nums[i] > nums[j] && dp[i] < dp[j] + 1 {
                dp[i] = dp[j] + 1;
                prev[i] = Some(j);
            }
        }
    }
    let mut max_index = 0;
    for i in 1..n {
        if dp[i] >= dp[max_index] {
            max_index = i;
        }
    }
    let mut lis = Vec::new();
    let mut current = Some(max_index);
    while let Some(i) = current {
        lis.push(nums[i]);
        current = prev[i];
    }
    lis.reverse();
    lis
}

fn main() {
    let nums = vec![0, 8, 4, 12, 2, 10, 6, 14, 1, 9];
    let result = lis_sequence(nums);
    println!("{:?}", result);
}

A [0, 4, 6, 9]

B [0, 8, 12, 14]

C [0, 2, 10, 14]

D [0, 2, 6, 9]

💡 Hint

Look for the LIS with maximum length and reconstruct by following prev indices.

The LIS found is [0, 4, 6, 9], which is one valid longest increasing subsequence.

🔧 Debug

advanced

Identify the error in LIS length code

This Rust code attempts to compute the length of the Longest Increasing Subsequence but produces incorrect results. What is the cause of the error?

DSA Rust

fn length_of_lis(nums: Vec<i32>) -> usize {
    let mut dp = vec![0usize; nums.len()];
    for i in 0..nums.len() {
        dp[i] = 1usize;
        for j in 0..i {
            if nums[i] > nums[j] {
                dp[i] = dp[i].max(dp[j] + 1usize);
            }
        }
    }
    *dp.iter().max().unwrap_or(&0usize)
}

fn main() {
    let nums = vec![3, 1, 2, 1, 8];
    println!("{}", length_of_lis(nums));
}

A The outer loop should start from 1, not 0, causing index out of range error.

B The comparison uses '>=' instead of '>' causing non-strictly increasing subsequence.

C The dp vector is initialized with zeros instead of ones causing wrong base values.

D The max function is called on dp before it is fully populated causing panic.

💡 Hint

Check the condition that compares elements for increasing order.

Using '>=' allows equal elements, which is not strictly increasing, so the LIS length is overcounted.

🧠 Conceptual

advanced

Time complexity of LIS algorithms

Which of the following statements correctly describes the time complexity of common algorithms to find the length of the Longest Increasing Subsequence (LIS)?

A The dynamic programming approach with nested loops runs in O(n^2), and the binary search optimized approach runs in O(n log n).

B Both the dynamic programming and binary search approaches run in O(n^2) time.

C The dynamic programming approach runs in O(n log n), and the binary search approach runs in O(n^2).

D Both approaches run in O(n log n) time but use different data structures.

💡 Hint

Consider how nested loops and binary search affect time complexity.

The classic DP approach uses two nested loops, resulting in O(n^2). The optimized method uses binary search on a tails array, achieving O(n log n).

🚀 Application

expert

Longest Increasing Subsequence in a sequence with duplicates

Given the input array [1, 3, 5, 4, 7, 4, 8], what is the length of the Longest Strictly Increasing Subsequence?

A 4

B 6

C 5

D 7

💡 Hint

Remember the subsequence must be strictly increasing, no equal elements allowed.

One LIS is [1, 3, 4, 7, 8], length 5. Duplicates like the second 4 cannot be included if it breaks strict increase.

Practice

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

easy

A. The longest sequence where each number is larger than the previous one

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

C. The longest sequence of equal numbers

D. The shortest sequence containing all numbers

Solution

1. Step 1: Understand the LIS definition

   The Longest Increasing Subsequence is the longest part of the list where every next number is bigger than the one before.

2. Step 2: Compare options with definition

   The longest sequence where each number is larger than the previous one matches the definition exactly. Other options describe different sequences.

3. Final Answer:

   The longest sequence where each number is larger than the previous one -> Option A

4. Quick Check:

   LIS = longest increasing sequence [OK]

Hint: LIS means strictly increasing sequence length [OK]

Common Mistakes:

• Confusing increasing with decreasing sequences
• Thinking LIS means equal numbers
• Mixing LIS with shortest sequences

2. Which Rust code snippet correctly initializes a vector to store LIS lengths for each element in a list named nums?

easy

A. let mut lis = vec![0; nums.len()];

B. let mut lis = vec![1; nums.len()];

C. let lis = vec![0; nums.len()];

D. let lis = vec![1; nums.len()];

Solution

1. Step 1: Understand LIS initialization

   Each element starts with LIS length 1 because the smallest subsequence includes the element itself.

2. Step 2: Check Rust syntax for mutable vector

   We need a mutable vector to update LIS values, so mut is required. The vector should be initialized with 1s.

3. Final Answer:

   let mut lis = vec![1; nums.len()]; -> Option B

4. Quick Check:

   Mutable vector with 1s = let mut lis = vec![1; nums.len()]; [OK]

Hint: LIS lengths start at 1, vector must be mutable [OK]

Common Mistakes:

• Initializing with zeros instead of ones
• Forgetting mut keyword for updates
• Using immutable vector when updates needed

3. What is the output of the following Rust code that calculates the length of the LIS for nums = vec![10, 9, 2, 5, 3, 7, 101, 18]?

fn length_of_lis(nums: Vec<i32>) -> usize {
    let n = nums.len();
    let mut lis = vec![1; n];
    for i in 1..n {
        for j in 0..i {
            if nums[i] > nums[j] {
                lis[i] = lis[i].max(lis[j] + 1);
            }
        }
    }
    *lis.iter().max().unwrap()
}

fn main() {
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    println!("{}", length_of_lis(nums));
}

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Trace LIS calculation for each element

   Starting with lis = [1,1,1,1,1,1,1,1]. - i=1: nums[1]=9 < 10, no update - i=2: nums[2]=2 < previous, no update - i=3: nums[3]=5 > 2, lis[3]=max(1, lis[2]+1)=2 - i=4: nums[4]=3 > 2, lis[4]=2 - i=5: nums[5]=7 > 5 and 3, lis[5]=max(1, lis[3]+1=3, lis[4]+1=3)=3 - i=6: nums[6]=101 > all previous, lis[6]=max(1, lis[5]+1=4, others less)=4 - i=7: nums[7]=18 > 7, lis[7]=max(1, lis[5]+1=4)=4

2. Step 2: Find maximum LIS value

   The maximum value in lis is 4, which is the length of the longest increasing subsequence.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   LIS length = 4 [OK]

Hint: Trace LIS array updates carefully for each element [OK]

Common Mistakes:

• Counting non-increasing sequences
• Forgetting to update lis[i] with max value
• Misreading the nested loops

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

fn length_of_lis(nums: Vec<i32>) -> usize {
    let n = nums.len();
    let mut lis = vec![1; n];
    for i in 0..n {
        for j in 0..i {
            if nums[i] < nums[j] {
                lis[i] = lis[i].max(lis[j] + 1);
            }
        }
    }
    *lis.iter().max().unwrap()
}

What is the error?

medium

A. The function should return the sum of lis instead of max

B. The vector lis should be initialized with zeros instead of ones

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

D. The comparison should be nums[i] > nums[j] instead of nums[i] < nums[j]

Solution

1. Step 1: Analyze the comparison condition

   The LIS requires increasing order, so we must check if nums[i] > nums[j]. The code incorrectly uses nums[i] < nums[j], which finds decreasing sequences.

2. Step 2: Confirm other parts are correct

   Initialization with ones and returning max are correct. Starting outer loop at 0 is valid but less efficient.

3. Final Answer:

   The comparison should be nums[i] > nums[j] instead of nums[i] < nums[j] -> Option D

4. Quick Check:

   Correct comparison is > for LIS [OK]

Hint: Check comparison signs for increasing sequences [OK]

Common Mistakes:

• Using less than instead of greater than
• Initializing lis with zeros
• Returning sum instead of max

5. Given a list nums = vec![3, 10, 2, 1, 20], how would you modify the LIS algorithm to also return the actual longest increasing subsequence, not just its length?

hard

A. Sort the list first, then find LIS length on sorted list

B. Use a stack to push elements and pop when sequence breaks

C. Keep a predecessor array to track previous indices and reconstruct the sequence after computing LIS lengths

D. Return the maximum value in nums as the LIS length and sequence

Solution

1. Step 1: Understand LIS length vs sequence

   Length calculation only tracks counts. To get the sequence, we must remember which elements lead to current LIS values.

2. Step 2: Use predecessor array for reconstruction

   Maintain an array storing the index of the previous element in the LIS for each position. After LIS lengths are computed, backtrack from the max index to build the sequence.

3. Step 3: Reject incorrect options

   Sorting changes order, invalid for LIS. Stack method is not standard for LIS. Returning max value is incorrect.

4. Final Answer:

   Keep a predecessor array to track previous indices and reconstruct the sequence after computing LIS lengths -> Option C

5. Quick Check:

   Predecessor array enables LIS reconstruction [OK]

Hint: Track previous indices to rebuild LIS sequence [OK]

Common Mistakes:

• Sorting input before LIS calculation
• Confusing stack usage with LIS logic
• Returning max element instead of sequence