Longest Increasing Subsequence in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LIS length calculation

What is the output of the following code that calculates the length of the longest increasing subsequence?

DSA Python

def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))

A 3

B 4

C 5

D 6

💡 Hint

Trace the dp array updates for each element.

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

❓ Predict Output

intermediate

Output of LIS reconstruction

What is the printed output of this code that reconstructs one longest increasing subsequence?

DSA Python

def lis_sequence(nums):
    if not nums:
        return []
    dp = [1] * len(nums)
    prev = [-1] * len(nums)
    max_len = 1
    max_index = 0
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
        if dp[i] > max_len:
            max_len = dp[i]
            max_index = i
    lis = []
    while max_index != -1:
        lis.append(nums[max_index])
        max_index = prev[max_index]
    return lis[::-1]

print(lis_sequence([0, 8, 4, 12, 2, 10, 6, 14, 1, 9]))

A [0, 2, 6, 9]

B [0, 4, 6, 9]

C [0, 4, 10, 14]

D [0, 8, 12, 14]

💡 Hint

Follow the prev array to reconstruct the LIS.

The longest increasing subsequence found is [0, 8, 12, 14].

🔧 Debug

advanced

Identify the error in LIS length code

What error does this code raise when run?

DSA Python

def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(length_of_lis([]))

A ValueError: max() arg is an empty sequence

B IndexError: list index out of range

C TypeError: 'int' object is not iterable

D No error, output is 0

💡 Hint

What happens when max() is called on an empty list?

When nums is empty, dp is empty, so max(dp) raises ValueError because max() cannot operate on an empty sequence.

🧠 Conceptual

advanced

Time complexity of LIS dynamic programming

What is the time complexity of the classic dynamic programming solution for the longest increasing subsequence problem shown below?

DSA Python

def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

💡 Hint

Count the nested loops and their ranges.

The solution uses two nested loops each up to n, so time complexity is O(n^2).

🚀 Application

expert

Longest Increasing Subsequence length with binary search optimization

What is the output of this optimized LIS length code using binary search?

DSA Python

import bisect

def length_of_lis(nums):
    sub = []
    for x in nums:
        i = bisect.bisect_left(sub, x)
        if i == len(sub):
            sub.append(x)
        else:
            sub[i] = x
    return len(sub)

print(length_of_lis([3, 5, 7, 1, 2, 8]))

A 4

B 3

C 6

D 5

💡 Hint

Track how the sub list changes with each element.

The longest increasing subsequence length is 4, for example [3,5,7,8].

Practice

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

easy

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

B. The longest subsequence where each number is equal to the previous one

C. The longest subsequence where numbers are in any order

D. The longest subsequence where each number is strictly greater than the previous one

Solution

1. Step 1: Understand the definition of LIS

   The LIS is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with the definition

   Only The longest subsequence where each number is strictly greater than the previous one matches the definition of LIS.

3. Final Answer:

   The longest subsequence where each number is strictly greater than the previous one -> Option D

4. Quick Check:

   LIS = strictly increasing subsequence [OK]

Hint: LIS means strictly increasing sequence, not equal or decreasing [OK]

Common Mistakes:

• Confusing LIS with longest equal subsequence
• Thinking LIS allows decreasing numbers
• Assuming LIS means any order

2. Which of the following Python code snippets correctly initializes a list dp to store LIS lengths for each element in nums of length n?

easy

A. dp = [0] * n

B. dp = [1] * n

C. dp = [None] * n

D. dp = []

Solution

1. Step 1: Understand LIS dp initialization

   Each element alone is a subsequence of length 1, so dp should start with 1s.

2. Step 2: Check options for correct initialization

   Only dp = [1] * n initializes dp with 1s for all elements.

3. Final Answer:

   dp = [1] * n -> Option B

4. Quick Check:

   dp initialized with 1 for LIS length [OK]

Hint: Start dp with 1s because each element is LIS of length 1 [OK]

Common Mistakes:

• Initializing dp with zeros instead of ones
• Using None which causes errors in comparisons
• Leaving dp empty

3. What is the output of the following code snippet?

nums = [10, 9, 2, 5, 3, 7, 101, 18]
dp = [1] * len(nums)
for i in range(len(nums)):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

medium

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Trace dp updates for each element

   Starting dp = [1,1,1,1,1,1,1,1]. Update dp as we find increasing subsequences:
   - i=1: nums[1]=9 < 10? Yes, dp[1]=max(1, dp[0]+1)=2.
   - i=2: nums[2]=2 < 10,9? No update.
   - i=3: nums[3]=5 > 2, dp[3]=max(1, dp[2]+1)=2.
   - i=4: nums[4]=3 > 2, dp[4]=2.
   - i=5: nums[5]=7 > 5,3,2, dp[5]=max(1, dp[3]+1=3, dp[4]+1=3)=3.
   - i=6: nums[6]=101 > all previous, dp[6]=max(1, dp[5]+1=4, dp[1]+1=3, dp[0]+1=2, dp[3]+1=3, dp[4]+1=3) = 5.
   - i=7: nums[7]=18 > 7, dp[7]=max(1, dp[5]+1=4, dp[3]+1=3, dp[4]+1=3) = 4.

2. Step 2: Find max dp value

   Maximum dp value is 5, which is the length of LIS.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Longest Increasing Subsequence length = 5 [OK]

Hint: Use nested loops to update dp with max LIS length [OK]

Common Mistakes:

• Forgetting to update dp[i] with max value
• Mixing up indices i and j
• Printing dp instead of max(dp)

4. The following code is intended to find the length of the LIS but has a bug. What is the bug?

def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

medium

A. dp[j] should be updated as dp[i], not dp[j]

B. The comparison should be nums[j] > nums[i]

C. dp[i] should be updated, not dp[j]

D. The function should return min(dp) instead of max(dp)

Solution

1. Step 1: Identify which dp index to update

   In LIS, dp[i] stores the length of LIS ending at index i. So dp[i] must be updated when nums[i] > nums[j].

2. Step 2: Check the code's update statement

   The code updates dp[j], which is incorrect. It should update dp[i].

3. Final Answer:

   dp[i] should be updated, not dp[j] -> Option C

4. Quick Check:

   Update dp[i] for LIS ending at i [OK]

Hint: Update dp at current index i, not previous j [OK]

Common Mistakes:

• Updating dp[j] instead of dp[i]
• Reversing comparison operators
• Returning min(dp) instead of max(dp)

5. Given the list nums = [3, 10, 2, 1, 20], which of the following is the correct longest increasing subsequence using a binary search optimization approach?

hard

A. [3, 10, 20]

B. [2, 10, 20]

C. [1, 2, 20]

D. [3, 10, 1, 20]

Solution

1. Step 1: Understand binary search LIS approach

   This method builds a list 'tails' where each element is the smallest possible tail of an increasing subsequence of given length.

2. Step 2: Trace the tails list for nums

   Start with empty tails:
   - 3: tails = [3]
   - 10: tails = [3, 10]
   - 2: replace 3 with 2, tails = [2, 10]
   - 1: replace 2 with 1, tails = [1, 10]
   - 20: tails = [1, 10, 20]
   The LIS length is 3, and one valid LIS is [3, 10, 20].

3. Final Answer:

   [3, 10, 20] -> Option A

4. Quick Check:

   Binary search LIS = [3, 10, 20] [OK]

Hint: Binary search builds tails array for LIS length [OK]

Common Mistakes:

• Confusing tails with actual subsequence
• Replacing wrong elements in tails
• Choosing subsequence with wrong order