← Back to DSA Animator
Longest Increasing Subsequence LC #300 Medium Patience Sort · Binary Search
Problem

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

Example 1
Input: [10,9,2,5,3,7,101,18]
Output: 4
Patience sort: tails[i] = smallest tail of IS of length i+1. Binary search for first tail ≥ num; extend or replace.
Try Examples
Custom:
Approach
Patience Sort — tails array + binary search
tails[i] = smallest tail of IS of length i+1. For each num: bin-search first tail ≥ num → replace or extend.
Input & Tails
Load an example to begin.
Variables
i / num
—
pos
—
action
—
tails.length
—
Step Logic
Press ▶ Play or Next Step to begin.
📈
Ready
0 / 0
Select an example and press Play.
Algorithm
1
tails[i] = smallest tail of IS of length i+1
2
For each num: binary search first tail ≥ num
3
Replace or extend: pos==size → append, else tails[pos]=num
4
Answer = tails.size()
Time
O(n log n)
Space
O(n)
Why This Works

Patience sorting: maintain pile tops. Each number goes on leftmost pile whose top ≥ it (binary search). If larger than all, new pile. Number of piles = LIS length.