0

Longest Increasing Subsequence

Medium

Keep the smallest possible tail for each achievable length. Binary search replaces the inner loop and drops the cost to n log n.

patience sortingbinary search
TimeO(n log n)
SpaceO(n)
InputComma separated numbers
10
0
9
1
2
2
5
3
3
4
7
5
101
6
18
7

tails[k] will hold the smallest value that can end an increasing run of length k+1.

1 / 10
tails = []
for x in a:
i = first index with tails[i] >= x
if i == tails.length: tails.push(x)
else: tails[i] = x
answer = tails.length
Why it matters

The tails array is not the actual subsequence, only its length is meaningful.

Practise this
Longest Increasing SubsequenceMRussian Doll EnvelopesHLongest Bitonic SubsequenceM
Keyboard
space play← → stepr restartctrl K search

More in Dynamic Programming

Kadane (Maximum Subarray)
O(n)
Memoisation vs Brute Force
O(2^n) naive, O(n) memoised
0/1 Knapsack
O(n * W)
Longest Common Subsequence
O(n * m)
Coin Change
O(coins * amount)
Minimum Path Sum
O(rows * cols)
Edit Distance
O(n * m)
Next visualiser
Minimum Path Sum