Skip to main content

300. Longest Increasing Subsequence

medium

Find the length of the longest strictly-increasing subsequence of an array. The textbook O(n^2) DP is the warm-up; patience sort with binary search gets you to O(n log n).

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Constraints

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1

Input
nums = [10,9,2,5,3,7,101,18]
Output
4

Explanation: The longest increasing subsequence is [2,3,7,101] with length 4.

Example 2

Input
nums = [0,1,0,3,2,3]
Output
4

Example 3

Input
nums = [7,7,7,7,7,7,7]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i] = length of the longest increasing subsequence ending at index i. dp[i] = 1 + max(dp[j] for j < i, nums[j] < nums[i]).

Hint 2

Answer is max(dp). O(n^2) — fine for n <= 2500.

Hint 3

For O(n log n), maintain a tails[] array where tails[k] is the smallest possible tail of any increasing subseq of length k+1. Binary-search each new num and replace or extend.

Solution approach

Reveal approach

Two approaches. O(n^2) DP: dp[i] = 1 + max(dp[j] for all j < i with nums[j] < nums[i]); the answer is max(dp). O(n log n) patience: maintain a tails array; for each num, binary-search the leftmost tail >= num. If found, replace it; if not, append (extending the longest run). The length of the tails array is the answer. The patience version doesn't reconstruct the subsequence directly — but length is what's asked.

Complexity

Time
O(n^2) DP or O(n log n) patience
Space
O(n)

Related patterns

  • dynamic-programming
  • binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta

More Dynamic Programming practice problems

See all Dynamic Programming problems →