Longest Increasing Subsequence

Reported in interviews at Citadel Citi Two Sigma Walleye Capital

Problem statement

Given an array of $n$ integers, find the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some (or no) elements without changing the order of the remaining elements.

Design an $O(n \log n)$-time algorithm. Specifically:

  1. Describe the algorithm and explain the invariant maintained by the auxiliary "tails" array.
  2. Show how to reconstruct one actual longest increasing subsequence (not just its length) while keeping time $O(n \log n)$ and extra space $O(n)$.

Constraints:

  • $1 \leq n \leq 10^5$
  • $-10^4 \leq \text{nums}[i] \leq 10^4$
  • Subsequence must be strictly increasing

Example 1:

  • Input: nums = [3, 1, 4, 1, 5, 9, 2, 6]
  • Output: 4
  • Explanation: One longest increasing subsequence is $[1, 4, 5, 9]$. Others of length 4 exist, e.g., $[1, 4, 5, 6]$.

Example 2:

  • Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
  • Output: 4
  • Explanation: One LIS is $[2, 3, 7, 101]$. Another is $[2, 5, 7, 18]$.

Example 3:

  • Input: nums = [7, 7, 7, 7]
  • Output: 1
  • Explanation: All elements are equal, so the longest strictly increasing subsequence has length 1.
Show hint

For each possible subsequence length, which single number summarizes everything you need to know to extend it later?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems