LeetCode 300 Longest Increasing Subsequence - Binary Search Implementation

Here's the faster solution:

function lengthOfLIS(nums)
    tails := empty array
    for each num in nums
        // Binary search for leftmost position >= num
        pos := binarySearch(tails, num)
        if pos = length of tails then
            tails.append(num)
        else
            tails[pos] := num
    return length of tails

Time: $O(n \log n)$. Space: $O(n)$.

tails[i] stores the smallest ending element of any increasing subsequence of length i+1. For each new number, you either extend the longest subsequence or replace an element to keep tails as small as possible.

The array tails is always sorted, enabling binary search. This greedy approach works because smaller endings give more room for future elements.