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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Longest Increasing Subsequence and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →