Print Longest Increasing Subsequence

Medium

Store a predecessor with each length

Problem

Return the actual longest strictly increasing subsequence (not just its length).

In simple words

Track tails and parent links so you can walk back and print an actual longest increasing subsequence.

The idea

Run the O(n²) LIS keeping, for each index, the previous index of the best subsequence ending there. Following those links back from the best endpoint reconstructs the actual sequence.

The trick

The O(n log n) tails method finds the length but not the sequence directly.
Store parent indices, then walk back and reverse.

←→stepspaceplay

101

1/8

Optimal

timeO(n log n)spaceO(n)

Replace the first tail ≥ x.

1// keep the smallest possible tail for each length2const tails = [];3for (const x of nums) {4  let lo = 0, hi = tails.length;5  while (lo < hi) { const m=(lo+hi)>>1;6    if (tails[m] < x) lo = m+1; else hi = m; }7  tails[lo] = x;8}9return tails.length;

Input

array: [2, 5, 3, 7, 101, 18]

Memory

num: —

Output

LIS: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output:: [2, 3, 7, 18]
Explanation:: One actual longest increasing run.

Example 2

Input:: nums = [1, 2, 3]
Output:: [1, 2, 3]
Explanation:: The whole array rises.

Example 3

Input:: nums = [5, 1, 2]
Output:: [1, 2]
Explanation:: 1,2 is the longest run.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.