300. Longest Increasing Subsequence

300

MediumOne-Dimensional Dynamic ProgrammingGreedy with binary searchPatience sorting (tails array)

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may drop elements; it need not be contiguous.

Open official problem prompt ↗

In plain English

Determine how long the longest run of values can be if we read left to right and only keep values that keep strictly rising.

Picture it like this

Dealing cards into piles in the patience card game: each new card goes on the leftmost pile whose top is not smaller, and the number of piles equals the longest increasing subsequence.

Example

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Why: The subsequence [2, 3, 7, 101] (or [2, 3, 7, 18]) is strictly increasing and has length 4.

Constraints

1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4

Pattern lesson

See the pattern, then code

Patience sorting (tails array)

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. Maintain the smallest possible tail value for an increasing subsequence of each length; a smaller tail leaves more room to extend later.

New words, made simpleKnow these before the algorithm

Subsequence: Elements picked in original order, gaps allowed.
tails array: tails[k] = smallest possible tail value of an increasing subsequence of length k+1.
bisect_left: Binary search for the leftmost position where x could be inserted to keep the list sorted.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

O(n^2) DP

Correct and intuitive but slower; fine for n<=2500 yet not the target technique.

dp[i] = 1 + max dp[j] for j<i with nums[j]<nums[i].

Time O(n^2)Space O(n)

Best choicePatience sorting + binary search

Optimal time; the length of tails is the answer.

Maintain tails and binary-search each element's slot.

Time O(n log n)Space O(n)

The rule we keep true

Invariant

tails is always sorted ascending, and tails[k] is the minimum tail achievable by any strictly increasing subsequence of length k+1 seen so far.

Why this is correct

Reasoning

Replacing the first tail >= x with x never shortens any subsequence (the length that tail represented is preserved) but lowers its tail, which can only help future extensions. Appending x happens exactly when x exceeds every tail, growing the longest run by one. So len(tails) tracks the true LIS length.

The algorithm in three movesSay these aloud before coding

1Keep a list tails where tails[k] is the smallest tail of an increasing subsequence of length k+1

after 5: tails=[2,5]

2For each x, binary-search the first tail >= x

after 3: tails=[2,3]

3If none exists, append x (extends the longest run); otherwise overwrite that tail with x

after 7,101: tails=[2,3,7,101] -> len 4

4The length of tails is the answer

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

100

1016

187

1 · Read10 then 9

2 · AskWhere does each go?

3 · Update statetails=[9]

4 · Result10 starts a pile; 9 overwrites it (smaller tail).

Key takeaway

Highlighted indices form one optimal increasing subsequence [2,3,7,101].

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Setup
tails starts empty; its final length will be the LIS length.
2
Lines 5-6Locate the slot
bisect_left finds the first tail not less than x, the pile x belongs on.
3
Lines 7-11Append or replace
If x is larger than every tail we grow the sequence; otherwise we lower an existing tail to keep it minimal.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Strictly decreasing input returns 1
Already sorted input returns n
Single element returns 1
Duplicates: strictly increasing means equal values do not extend, and bisect_left overwrites the equal tail

Common beginner mistakes

Using bisect_right, which would allow equal values and compute the longest non-decreasing subsequence instead of strictly increasing
Believing tails itself is a valid subsequence -- it is not, only its length is meaningful
Confusing subsequence with contiguous subarray

Check your understanding

Why does using bisect_left rather than bisect_right matter here?

Longest Increasing Subsequence

Longest Increasing Subsequence

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming