300. Longest Increasing Subsequence

Problem¶

Given an array nums, return the length of the longest subsequence whose values are strictly increasing.

Example:

nums = [10,9,2,5,3,7,101,18] -> 4
because one valid subsequence is [2,3,7,101]

Key trick¶

Use a tails array:

tails[k] = smallest possible tail of any increasing subsequence of length k + 1
For each number, replace the first tail >= it using binary search
The size of tails is the answer

This gives \(O(n \log n)\).

Trap¶

Confusing subsequence with subarray
Using <= instead of <, since it must be strictly increasing
Thinking tails stores an actual LIS; it only stores enough information to get the length
Sorting is invalid because it destroys original order

Why is it interesting?¶

It has a clean \(O(n^2)\) DP first solution and a classic \(O(n \log n)\) optimization
It tests whether you can keep order constraints while optimizing with binary search

Python solution¶

import bisect

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        # tails[i] = smallest possible ending value of an
        # increasing subsequence of length i + 1
        tails = []

        for x in nums:
            # Binary search for the first index with tails[idx] >= x
            l, r = 0, len(tails)
            while l < r:
                mid = (l + r) // 2
                if tails[mid] < x:
                    l = mid + 1
                else:
                    r = mid

            # If x is bigger than all tails, extend the longest subsequence.
            if l == len(tails):
                tails.append(x)
            else:
                # Otherwise replace to keep the tail as small as possible.
                tails[l] = x

        return len(tails)

    def lengthOfLIS_2(self, nums: list[int]) -> int:
        tails = []

        for x in nums:
            i = bisect.bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x

        return len(tails)

Comment on my solution¶

Your DP is correct and is the standard \(O(n^2)\) solution:

dp[i] means LIS ending at index i

Transition is:

dp[i] = 1 + max(dp[j]) for all j < i with nums[j] < nums[i]

Good points:

Correct state definition
Correct transition
Correct handling of duplicates via strict <

What to improve:

The "sort the array" idea is a dead end because subsequences must preserve original order
Minor typo: "expand", not "expend"
For the follow-up, replace DP with tails + binary search for \(O(n \log n)\)

Your current complexity:

Time: \(O(n^2)\)
Space: \(O(n)\)

## Solution
# Works - but seems to be in O(n^2)
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        # [10,9,2,5,3,7,101,18] -> 4 (because [2,3,7,101])
        # [0,1,0,3,2,3] -> 4 (because [0,1,2,3])
        # - the follow-up in O(n log(n)) suggest maybe sorting the array???
        #   - But what can we do with the sorted array then?
        # - note that we want the length of such sequence (not the sequence)
        #   - no enumaration
        # - in the example [0,1,0,3,2,3]
        #   - how to count [0,1,2,3] sequence and not the shorter [0,1,3]???
        # - if we sort (and remove duplicate) we can know the upper bound
        #   of such a sequence

        # dp[i] = max length of increasing sequence ending at `i`
        #         (max value of this sequence is nums[i])
        dp = [1] * len(nums)
        best = 1

        for i in range(1,len(nums)):
            for j in range(i):
                # we can expend the sequence by one
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
            best = max(best, dp[i])
        return best

Solution().lengthOfLIS([10,9,2,5,3,7,101,18]) # 4
Solution().lengthOfLIS([0,1,0,3,2,3]) # 4
Solution().lengthOfLIS([7,7,7]) # 1