Example 1
ready- Input
nums = [ 10, 9, 2, 5, 3, 7, 101, 18 ]- Expected
4- Why
- one longest choice is 2, 3, 7, 18
Longest Increasing Subsequence
35 min · lengthOfLIS()mediumOpen in LeetCode #300 ↗
Daily temperatures can dip, repeat, and spike. Hidden inside that noisy record may be a much longer upward trend than any one continuous stretch suggests.
Given an integer array nums, return the length of its longest strictly increasing
subsequence. A subsequence keeps elements in their original order while allowing you
to skip any number of positions.
The increase must be strict: every chosen value must be greater than the chosen value before it. Equal values never extend the sequence.
Constraints
1 <= nums.length <= 2_500-10_000 <= nums[i] <= 10_000
Hints
End at one position
Suppose the subsequence must end at index i. Which earlier indices could sit
immediately before it, and which earlier answer would you want to extend?
Write the DP state
Let dp[i] be the longest increasing subsequence ending exactly at i. Start it at
1, then inspect every j < i with nums[j] < nums[i].
Keep only useful tails
For each possible length, remember the smallest ending value found so far. A smaller tail leaves more room for future values, and binary search finds the tail to replace.
Follow-up
Can you reconstruct one longest increasing subsequence, not just report its length?
Visible cases
Examples
Example 2
ready- Input
nums = [ 0, 1, 0, 3, 2, 3 ]- Expected
4- Why
- 0, 1, 2, 3 keeps order while skipping positions
Example 3
ready- Input
nums = [ 7, 7, 7, 7 ]- Expected
1- Why
- equal values don't count as a strict increase
Interview signal
Asked at
AmazonGoogleMicrosoft
Quadratic LIS DP — choose the previous value
Dynamic programming (DP) stores answers for smaller overlapping problems so later
answers can reuse them. Define dp[i] as the length of the longest strictly increasing
subsequence that ends exactly at index i.
Every value can stand alone, so each state starts at 1. For every earlier index j, you
may append nums[i] only when nums[j] < nums[i].
def length_of_lis(nums: list[int]) -> int:
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)The final subsequence may end anywhere, so the answer is the largest state rather than
only dp[-1].
Time O(n²) for all earlier/later pairs. Space O(n) for the DP array.
Patience sorting — tails + binary search
The O(n log n) method is often called the patience-sorting method, a strategy that
maintains the best tail value for every length seen so far. tails[k] is the smallest
possible ending value of an increasing subsequence of length k + 1.
For each number, binary-search for the first tail that is greater than or equal to it:
- If no such tail exists, the number extends the longest subsequence.
- Otherwise, replace that tail. The length doesn't change, but future numbers now have an easier value to extend.
from bisect import bisect_left
def length_of_lis(nums: list[int]) -> int:
tails: list[int] = []
for value in nums:
position = bisect_left(tails, value)
if position == len(tails):
tails.append(value)
else:
tails[position] = value
return len(tails)bisect_left finds the first value >= value. That detail enforces strict increase:
when a duplicate arrives, it replaces an existing tail instead of creating a new length.
The tails entries need not form a subsequence from the input; only its length is the
answer.
Time O(n log n) because each of n values performs one binary search. Space O(n) for the tails array.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
4
Run: visible + custom · Submit: full suite