Longest Increasing Subsequence in O(n log n)

Reported in interviews at Barclays

Problem statement

Given an array of integers $a_1, a_2, \ldots, a_n$, find the length of the longest strictly increasing subsequence (LIS).

A subsequence is strictly increasing if each element is greater than the one before it -- elements need not be contiguous.

Requirements:

  1. Implement the patience-sorting approach: maintain a list of "pile tops" and use binary search to place each new element. Return the number of piles at the end.
  2. Explicitly handle duplicate values in the input (remember: the subsequence must be strictly increasing, so duplicates cannot both appear).
  3. Argue why this algorithm is correct -- why does the number of piles equal the LIS length?

Constraints:

  • $1 \leq n \leq 10^5$
  • $-10^4 \leq a_i \leq 10^4$
  • Target: $O(n \log n)$ time, $O(n)$ space

Examples:

  • Input: [10, 9, 2, 5, 3, 7, 101, 18] -- Output: 4 (the LIS is [2, 3, 7, 101] or [2, 5, 7, 101])
  • Input: [0, 1, 0, 3, 2, 3] -- Output: 4 (the LIS is [0, 1, 2, 3])
  • Input: [7, 7, 7, 7, 7] -- Output: 1 (all duplicates, no two can both appear in a strictly increasing subsequence)
Show hint

For each possible subsequence length, what is the most useful single number to remember about all runs of that length?

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

Related free problems