NUHMAN.com

Introduction

LeetCode 300: Longest Increasing Subsequence (LIS) is a problem that requires you to find the length of the longest increasing subsequence (LIS) in an integer array. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

The challenge is to solve the problem efficiently for large input sizes. We need to look for an optimal approach that can solve the problem in O(n log n) time, where n is the length of the input array.

Problem Statement

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

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Example

python

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

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

✅ Step-by-Step Solution

🧠 Intuition

The problem can be solved using two main techniques:

1. Dynamic Programming (DP): We use a dynamic programming approach where we maintain an array dp such that dp[i] stores the length of the longest increasing subsequence that ends at index i.
2. Binary Search (Optimized Approach): We can use binary search to optimize the solution from O(n²) to O(n log n). The idea is to maintain a list that represents the smallest possible last element of an increasing subsequence of each possible length.

✅ Approach

Approach 1: Dynamic Programming (O(n²) Time Complexity)

1. DP Initialization:

• Initialize a dp array where each element is set to 1, representing that the shortest possible subsequence at each index is the number itself.

1. DP State Transition:

• For each element nums[i], we check all previous elements nums[j] where j < i. If nums[i] > nums[j], it means we can extend the subsequence ending at j by adding nums[i] to it. Therefore, we update dp[i] = max(dp[i], dp[j] + 1).

1. Result:

• The length of the longest increasing subsequence is the maximum value in the dp array.

Approach 2: Binary Search (O(n log n) Time Complexity)

1. Use a List for Tracking:

• Maintain a list sub which represents the smallest possible last element of an increasing subsequence of each length. For example, sub[i] holds the smallest possible element that can form a subsequence of length i+1.

1. Binary Search:

• For each element in the input array, use binary search to find the position where it should be placed in the sub list. If the element is greater than the largest element in sub, append it to the list. Otherwise, replace the element in sub that is just larger than the current element.

1. Result:

• The length of the sub list at the end will give the length of the longest increasing subsequence.

✅ Python Code (O(n²) DP Solution)

python

class Solution:
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        
        dp = [1] * len(nums)  # Initialize DP array
        
        # Build the DP array
        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)
        
        # The length of the longest increasing subsequence is the max value in the DP array
        return max(dp)

✅ Python Code (O(n log n) Binary Search Solution)

python

import bisect

class Solution:
    def lengthOfLIS(self, nums):
        sub = []
        
        for num in nums:
            # Use binary search to find the position where `num` should be placed in `sub`
            pos = bisect.bisect_left(sub, num)
            
            # If pos is equal to the length of the sub list, `num` is greater than any element in sub
            if pos == len(sub):
                sub.append(num)
            else:
                # Otherwise, replace the element at `pos` with `num`
                sub[pos] = num
        
        return len(sub)

🧪 How It Works

DP Solution:

• Initialization: The dp array is initialized to 1 for all indices, as each element is its own subsequence of length 1.
• Nested Loops: For each i from 1 to n-1, we compare nums[i] with all previous elements (nums[0] to nums[i-1]). If nums[i] > nums[j], we update dp[i] to reflect the longest subsequence that can end at index i.
• Final Result: After the loops, the longest subsequence will be the maximum value in the dp array.

Binary Search Solution:

• List Maintenance: We use a list sub to maintain the smallest possible last elements of increasing subsequences of each possible length.
• Binary Search: For each number in nums, we use bisect_left to find the index where the number should be placed in the sub list. If the number is larger than all elements in sub, we append it to the end. If not, we replace the element in sub at the found index.
• Result: The length of the sub list gives the length of the longest increasing subsequence.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n²) for DP, O(n log n) for Binary SearchSpace ComplexityO(n)

• Time Complexity (DP): The DP approach uses a nested loop, where the outer loop runs n times, and the inner loop runs up to n times, leading to a time complexity of O(n²).
• Time Complexity (Binary Search): The binary search approach uses a single loop through the array, with each insertion operation requiring O(log n) time due to binary search, resulting in a total time complexity of O(n log n).
• Space Complexity: Both approaches use O(n) space due to the additional array (dp or sub) to store the results.

🔍 Edge Cases

1. Empty Array:

• If nums is an empty array, the length of the longest increasing subsequence is 0.

1. Array with One Element:

• If the array contains only one element, the longest increasing subsequence is 1.

1. Array with All Elements the Same:

• If all elements in the array are the same, the longest increasing subsequence is 1, as no elements are strictly greater than the others.

1. Array with Already Increasing Elements:

• If the array is already sorted in increasing order, the longest increasing subsequence is the entire array.

1. Array with Decreasing Elements:

• If the array is sorted in decreasing order, the longest increasing subsequence is 1.

✅ Conclusion

LeetCode 300: Longest Increasing Subsequence is a classic dynamic programming problem that challenges us to find the length of the longest strictly increasing subsequence in an array.

• The dynamic programming solution provides a clear and straightforward O(n²) approach.
• The binary search solution optimizes the problem to O(n log n) by using a list to store the smallest possible elements of increasing subsequences, and applying binary search to maintain this list efficiently.

By using one of these solutions, you can solve the problem in an optimal way depending on your performance needs.