mafeshsho8lmafeshsho8l
Get Started
All coding questions

Longest Increasing Subsequence

medium
Blind 75NeetCode 150dynamic-programmingbinary-search

Problem

Given a list of integers, return the length of the longest strictly increasing subsequence. The chosen elements need not be contiguous but must keep their original order.

Examples

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
2, 3, 7, 101 is one longest increasing run of length four.
Input: nums = [7, 7, 7]
Output: 1
No strict increase is possible.

Constraints

  • • 1 <= nums.length <= 2500
  • • -10^4 <= nums[i] <= 10^4
Hints(tap to reveal)
  • 1. A quadratic DP extends each prior smaller element.
  • 2. A patience-sorting tails array gives O(n log n).
Optimal approach(spoiler)
  1. Maintain a tails array where each slot holds the smallest possible tail of an increasing subsequence of that length.
  2. For each value, binary search for the first tail not smaller than it.
  3. Replace that tail, or append if the value extends all tails.
  4. The tails length is the answer.
  5. O(n log n) time, O(n) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor