algoadvance

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

A subsequence is a sequence that can be derived from an 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 1:

Input: nums = [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.

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

Strategy

1. Dynamic Programming Approach:
   • Use a DP array dp where dp[i] represents the length of the longest increasing subsequence ending at index i.
   • Initialize each value in dp to 1 since the minimum length of an increasing subsequence including any element is 1 (the element itself).
   • For each element i in the array, iterate through all previous elements j (0 to i-1):
     • If nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1).
   • The length of the longest increasing subsequence will be the maximum value in the dp array.
2. Binary Search Optimization:
   • Maintain an array lis which will store the smallest tail of all increasing subsequences of various lengths.
   • Iterate through the array nums, and for each element num, use binary search to determine its position in lis.
   • If num is greater than the largest element in lis, append it to lis.
   • Otherwise, replace the element in lis that is just bigger than num with num.
   • The length of lis at the end will be the length of the longest increasing subsequence.

Time Complexity

• Dynamic Programming Approach: O(n^2)
• Binary Search Optimization: O(n log n)

We will use the Binary Search Optimization approach for better performance.

Code

def lengthOfLIS(nums):
    if not nums:
        return 0
    
    lis = []
    
    for num in nums:
        pos = binarySearch(lis, num)
        if pos == len(lis):
            lis.append(num)
        else:
            lis[pos] = num
            
    return len(lis)

def binarySearch(lis, num):
    left, right = 0, len(lis)
    while left < right:
        mid = (left + right) // 2
        if lis[mid] < num:
            left = mid + 1
        else:
            right = mid
    return left

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

Explanation

• Initialization: Initialize an empty list lis.
• Iterate through nums: For each number in nums:
  • Use binarySearch to find its placement in lis.
  • If it should be added to the end, append it.
  • Otherwise, replace the element at the found position with this number.
• Return the length of lis: This length represents the length of the longest increasing subsequence.

This approach ensures an efficient time complexity of O(n log n) due to the binary search within the loop.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?