Longest Increasing Subsequence with Reconstruction

Coding · Hard · Free problem

Given an array of $n$ integers, return the length of a strictly longest increasing subsequence (LIS).

Implement the function:

```python def lis_length(nums): ... ```

  • nums is a list of integers.
  • Return an int: the length of the strictly increasing subsequence of maximum length.

Your solution must run in $O(n \log n)$ time and $O(n)$ space.

Constraints:

  • $0 \le n \le 10^5$
  • Array elements can be any 32-bit integer (including negatives and duplicates)
  • "Strictly increasing" means no two equal elements are allowed in the subsequence
  • The empty array has LIS length 0

Example

``` lis_length([10, 9, 2, 5, 3, 7, 101, 18]) -> 4 ```

A longest strictly increasing subsequence is [2, 3, 7, 18] (or [2, 3, 7, 101]), which has 4 elements, so the returned length is 4.

Hints

  1. Think about what information you need to maintain as you scan left to right. For each possible subsequence length, what single value is most useful to track?
  2. If you keep track of the smallest tail element for increasing subsequences of each length, this array stays sorted -- so you can binary search it. That is the core of patience sorting.
  3. To reconstruct the actual subsequence (not just its length), store a predecessor pointer for each element when you place it. After the scan, walk backward from the last element of the longest subsequence.

Worked Solution

How to Think About It: The brute-force approach checks all $2^n$ subsequences -- hopeless. The classic DP gives $O(n^2)$, fine for small $n$ but too slow at $n = 10^5$. The key insight is patience sorting: maintain an array tails where tails[i] holds the smallest possible tail value of any strictly increasing subsequence of length $i+1$ found so far. This array is always sorted, so you can binary search it for each new element, giving $O(n \log n)$.

This problem only asks for the length, so no predecessor tracking / reconstruction is needed -- the answer is simply len(tails) after processing every element.

Algorithm:

1. Maintain a sorted array tails of the smallest tail values for each achievable subsequence length. 2. For each x in nums, binary search tails with bisect_left for the leftmost position pos where tails[pos] >= x. - If pos == len(tails), x is larger than every tail, so it extends the longest subsequence: append x. - Otherwise, replace tails[pos] with x (a smaller tail for a subsequence of that length). 3. The final len(tails) is the LIS length.

Using bisect_left (not bisect_right) enforces strict increase: an element equal to an existing tail overwrites it rather than extending, so duplicates never lengthen the subsequence.

Why does tails stay sorted? The smallest tail of a length-$k$ subsequence must be strictly less than the smallest tail of a length-$(k+1)$ subsequence, otherwise you could extend the shorter one. Binary search exploits this invariant.

Code:

```python from bisect import bisect_left

def lis_length(nums): # Return the LENGTH of a strictly longest increasing subsequence of nums. # Patience sorting: tails[i] = smallest possible tail value of an # increasing subsequence of length i+1. tails stays sorted, so each new # element is placed via binary search in O(log n). tails = [] for x in nums: pos = bisect_left(tails, x) # leftmost tail >= x (strictly increasing) if pos == len(tails): tails.append(x) else: tails[pos] = x return len(tails) ```

Edge Cases:

  • Empty array: the loop never runs, tails stays empty, returns 0.
  • Single element: tails becomes [x], returns 1.
  • All equal elements: bisect_left returns position 0 every time, so tails never grows beyond length 1. Returns 1 -- correct, since strict increase forbids equal elements.
  • Already sorted: each element extends tails, so the length equals n.
  • Reverse sorted: each element overwrites tails[0], so the length is 1.

Complexity:

  • Time: $O(n \log n)$ -- $n$ elements, each doing one $O(\log n)$ binary search.
  • Space: $O(n)$ -- tails has at most $n$ entries.

Intuition

Patience sorting gets its name from the card game Patience (Solitaire). Imagine dealing cards into piles where you can only place a card on top of a pile whose top card is greater than or equal to the card you are dealing, and you always choose the leftmost valid pile (or start a new pile if none works). The number of piles at the end equals the LIS length. The reason is subtle: each pile corresponds to a "level" in the subsequence hierarchy, and the invariant that pile tops are increasing means you can always stitch together one element from each pile into a valid increasing subsequence.

This pattern shows up constantly in algorithm design: maintaining a compact summary of the search space (here, the tails array) that supports fast updates. The same "replace the first element that is too big" idea appears in problems about scheduling, covering, and greedy optimization. The reconstruction trick -- storing predecessor pointers during the forward pass and walking them backward -- is a universal technique for recovering solutions from DP and greedy algorithms. In interviews, forgetting reconstruction is the most common mistake; candidates find the length but cannot produce the actual subsequence.

Related problems

Open the full interactive solver →