Longest Increasing Subsequence in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the dp array with 1s for each element.

DSA Python

dp = [[1]] * len(nums)

Drag options to blanks, or click blank then click option'

ANone

B0

Clen(nums)

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp with 0 instead of 1

Using length of nums as initial value

Using None which causes errors

Each element starts with a subsequence length of 1 (the element itself).

2fill in blank

medium

Complete the code to check if the current element can extend the subsequence ending at j.

DSA Python

if nums[i] [1] nums[j]:

Drag options to blanks, or click blank then click option'

A>

B==

C<

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= or < which allows non-increasing sequences

Using == which doesn't extend the subsequence

We want to extend the subsequence only if current element is greater than previous.

3fill in blank

hard

Fix the error in updating dp[i] to the maximum subsequence length.

DSA Python

dp[i] = max(dp[i], dp[[1]] + 1)

Drag options to blanks, or click blank then click option'

Ai

Bj

C0

Dlen(nums)

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[i] + 1 which causes incorrect increments

Using dp[0] or dp[len(nums)] which are invalid indices

We compare dp[i] with dp[j] + 1 because we extend the subsequence ending at j.

4fill in blank

hard

Fill both blanks to complete the nested loops for LIS calculation.

DSA Python

for [1] in range(1, len(nums)):
    for [2] in range([1]):

Drag options to blanks, or click blank then click option'

Ai

Bj

Ck

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using same variable for both loops

Starting outer loop from 0 instead of 1

Outer loop uses i from 1 to end, inner loop uses j from 0 to i-1 to compare elements.

5fill in blank

hard

Fill both blanks to return the length of the longest increasing subsequence.

DSA Python

return max(dp) if nums [1] [] else [2]

Drag options to blanks, or click blank then click option'

A==

B0

C!=

Dlen(nums)

Attempts:

3 left

💡 Hint

Common Mistakes

Using == instead of != causing wrong condition

Returning len(nums) instead of 0 for empty list

Return max(dp) if nums is not empty, else return 0 for empty input.

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