Problem 300

(Last updated: )

Question Statement

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

Solution

We approach this problem via dynamic programming. One clue that this problem admits a dp solution is that the longest subsequence (and thus it’s length) in the array is just obtained from slices of that subsequence (increasing their length by 1 each time).

Main idea:

  • Create a new array $\texttt{dp}$ of length equal to that of $\texttt{nums}$, and initialize every entry to $1$
    • The entry $\texttt{dp}[i]$ stores the length of the longest subsequence ending in index $\texttt{i}$
  • Once $\texttt{dp}$ is all filled up with the correct lengths, we return $\texttt{max(dp)}$.
  • We fill up $\texttt{dp}$ as follows:
    • For each $i$, memoize the list $L_i$ of indices $j$ of elements in $\texttt{nums}$ such that $\texttt{nums[j]} < \texttt{nums[i]}$
    • If $L_i$ is empty, then $i$ is the smallest element we’ve encountered thus far.
      • Our initialization $\texttt{dp[i] = 1}$ captures this phenomenon already.
    • Otherwise, set
      $$\texttt{dp[i] = 1 + max(len(LIS ending at index j | j $\in L_i$)) = 1 + max(dp[j] | j in $ \in L_i$)}$$

Here’s an example to illustrate this:

Example:

Suppose $\texttt{nums} = [10,9,2,5,3,7,101,18]$. In this case, $\texttt{dp[0] = dp[1] = dp[2] = 1}$. However at index $3$ we have $\texttt{nums[3] = 5}$ and so $L_3 = [2]$. Thus $\texttt{dp[3] = 2 = 1 + dp[2]}$. Similarly $\texttt{dp[4] = 2 = 1 + dp[2]}$. Now, at index $5$, we have $\texttt{nums[5] = 7}$ and $L_5 = [2,5,3]$. Thus $\texttt{dp[5] = 1 + 2 = 1 + max(dp[2], dp[3], dp[4])}$. And so on…

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def lengthOfLIS(self, nums: List[int]) -> int:
    L = defaultdict(list)
    dp = [1]*len(nums)
    for i in range(1, len(nums)):
        L[i] = [j for j in range(i) if nums[j]< nums[i]]

    for i in range(1, len(nums)):
        if(L[i] == []):
            continue
        else:
            max_ = 0
            for j in L[i]:
                dp[i] = 1 + dp[j]
                if(dp[i] > max_):
                    max_ = dp[i]
            dp[i]=max_
    return max(dp)

Comments:

Time complexity: $\texttt{O(len(nums)}^2)$ (during memoization).

At the time of submission, the above solution passes leetcode submission cases in 1417ms, beats 72.39% of users. It uses 122.6MB of memory, beating 5.04% of users.

Looking through the other solutions, there is also an $\texttt{O(nlog(n))}$ solution using binary search (that uses drastically less memory), that I haven’t quite fully looked into. Perhaps I’ll make an edit to this post at a later time once I understand what’s going on there.