Longest Increasing Subsequence in DSA Rust - 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 longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the length of the longest increasing subsequence by checking all pairs and building up answers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops comparing pairs of elements.
• How many times: Outer loop runs n times, inner loop runs up to n times for each outer loop.

How Execution Grows With Input

As the list size grows, the number of comparisons grows much faster because each new element is compared with all before it.

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

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

Final Time Complexity

Time Complexity: O(n²)

This means if the list doubles in size, the work needed grows about four times.

Common Mistake

[X] Wrong: "The algorithm only looks at each element once, so it must be O(n)."

[OK] Correct: Each element is compared with many others inside nested loops, so the total steps add up much more than just once per element.

Interview Connect

Understanding this time complexity helps you explain why some solutions are slower and how to improve them, a skill valued in problem solving.

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 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