Skip to content

Practice Longest Increasing Subsequence

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#300
LeetCode Problem

Longest Increasing Subsequence

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence. Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Source: Longest Increasing Subsequence on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nums = [10,9,2,5,3,7,101,18]
Output
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

Constraints

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

How to solve Longest Increasing Subsequence

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

For each possible length, track the smallest value that can end an increasing subsequence of that length; this list stays sorted, so each new element either extends it or replaces the first entry that is at least as large, located by binary search.

Why brute force is not enough

Enumerating 2^n subsequences is impossible for n up to 2500. The quadratic dynamic program, where each position looks back at every earlier smaller element, is O(n^2), about 6 * 10^6 steps, which passes but does not meet the O(n log n) follow-up an interviewer will push toward.

Approach

  1. Keep a list called tails where entry i is the smallest possible last value of a strictly increasing subsequence of length i + 1; because a shorter subsequence can always end no higher than a longer one, the list is strictly increasing.
  2. For each element in order, binary search for the leftmost tails entry that is greater than or equal to it.
  3. If none exists, the element extends the longest subsequence so far, so append it.
  4. Otherwise overwrite that entry; the length it represents is unchanged but now ends on a smaller value, which only helps later extensions.
  5. The final length of tails is the answer. The list itself is generally not a valid subsequence, so reconstructing one needs a separate predecessor record.

Walkthrough of Example 1

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

  1. 10 starts tails as [10]; 9 replaces it giving [9]; 2 replaces it giving [2].
  2. 5 exceeds everything, so append: [2,5]. 3 replaces 5, the first entry at least 3: [2,3].
  3. 7 is appended: [2,3,7]. 101 is appended: [2,3,7,101].
  4. 18 replaces 101: [2,3,7,18]. The length 4 is the answer, matching subsequences such as 2, 3, 7, 101.

Time and space

Time O(n log n) · Space O(n). n is nums.length; each element does one binary search over a list of at most n entries, and tails is the only extra storage.

Interview pitfalls

  • Using the wrong binary search bound: strictly increasing requires replacing the first entry greater than or equal to the element; searching for strictly greater instead permits equal values and returns 7 rather than 1 for example 3.
  • Reporting tails as the subsequence; after example 1 it reads [2,3,7,18], a valid subsequence here only by coincidence.
  • Off-by-one when the element exceeds the last entry, which must append rather than overwrite an out-of-range index.
  • Not being able to explain how to upgrade the O(n^2) solution when asked.

Follow-up questions interviewers ask

  • How would you reconstruct one actual longest increasing subsequence, not just its length?
  • How does the method change for a longest non-decreasing subsequence?
  • Can you count how many distinct longest increasing subsequences exist, and why does the tails trick no longer suffice?

Further reading on the technique: Longest increasing subsequence

Related LeetCode Problems

Practice more problems similar to Longest Increasing Subsequence.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.