{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Longest Increasing Subsequence – Solution & Complexity

Interview solutions
/
Longest Increasing Subsequence

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • A subsequence keeps the original order but may skip elements.
    • We want the longest run of values that strictly increase from left to right.
    • We only need the length, not the actual subsequence.

  2. Step 2: Simple O(n^2) DP

    • Let dp[i] be the length of the longest increasing subsequence that ends at index i.
    • For each i, look back at every j < i; if nums[j] < nums[i], we can extend that subsequence.
    • The answer is the maximum value in dp.
    def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

  3. Step 3: Optimizing with Patience Sorting

    • Keep a list sub where sub[k] is the smallest possible tail of an increasing subsequence of length k + 1.
    • For each number, binary search for the first tail >= it.
    • Replacing that tail keeps sub sorted and as small as possible, leaving room to grow.
    import bisect

def length_of_lis(nums):
    sub = []
    for x in nums:
        i = bisect.bisect_left(sub, x)
        if i == len(sub):
            sub.append(x)   # x extends the longest subsequence
        else:
            sub[i] = x      # x replaces a larger tail
    return len(sub)

  4. Step 4: Why It Works

    • sub is never the real subsequence, but its length always equals the LIS length so far.
    • Using bisect_left enforces strictly increasing values (equal numbers overwrite rather than extend).
    • That is why [7,7,7,...] correctly returns 1.

  5. Step 5: Complexity

    • Time: O(n log n) thanks to the binary search per element.
    • Space: O(n) for the sub array in the worst case.

FAQ

See also

Practice Longest Increasing Subsequence online (run code in the browser)Best Time to Buy and Sell Stock solution (easy)Binary Search solution (easy)Coin Change solution (medium)Find Minimum in Rotated Sorted Array solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?