We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Increasing Subsequence

Difficulty: Medium

Problem Description

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

Key Insights

  • A subsequence is derived from another sequence by deleting some elements without changing the order of the remaining elements.
  • The problem can be solved using dynamic programming or a combination of dynamic programming and binary search for improved efficiency.
  • The use of a helper array (or list) to store the smallest tail of all increasing subsequences found can help in determining the length of the longest increasing subsequence.

Space and Time Complexity

Time Complexity: O(n log(n))
Space Complexity: O(n) or O(1) depending on the method used.

Solution

To solve the problem, we can utilize a dynamic programming approach combined with binary search to maintain an array that keeps track of the smallest possible tail value for all increasing subsequences of various lengths.

  1. Initialize an empty list tails where each index represents the smallest tail of increasing subsequences.
  2. Iterate through each number in the input list nums.
  3. For each number, use binary search to determine its position in tails. If it can extend the longest subsequence, append it; otherwise, replace the existing value to maintain the minimum tail.
  4. The length of the tails list will give us the length of the longest increasing subsequence.

Code Solutions

def lengthOfLIS(nums):
    from bisect import bisect_left
    tails = []
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)
← Back to All Questions