Challenge: LIS in O(n log n) Space O(n)

The binary search LIS uses $O(n)$ space for the tails array. Can we do better? Not. We need to store the tails array to enable binary search.

The array size is at most $n$ (the LIS length). For reconstruction with $O(n \log n)$ time, we need additional $O(n)$ space to track predecessors. space reduction is more relevant for the $O(n^2)$ approach: we can avoid storing the full DP array if we only need the length, but reconstruction requires $O(n)$ space regardless.