Longest Increasing Subsequence (LeetCode #300)
This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Clone Graph.
Introduction
If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Longest Increasing Subsequence problem, you’re in the right spot.
This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.
Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.
Let’s get it started!
Understanding the Problem 🕵🏻♂️
The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):
- We’ll be given a list of
nums numswill have a minimum length of1and a maximum of2500- We should return the length of the longest increasing subsequence (but not necessarily with these numbers being consecutively increasing)
I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.
We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.
Okay. I think that’s enough housekeeping items for us to get started!
Setup 🏗
This problem is a dynamic programming problem! This means that we’ll be using a data structure to dynamically track results and also break down the problem into smaller “sub-problems.”
We’ll be using a list of the same length as nums, and we’ll initialize each index position with 1. You’ll see why shortly, I promise!
For instance, a list of nums of length 6 will produce a tracker list that look like this:
nums = [2, 6, 4, 5, 9, 10]tracker = [1, 1, 1, 1, 1, 1]
We’re using 1 as the initial value since each number marks a longest increasing subsequence of at least 1. In other words, a list of nums = [4] with one value 4 would be correct with an initial value of tracker = [1] since the longest increasing subsequence would be 1. Make sense?
This gives us a dynamic programming list to track our progress and an initial value for each index position.
Now that we have this setup, let’s jump straight into our loops which are the bread and butter for this problem! 🍞
Building Our Loops 🔁
It turns out that the optimal solution for this problem uses two loops.
The first thing we want to do is set up a for loop that iterates over every number in the nums list:
The fact that we’re starting at index 1 here is just because we’ve been asked in this problem to find an increasing subsequence. This means we can skip the first number since we’ll be looking at it in a second in our look-back.
You can’t have an increasing subsequence without numbers beforehand to increase upon, right?
The second thing we want to do is write a second, inner for loop that will iterate from the start of the list all the way up to (but not including) the current index i:
Inside of this inner loop, we want to compare the numbers at nums[j] and nums[i]:
Essentially, we’re updating tracker at position i with whatever the tracker[j] + 1 value is if it’s greater than current tracker[i].
If none of that made sense, just hold on — I’ll walk you through it.
First we start with our nums list and initialize a tracker list:
nums = [1, 10, 5, 2, 7, 8]
tracker = [1, 1, 1, 1, 1, 1]We then start traversing our nums list with our outer loop, starting at index 1:
# We then start traversing our nums list, starting at index 1
nums = [1, 10, 5, 2, 7, 8]
^^We then iterate in our inner loop from 0 up to (but not including) the outer loop index. At each step (which is only once for this iteration), we compare the inner loop index of nums to the outer loop to see if the values are increasing:
nums = [1, 10, 5, 2, 7, 8]
^ ^^They are, so we need to update tracker at the outer loop index (1) to be the value of tracker at the inner loop index (0) + 1:
tracker = [1, 2, 1, 1, 1, 1]
^ ^We will continue walking through the values of nums with our outer and inner loops which will gradually build up an answer of the longest increasing subsequence.
For instance, the next few indices will build up like this:
nums = [1, 10, 5, 2, 7, 8]# Second iteration at index 2, inner loop running up to it
# No updates because the num is not increasing
tracker = [1, 2, 1, 1, 1, 1]
^# Third iteration at index 3, inner loop running up to it
# Update because the num is increasing
tracker = [1, 2, 1, 3, 1, 1]
^
I’d like to challenge you to finish the rest of this on a piece of paper or even on a text file. 💪🏻
See how this progressively builds up an answer for us?
The last thing we need to do is scan through the tracker list and return the maximum value in it. While my example above had the biggest increasing subsequence at the end, that won’t always be the case.
We can easily find our answer like this:
This max(tracker) does exactly what it says on the box; it iterates through the list once and returns the largest value in the list.
This entire solution will run in O(n^2) time in the worst case (as we have a nested loop setup iterating over our loop) and have a space complexity of O(n) (for our tracker list).
Conclusion
Great job! What did you think? I hope you enjoyed this one.
Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.
Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).
Thanks for reading. 🔥
Nathan
(GitHub, LinkedIn, Twitter, and Personal Site)
