Compute longest increasing subsequence

Longest Increasing Subsequence: length, reconstruction, and counting

Given an integer array nums, do all of the following:

1. Length. Compute the length of a longest strictly increasing subsequence (LIS). A subsequence is obtained by deleting zero or more elements without changing the relative order of the remaining elements; strictly increasing means each chosen element is strictly greater than the previous one.
2. Reconstruction. Output one concrete LIS (the actual sequence of values/indices), not just its length.
3. Efficiency. Target an $O(n \log n)$ time solution. Explain the binary-search (patience-sorting) technique, how reconstruction works on top of it, and give the time and space complexity.

Walk through your approach, write clean code, and reason about correctness and edge cases as you go.

Hint: Brute force first, then sharpen

The $O(n^2)$ DP is the natural starting point: $\text{dp}[i] =$ length of the longest increasing subsequence ending at index $i$. Get that right and stated, then ask what's redundant about it — that's the door to $O(n \log n)$.

Hint: The key data structure

Maintain an array tails, where tails[k] is the smallest possible tail value of any increasing subsequence of length $k+1$ seen so far. Convince yourself tails is always strictly increasing — that invariant is exactly what lets you binary-search it.

Hint: Which binary search

For a strictly increasing LIS, for each new element find the leftmost position in tails whose value is $\geq$ the element (a lower-bound / bisect_left) and overwrite it; append only when the element exceeds every tail. The LIS length is len(tails). Think about why tails's length — not its contents — is the answer.

Hint: Reconstruction without storing every candidate

tails itself is not a valid subsequence (it gets overwritten). To recover an actual LIS, also record, for each original index, the length of the LIS ending there (= the tails slot you wrote to, plus 1) and a predecessor pointer to the index that occupied tails[slot-1] at that moment. Backtrack from the index that achieved the maximum length.

Constraints & Assumptions

• Use these unless your interviewer says otherwise:
  • $1 \le n \le 2{,}500$ for the basic version, but design for large $n$ (e.g. up to $10^5$ or more) so the $O(n\log n)$ method is justified.
  • Values fit in a 32-bit signed integer and may be negative; duplicates may appear.
• "Strictly increasing" is the default. The non-decreasing variant is treated as a follow-up.
• Returning any one valid LIS is acceptable when several exist; you do not need a specific tie-break unless asked.

Clarifying Questions to Ask

• Strictly increasing, or non-decreasing (are equal adjacent values allowed)?
• Do you want the length only, or also one reconstructed subsequence (values vs. indices)?
• What is the expected range of $n$ and of the values? Can values be negative or duplicated?
• If multiple LIS exist, is any one acceptable, or is there a required tie-break (e.g. lexicographically smallest)?
• Is the input mutable / can I use $O(n)$ auxiliary space?

What a Strong Answer Covers

• States the $O(n^2)$ DP recurrence correctly, then explains the specific redundancy the $O(n\log n)$ method removes.
• Defines the tails invariant precisely (smallest tail per length) and argues it stays sorted, justifying the binary search.
• Picks the correct binary-search variant for strict increase (lower-bound / bisect_left) and can articulate how it changes for the non-decreasing case.
• Produces a correct reconstruction, not just a length — via length-at-index plus predecessor pointers — and explains why tails alone cannot be returned.
• Gives accurate complexity: $O(n\log n)$ time, $O(n)$ space, and handles edge cases (empty array, all-equal, all-decreasing, single element).
• Communicates clearly, names the patience-sorting intuition, and tests the code on a small example.

Follow-up Questions

• Non-decreasing variant: how does the algorithm change to allow equal adjacent values, and which binary-search bound do you switch to?
• Duplicates: with repeated values, where exactly does the strict-vs-non-strict distinction bite, and how do you avoid an off-by-one that lets duplicates sneak into a "strict" LIS?
• Counting LIS: how would you count how many distinct longest increasing subsequences exist? Discuss both an $O(n^2)$ DP (carry a count alongside each length) and the idea behind an $O(n\log n)$ count using Fenwick/segment trees keyed by value.
• Output sensitivity: if you needed to enumerate all LIS rather than count them, what changes, and why can that be exponential?

Longest Increasing Subsequence (length + reconstruction)

Given an integer array nums, return a pair (length, subsequence) where length is the length of a longest STRICTLY increasing subsequence (LIS), and subsequence is one concrete LIS of that length (its actual values, in order).

A subsequence is formed by deleting zero or more elements without changing the relative order of the rest. 'Strictly increasing' means each chosen value is strictly greater than the previous one.

If several LIS exist, returning any one of them is acceptable. Aim for an O(n log n) approach using the patience-sorting / binary-search technique, augmented with predecessor pointers so you can reconstruct an actual subsequence (not just its length).

Return convention by language:

• Python: return a tuple (length, subsequence_list).
• Java: return int[] whose first element is the length, followed by the subsequence values (length 1 + L).
• C++: return vector<int> whose first element is the length, followed by the subsequence values.
• JavaScript: return an array [length, ...subsequence].

For the empty input, return length 0 with an empty subsequence.

Examples

Example 1

Input: ([10, 9, 2, 5, 3, 7, 101, 18],)
Output: (4, [2, 3, 7, 101])

Explanation: LIS length is 4; [2,3,7,101] is one valid longest strictly increasing subsequence (so is [2,3,7,18]).

Example 2

Input: ([],)
Output: (0, [])

Explanation: Empty array: length 0 and an empty subsequence.

Hints

1. Start with the O(n^2) DP: dp[i] = length of the longest strictly increasing subsequence ending at index i. Then ask what is redundant about rescanning all earlier elements.
2. Maintain an array tails where tails[k] is the smallest possible tail value of any strictly increasing subsequence of length k+1. It stays strictly increasing, so you can binary-search it; len(tails) is the LIS length.
3. For a STRICT LIS use bisect_left (leftmost tail >= x): overwrite that slot, or append if x exceeds every tail. (For the non-decreasing variant you'd switch to bisect_right.)
4. tails is not itself a valid subsequence. To reconstruct, also record a predecessor pointer per index (the index occupying tails[pos-1] at write time) and backtrack from the index that achieved the maximum length.

Solution

Longest Increasing Subsequence — full solution

1. Restating the problem

Given nums, find the length of a longest strictly increasing subsequence, return one such subsequence, and do it in $O(n\log n)$. A subsequence keeps relative order; elements need not be contiguous.

Example: nums = [10, 9, 2, 5, 3, 7, 101, 18] → LIS length 4, e.g. [2, 3, 7, 18] or [2, 3, 7, 101].

2. Baseline: the $O(n^2)$ DP (state it, then beat it)

Let $\text{dp}[i]$ be the length of the longest strictly increasing subsequence ending exactly at index $i$.

$$\text{dp}[i] = 1 + \max\big(\{\,\text{dp}[j] : j < i \text{ and } \text{nums}[j] < \text{nums}[i]\,\} \cup \{0\}\big)$$

The answer is $\max_i \text{dp}[i]$. This is $O(n^2)$ time, $O(n)$ space, and is easy to reconstruct by storing a predecessor for each $i$.

Why it's wasteful: for each $i$ we rescan all earlier elements just to find the best compatible predecessor. The $O(n\log n)$ method replaces that linear scan with a binary search over a cleverly maintained array.

3. The $O(n\log n)$ method (patience sorting)

The invariant

Maintain tails, where

tails[k] = the smallest possible tail value among all strictly increasing subsequences of length k + 1 found so far.

Two facts make this work:

• tails is always strictly increasing. A length-$(k{+}1)$ subsequence with tail $t$ contains a length-$k$ prefix whose tail is $< t$, so tails[k-1] < tails[k]. Because it's sorted, we can binary-search it.
• len(tails) is exactly the current LIS length. We never store a length we can't achieve.

Processing one element x

For a strictly increasing LIS:

• Find the leftmost index pos in tails with tails[pos] >= x (a lower bound, bisect_left).
• If pos == len(tails), x extends the longest subsequence → append it.
• Otherwise overwrite tails[pos] = x. This keeps the "smallest tail for that length" invariant and never decreases any achievable length.

Using bisect_left (≥) is what enforces strict increase: a value equal to an existing tail overwrites that same slot rather than extending, so duplicates can't lengthen a strict LIS.

Length-only code

from bisect import bisect_left

def lis_length(nums):
    tails = []
    for x in nums:
        pos = bisect_left(tails, x)   # leftmost tail >= x  (strict LIS)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

tails is not itself a valid subsequence — its entries come from different positions and later writes overwrite earlier ones. Its length is correct; its contents are not a reconstructable answer. Hence the next section.

4. Reconstructing one actual LIS in $O(n\log n)$

Add two arrays during the same pass:

• length_ending[i] — length of the LIS ending at index i = pos + 1 (the slot we wrote to, 1-indexed).
• prev[i] — the index that currently sits in tails[pos - 1] at the moment we place i (its predecessor in the LIS), or -1 when pos == 0.

We also keep tail_idx[k] = the index (not value) currently occupying tails[k], so we can read off the predecessor's index in $O(1)$.

from bisect import bisect_left

def lis_with_reconstruction(nums):
    if not nums:
        return 0, []

    tails_val = []      # tails_val[k] = smallest tail VALUE for length k+1
    tail_idx  = []      # tail_idx[k]  = index achieving that tail
    prev      = [-1] * len(nums)
    best_len, best_end = 0, -1

    for i, x in enumerate(nums):
        pos = bisect_left(tails_val, x)   # strict LIS -> lower bound
        prev[i] = tail_idx[pos - 1] if pos > 0 else -1

        if pos == len(tails_val):
            tails_val.append(x)
            tail_idx.append(i)
        else:
            tails_val[pos] = x
            tail_idx[pos]  = i

        if pos + 1 > best_len:
            best_len, best_end = pos + 1, i

    # backtrack predecessor pointers from the best endpoint
    seq, k = [], best_end
    while k != -1:
        seq.append(nums[k])
        k = prev[k]
    seq.reverse()
    return best_len, seq

Why the predecessor is correct: when we place index i into slot pos, its LIS prefix has length pos, and tail_idx[pos-1] holds an index whose own LIS has length pos and ends in a value < x (guaranteed because tails_val[pos-1] < tails_val[pos] <= x by the sorted invariant and the lower-bound search). Chaining prev from the global best endpoint yields a genuinely increasing subsequence of length best_len.

Returning indices instead of values is a trivial change (append k instead of nums[k]), and is preferable when the caller needs positions.

5. Complexity

	Time	Space
$O(n^2)$ DP	$O(n^2)$	$O(n)$
Patience sorting (length)	$O(n\log n)$	$O(n)$
Patience sorting + reconstruction	$O(n\log n)$	$O(n)$

Each of the $n$ elements does one $O(\log n)$ binary search; backtracking is $O(\text{LIS length}) \le O(n)$. The auxiliary arrays (tails_val, tail_idx, prev) are each $O(n)$.

6. Edge cases (tested mentally)

• Empty array → length 0, empty subsequence.
• Single element → length 1.
• All equal, e.g. [7,7,7] → strict LIS length 1 (lower bound keeps overwriting slot 0). This is the case that exposes a wrong binary-search choice.
• Strictly decreasing, e.g. [5,4,3,2,1] → length 1.
• Already increasing → length n, the whole array.
• Negatives / duplicates mixed, e.g. [3, -1, -1, 0, 5] → strict LIS [-1, 0, 5], length 3.

7. Follow-ups

(a) Non-decreasing variant

Allow equal adjacent values. The only change is the binary-search bound: use the upper bound (bisect_right, leftmost tail > x) instead of bisect_left. Now an element equal to an existing tail extends past it rather than overwriting, so equal values can chain.

from bisect import bisect_right
def lnds_length(nums):                 # longest NON-decreasing subsequence
    tails = []
    for x in nums:
        pos = bisect_right(tails, x)    # leftmost tail > x
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

Reconstruction is identical with bisect_right swapped in.

(b) Where duplicates bite

The strict-vs-non-strict distinction is entirely the bisect_left vs bisect_right choice. The classic off-by-one is using bisect_right while believing you computed a strict LIS: with input [2, 2], bisect_right would append the second 2, reporting length 2 and letting a duplicate sneak into a "strictly increasing" answer. bisect_left (≥) correctly overwrites and reports 1. So: bisect_left ⇒ strict, bisect_right ⇒ non-decreasing, and nothing else changes.

(c) Counting how many LIS exist

$O(n^2)$ DP with counts. Alongside dp[i] (length of LIS ending at i) keep cnt[i] (number of LIS ending at i). Initialize dp[i]=1, cnt[i]=1. For j < i with nums[j] < nums[i]:

• if dp[j] + 1 > dp[i]: set dp[i] = dp[j] + 1, cnt[i] = cnt[j] (new strictly-longer length resets the count);
• elif dp[j] + 1 == dp[i]: cnt[i] += cnt[j] (another way to reach the same max length).

The answer is $\sum_{i:\,dp[i]=L} cnt[i]$ where $L = \max_i dp[i]$.

def count_lis(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp  = [1] * n
    cnt = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    cnt[i] = cnt[j]
                elif dp[j] + 1 == dp[i]:
                    cnt[i] += cnt[j]
    L = max(dp)
    return sum(c for d, c in zip(dp, cnt) if d == L)

This is $O(n^2)$ time, $O(n)$ space.

Idea behind an $O(n\log n)$ count. Coordinate-compress the values, then process left to right maintaining a Fenwick (BIT) / segment tree keyed by value that, for any value v, returns (best_length, total_count) over all already-processed elements with value < nums[i] (strict). Each query/update is $O(\log n)$:

• query the prefix [min .. nums[i]-1] for the best length $\ell$ and the summed count at that length;
• the element's own (length, count) is (ℓ+1, that_count) (or (1, 1) if the prefix is empty);
• update position nums[i] in the tree, merging with any existing entry at the same length.

A segment tree storing (maxLen, countAtMaxLen) with a merge that keeps the max length and adds counts on ties gives the global answer in $O(n\log n)$. For the non-decreasing count, query the inclusive prefix [min .. nums[i]] instead.

(d) Enumerating all LIS

Counting is polynomial, but the number of distinct LIS can be exponential (e.g. many parallel equal-length chains), so explicitly listing them is worst-case $O(\text{count} \times L)$ — exponential in $n$. To enumerate, build the dp/prev-set graph (each index points to all predecessors that achieve dp[i]-1 with a smaller value) and DFS-backtrack from every max-length endpoint, which is why counting (a single number) is far cheaper than enumeration.