Longest Increasing Subsequence [Solution]

Solution 1 (Simpler)

The problem of finding the length of the Longest Increasing Subsequence (LIS) can be solved using dynamic programming. Here’s a Python implementation:

from typing import List

def length_of_lis(nums: List[int]) -> int:
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n  # Initialize dp array with all values set to 1
                  # because each element is a valid subsequence of length 1

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                # we can extend the LIS ending at index j by including the
                # element at index i
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# Example usage:
nums = [0, 1, 2, 3]
print(length_of_lis(nums))  # Output: 4

nums = [0, 1, 3, 10, 2, 3, 4]
print(length_of_lis(nums))  # Output: 5

nums = [10, 9, 2, 5, 3, 7, 101, 18, 105]
print(length_of_lis(nums))  # Output: 5

This solution uses dynamic programming to build an array dp where dp[i] represents the length of the LIS ending at index i. The time complexity of this solution is O(n^2), where n is the length of the input array nums. The space complexity is O(n) for the dp array.

Let’s break down the key components contributing to the time complexity:

Initialization of dp array: O(n)
- The initialization of the dp array takes linear time, as each element of the array is set to 1 initially.
Nested Loops: O(n^2)
- The outer loop runs n times, iterating over each element in the nums array.
- The inner loop runs in a nested manner, going from the beginning of the array up to the current outer loop index.
- Both loops contribute to a quadratic time complexity of O(n^2).
Updating dp array: O(1) per iteration
- Inside the inner loop, each iteration involves a constant-time update of the dp array, as it simply compares and updates the value at the current index.
Overall Time Complexity: O(n) + O(n^2) = O(n^2)
- The dominant factor in the time complexity is the nested loop, resulting in a final time complexity of O(n^2).

It’s important to note that there exists a more efficient algorithm for solving the LIS problem with a time complexity of O(n log n) using dynamic programming and binary search (see below). The quadratic solution provided above is a simple and intuitive approach but may not be optimal for very large input sizes.

Solution 2 (More Efficient)

The Longest Increasing Subsequence (LIS) problem can be solved more efficiently using a dynamic programming approach with a time complexity of O(n log n). This improved solution uses a binary search to find the position where the current element should be inserted in the temporary lis array. Here’s the optimized Python implementation:

from typing import List

def length_of_lis(nums: List[int]) -> int:
    # Check if the input array is empty
    if not nums:
        return 0

    # Initialize the temporary LIS array with the first element of nums
    lis = [nums[0]]

    # Iterate over the remaining elements in nums
    for num in nums[1:]:
        # If num is greater than the last element in lis, append it to lis
        if num > lis[-1]:
            lis.append(num)
        else:
            # Perform binary search to find the correct position for num in lis
            left, right = 0, len(lis) - 1
            while left < right:
                mid = (left + right) // 2
                if lis[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            # Update lis by replacing the element at position left with num
            lis[left] = num

    # The length of lis represents the length of the longest increasing subsequence
    return len(lis)

# Example usage:
nums = [0, 1, 2, 3]
print(length_of_lis(nums))  # Output: 4

nums = [0, 1, 3, 10, 2, 3, 4]
print(length_of_lis(nums))  # Output: 5

nums = [10, 9, 2, 5, 3, 7, 101, 18, 105]
print(length_of_lis(nums))  # Output: 5

Time Complexity

The time complexity of the optimized solution for the Longest Increasing Subsequence (LIS) problem is O(n log n), where n is the length of the input array nums. Let’s break down the time complexity:

Outer Loop:
- The outer loop iterates through each element in the input array nums exactly once.
- Therefore, the time complexity of the outer loop is O(n).
Binary Search:
- The binary search is performed for each element num in the input array.
- The time complexity of each binary search operation is O(log n).
- Since the binary search is performed for all n elements, the total time complexity of binary searches is O(n log n).
Overall Time Complexity:
- The dominant factor in the overall time complexity is the O(n log n) from the binary searches.
- Therefore, the overall time complexity is O(n log n).

The reason for this improved time complexity is that the algorithm uses a binary search to efficiently find the correct position for each element in the lis array. This reduces the overall time complexity compared to the O(n^2) time complexity of the naive dynamic programming approach.

Space Complexity

The space complexity of the optimized solution is O(n), where n is the length of the input array nums. Let’s analyze the space complexity:

lis Array:
- The primary data structure used in this solution is the lis array, which stores the current increasing subsequence.
- In the worst case, the length of lis can be equal to the length of the input array nums (n).
- Therefore, the space complexity for the lis array is O(n).
Additional Variables:
- The solution uses a few additional variables such as left, right, mid, and num.
- These variables occupy constant space and do not depend on the size of the input array.
- Therefore, the space complexity for these variables is O(1).
Overall Space Complexity:
- The dominant factor in the overall space complexity is the space required for the lis array, which is O(n).
- The additional variables contribute only constant space.
- Therefore, the overall space complexity is O(n).

The space complexity is linear in the size of the input array due to the space used to store the increasing subsequence (lis).