Longest Increasing Subsequence Leetcode Problem 300 [Python Solution]

To solve the Longest Increasing Subsequence Leetcode problem today, we be understanding the problem and its constraints in-depth.

Then, provide both a brute-force approach and an efficient dynamic programming solution in Python.

Problem Overview

The problem statement goes as follows: Given an integer array nums, you need to return the length of the longest strictly increasing subsequence.

In simpler terms, you’re given an array of numbers, and you need to find the length of the longest subsequence where the numbers are in ascending order, but not necessarily adjacent in the array.

Here’s an example to illustrate the problem:

Example 1:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], making its length 4.

Example 2:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

Example 3:

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Now that we understand the problem, let’s dive into the solution.

Understanding the Constraints

Before we explore the solution, it’s essential to understand the constraints given in the problem.

These constraints help us choose the appropriate algorithm and data structures for our solution.

The length of the input array nums can vary, but it’s limited to a reasonable range (between 1 and 2500 elements).

This tells us that we need an efficient solution, as brute force or exponential time complexity won’t work for large inputs.

The values in the nums array can be both positive and negative, ranging from -104 to 104. While these values aren’t exceptionally large, we should consider them when designing our solution.
The problem requires us to find the length of the longest increasing subsequence.

This means we’re interested in the result, not the specific subsequence itself.

Therefore, we don’t need to keep track of the actual subsequence elements; we need to find its length efficiently.

With these constraints in mind, let’s explore different approaches to solving this problem.

Longest Increasing Subsequence LeetCode Problem Solution

Bruteforce Approach

The most straightforward way to approach this problem is through a brute-force approach.

We can use a depth-first search (DFS) strategy to explore all possible subsequences and find the longest increasing one.

However, keep in mind that this approach is not efficient, especially for larger input arrays.

Here’s how the brute-force approach works:

Start at the first element in the array and consider it as the beginning of our subsequence.
For the current element, we have two choices: either include it in our subsequence or skip it.
Recursively explore both choices for the next elements.
Keep track of the length of the increasing subsequence in each branch of recursion.
Return the maximum length obtained among all possible subsequences.

The time complexity of this brute-force approach is exponential, O(2^n), where n is the length of the input array.

This is because, for each element in the array, we have two choices (include or skip), and we explore all possible combinations.

Efficient Approach with Dynamic Programming

The dynamic programming approach is a significant improvement over the brute-force method.

It allows us to avoid redundant calculations and find the solution with a much more efficient time complexity, O(n^2).

The idea behind dynamic programming is to store the length of the longest increasing subsequence for each element in the input array.

We iteratively build upon this information while considering the elements that come after the current element.

Let’s go through the dynamic programming solution step by step:

Initialize a list called lis of the same length as the input array nums.

Each element in lis represents the length of the longest increasing subsequence that ends with the corresponding element in nums.

Initially, set all elements in lis to 1 because a single element is considered a valid subsequence of length 1.

Start iterating through the elements of nums in reverse order.

We go in reverse to make sure we calculate the length of increasing subsequences for each element while considering only the elements that come after it.

For each element at index i, iterate through all elements that come after it (with an index j greater than i).
Check if nums[i] < nums[j], meaning that the element at index j is greater than the element at index i.

If this condition is met, it indicates a potential extension of the increasing subsequence.

If the condition is true, update the lis[i] with the maximum between its current value and lis[j] + 1.

This means we’re considering adding the current element (nums[i]) to an existing increasing subsequence that ends with nums[j].

Continue this process for all elements in nums, considering only elements that come after the current element.
Finally, return the maximum value in the lis list, which represents the length of the longest increasing subsequence.

Here’s the Python code that implements this efficient dynamic programming solution:

View on GitHub ➹

def lengthOfLIS(self, nums: List[int]) -> int:
        # Initialize a list to store the length of LIS for each element in nums
        lis = [1] * len(nums)

        # Iterate through the elements in reverse order
        for i in range(len(nums) - 1, -1, -1):
            # Iterate through elements that come after the current element
            for j in range(i + 1, len(nums)):
                if nums[i] &lt; nums[j]:
                    # Update the lis for the current element
                    lis[i] = max(lis[i], 1 + lis[j])

        # Return the maximum value in lis, which represents the length of the longest increasing subsequence
        return max(lis)

This dynamic programming approach has a time complexity of O(n^2) because we iterate through the elements in the input array twice: once for each element and once for each possible element that comes after it.

The result is an efficient solution that can handle the given constraints.

Time and Space Complexity

Now, let’s analyze the time and space complexity of our efficient dynamic programming solution:

Time Complexity:

Iterating through the elements in the input array once takes O(n) time.
For each element, we iterate through all elements that come after it, which results in another O(n) time.
Therefore, the overall time complexity is O(n^2).

Space Complexity:

We use an additional list lis of the same length as the input array to store the length of the longest increasing subsequence for each element.

Hence, the space complexity is O(n).

This dynamic programming solution provides a time complexity of O(n^2), making it efficient for the given

constraints.

Reasoning Behind Our Approach

The dynamic programming solution is based on the concept of optimal substructure.

It breaks down the problem into smaller subproblems and builds the solution incrementally by considering each element in the input array while taking into account the elements that come after it.

By iteratively calculating the length of the longest increasing subsequence for each element, we avoid redundant calculations and optimize the overall solution.

The use of dynamic programming and the storage of intermediate results in the lis list allow us to find the maximum length efficiently.

Conclusion

In this post, we’ve tackled the Longest Increasing Subsequence problem (LeetCode Problem 300) and provided both a brute-force approach and an efficient dynamic programming solution in Python.

Understanding the problem constraints is crucial in choosing the appropriate algorithm.

The dynamic programming solution offers an efficient way to find the length of the longest increasing subsequence with a time complexity of O(n^2).

It optimizes the solution by avoiding redundant calculations and is suitable for larger input arrays.

I hope this guide has been helpful in understanding the problem and its solutions.

If you have any questions, suggestions, or would like to discuss this further, please feel free to comment.

Happy coding!

Link to the LeetCode Problem