Longest Increasing Subsequence in DSA Python - 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 bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the length of the longest increasing subsequence in a list of numbers using dynamic programming.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where for each element, we check all previous elements.
• How many times: Outer loop runs n times, inner loop runs up to i times, so roughly n x n = n² times.

How Execution Grows With Input

As the list size grows, the number of comparisons grows roughly with the square of the size.

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

Pattern observation: Doubling the input size roughly quadruples the work needed.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the input size, so bigger lists take much more time.

Common Mistake

[X] Wrong: "The algorithm runs in linear time because it just loops through the list once."

[OK] Correct: There is a nested loop inside the first loop, so for each element, it checks many previous elements, making it slower than just one loop.

Interview Connect

Understanding this time complexity helps you explain why some solutions are slower and shows your skill in analyzing nested loops, a common interview topic.

Self-Check

"What if we used a binary search approach to build the subsequence? 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 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