Longest Increasing Subsequence

LeetCode

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].

Initial attempt

Time spent: 20m | Runtime: 92.95% | Memory: 49.79%

• Failed this one pretty hard - I spent a lot of time initially staring and not having any intuition on how to do it.
• The time spent is misleading since it represents how quickly I gave up.
• Performance is also misleading since it reflects the solution I read.
• I spent a lot of time thinking about keeping track of the actual subsequence. This was not the way.

Solution

In dynamic programming, we're often looking for the relevant details that represent the state of the problem at any given point. Here, we keep an increasing subsequence to track the best we can do at any point.

As a crucial note, the increasing subsequence we keep is not necessarily a valid subsequence of the list. This is similar to Minimum Window Substring where the sliding window is not always valid. That said, based on how we will update this subsequence, the length should accurately reflect the length of the longest valid subsequence. The values in the subsequence should also help us maintain the integrity of the solution.

As you may be able to tell, this can be really unintuitive if you are seeing this for the first time. It definitely was for me.

Cleaned up code

Time spent: 3m | Runtime: 75.69% | Memory: 49.79%

import bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tracker = []
        for num in nums:
            insert = bisect.bisect_left(tracker, num)
            if insert == len(tracker):
                tracker.append(num)
            else:
                tracker[insert] = num
        return len(tracker)

Other notes

• bisect is a cheat code for interviews.