Longest Increasing Subsequence
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return the length of the longest strictly increasing subsequence (not necessarily contiguous).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Why is it good to end a run of length 3 with a smaller number rather than a bigger one?
- Hint 2A sorted list of tails lets you binary-search where a new number belongs.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
People of different heights join a queue one by one, and you want the longest group that could stand in strictly increasing height order. Keep a row of "slots": slot k holds the shortest person who can end a rising line of k + 1 people. A new person replaces the first slot whose person is as tall or taller (a shorter end is better), or goes to the end if taller than all. The number of slots used is the answer.
- The obvious way
DP: for each number, longest run ending there by scanning all earlier smaller numbers: O(n²).
- The key insight
Keep a list tails (always increasing). For each number find the first place in tails holding a value >= the number (binary search). If there is none, append it (the longest run grew). Otherwise replace that value with the number (same length, smaller ending). The answer is the length of tails.
- The algorithm
- tails = [].
- For each number, binary-search the first tail >= number.
- None: append. Else replace that tail with the number.
- Return len(tails).
Watch it run
Examplenums = [10, 9, 2, 5, 3, 7, 101, 18]
10 starts a run. 9 replaces 10 (a smaller end is better). 2 replaces 9.
tails: 2
Where people slip
- The tails list is NOT the subsequence itself, only its length is right.
- Use bisect_left (first >= number) for strictly increasing; equal numbers must replace, not append.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
import bisect
def length_of_lis(nums):
tails = [] # tails[k] = smallest end of a rising run of length k + 1
for number in nums:
place = bisect.bisect_left(tails, number) # first tail that is >= number
if place == len(tails):
tails.append(number) # the longest run just got longer
else:
tails[place] = number # same length, smaller ending
return len(tails)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.