Longest Increasing Subsequence
MediumPatience sorting · O(n log n)
For each number, the longest rising run ending there is one more than the best smaller number before it.
The idea
Maintain the smallest possible tail for an increasing subsequence of each length. Binary-search each number into that tails array; its length is the LIS length.
2
5
3
7
101
18
0
1
2
3
4
5
Step 1 of 8. Keep the smallest tail for each length. Binary-search each number into "tails". Values: 2, 5, 3, 7, 101, 18.
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:
- 4
- Explanation:
- 2,3,7,101 rises for length 4.
Example 2
- Input:
- nums = [0, 1, 0, 3, 2, 3]
- Output:
- 4
- Explanation:
- 0,1,2,3 gives length 4.
Example 3
- Input:
- nums = [7, 7, 7]
- Output:
- 1
- Explanation:
- No increase possible → length 1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.