LeetCode 300 Longest Increasing Subsequence - Binary Search Optimization

The $O(n^2)$ bottleneck: for each element, we scan all previous elements. Can we do better? observation: maintain an array $tails$ where $tails[k]$ is the smallest ending element of all increasing subsequences of length $k+1$. When you see a new element $x$:

$1.$ If $x$ is larger than all elements in $tails$, append it (extends the longest subsequence).

$2.$ Otherwise, find the smallest element in $tails$ that is $\ge x$ and replace it with $x$. Why replace? A smaller ending value gives more room to extend later. The length of $tails$ is your answer.