Longest Increasing Subsequence – LeetCode 300

The Longest Increasing Subsequence (LIS) is a popular problem often encountered in coding interviews and algorithm challenges. In this blog, we will break down how to approach this problem, implement a solution using Dynamic Programming, and test our code with various test cases to ensure its correctness.

Problem Understanding

The problem statement on LeetCode reads as follows:

Given an integer array nums, return the length of the longest strictly increasing subsequence.

What is a subsequence? A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

For example, [3, 6, 2, 7] is a subsequence of the array [0, 3, 1, 6, 2, 2, 7].

Example:

Input:

codenums = [10, 9, 2, 5, 3, 7, 101, 18]

Explanation: The longest increasing subsequence is [2, 3, 7, 101]. Therefore, the length is 4.

Example:

Input:

codenums = [0, 1, 0, 3, 2, 3]

Explanation: The longest increasing subsequence is [0, 1, 3, 5], and its length is also 4.

Plan

To solve this problem, we can use Dynamic Programming (DP). The idea is to build a table dp where dp[i] represents the length of the longest increasing subsequence that ends at index i of the input array.

We can follow these steps:

• Edge Case: If the input array is empty, return 0 because there’s no subsequence.
• Initialization: Initialize the dp array with 1 for each element. The reason for starting with 1 is that each element, by itself, is a subsequence of length 1.
• Nested Loops: For each element nums[i], we will check all previous elements nums[j] (where j < i) and if nums[i] > nums[j], we will update dp[i] to be the maximum of dp[i] or dp[j] + 1. This checks if including nums[i] extends any increasing subsequence ending at nums[j].
• Result: The length of the longest increasing subsequence will be the maximum value in the dp array.

Algorithm

• Time Complexity: O(n²) because we have two nested loops: one iterating through each element and another iterating through all previous elements.
• Space Complexity: O(n) for the dp array.

Code Implementation

Now, let’s implement the solution in Python.

codeclass Solution:
    def lengthOfLIS(self, nums):
        # Edge case: if the array is empty, return 0
        if not nums:
            return 0

        # Initialize the dp table with all 1s (each element is a subsequence of length 1 by itself)
        dp = [1] * len(nums)

        # Iterate through the array from index 1 to n-1
        for i in range(1, len(nums)):
            # Iterate through all previous elements
            for j in range(i):
                # If current element nums[i] is greater than nums[j], it can extend the subsequence
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        # Return the maximum value in the dp table, which is the length of the longest increasing subsequence
        return max(dp)

Explanation of the Code

• Edge Case Handling:
  • If the input array nums is empty, we return 0 because no subsequence exists.
• Dynamic Programming Table (dp):
  • We initialize an array dp where each entry is set to 1, meaning each element is an increasing subsequence by itself.
• Main Logic:
  • We loop through each element in the array (i from 1 to n-1).
  • For each element, we check all previous elements (j from 0 to i-1).
  • If nums[i] > nums[j], it means nums[i] can be added to the subsequence ending at nums[j]. We then update dp[i] with max(dp[i], dp[j] + 1), which ensures we store the maximum possible subsequence length at each index.
• Result:
  • After the loop completes, we return the maximum value from the dp array, which represents the length of the longest increasing subsequence in the entire array.

Testing the Solution

Testing is an essential part of any software development process. Let’s test our solution with several cases to ensure it works as expected.

General Test Case

codenums = [10, 9, 2, 5, 3, 7, 101, 18]
print(Solution().lengthOfLIS(nums))  # Output: 4

Explanation: The longest increasing subsequence is [2, 3, 7, 101], so the output is 4.

Increasing Order

codenums = [1, 2, 3, 4, 5]
print(Solution().lengthOfLIS(nums))  # Output: 5

Explanation: Since the entire array is already strictly increasing, the longest subsequence is the array itself, and the output is 5.

Decreasing Order

 codenums = [5, 4, 3, 2, 1]
print(Solution().lengthOfLIS(nums))  # Output: 1

Explanation: In this case, no element can form a strictly increasing subsequence, so the longest subsequence has a length of 1.

Array with Repeated Elements

codenums = [0, 1, 0, 3, 2, 3]
print(Solution().lengthOfLIS(nums))  # Output: 4

Explanation: The longest increasing subsequence is [0, 1, 3, 5], and its length is 4.

Edge Case – Empty Array

codenums = []
print(Solution().lengthOfLIS(nums))  # Output: 0

Explanation: An empty array doesn’t have any subsequences, so the output is 0.

Conclusion

The Longest Increasing Subsequence (LIS) problem is a classic problem that can be efficiently solved using Dynamic Programming. By carefully updating the dp array and iterating over previous elements, we can determine the length of the longest subsequence in O(n²) time.

We’ve implemented the solution in Python, tested it with several edge cases, and confirmed that the solution is correct for various input scenarios.