Longest Increasing Subsequence
Description
Given an array of integers, find the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be formed from the original array by deleting some (or no) elements without changing the relative order of the remaining elements. Unlike a subarray, the elements in a subsequence do not need to be contiguous — they just need to maintain their original left-to-right order.
The subsequence must be strictly increasing, meaning each element must be strictly greater than the one before it (not equal).
Return the length of the longest such subsequence.
Examples
Example 1
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: One longest increasing subsequence is [2, 3, 7, 101]. We pick index 2 (value 2), index 4 (value 3), index 5 (value 7), and index 6 (value 101). Each element is strictly greater than the previous: 2 < 3 < 7 < 101. There are other valid LIS of length 4 as well, such as [2, 5, 7, 101] or [2, 3, 7, 18], but none is longer than 4.
Example 2
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: The longest increasing subsequence is [0, 1, 2, 3] — picking values at indices 0, 1, 4, and 5. Notice that we skip the 0 at index 2 and the 3 at index 3, choosing the 2 at index 4 instead, which allows us to extend with 3 at index 5.
Example 3
Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1
Explanation: Since the subsequence must be strictly increasing, equal elements cannot be part of the same subsequence. Every element is 7, so no two elements form an increasing pair. The longest increasing subsequence is any single element, giving a length of 1.
Constraints
- 1 ≤ nums.length ≤ 2500
- -10^4 ≤ nums[i] ≤ 10^4
Editorial
Brute Force
Intuition
The most straightforward way to think about this problem is: try every possible subsequence and check which ones are strictly increasing, then take the longest one.
An array of length n has 2^n possible subsequences (for each element, we either include it or skip it). For each subsequence, we check whether it is strictly increasing — meaning every element is larger than the one before it. Among all increasing subsequences, we track the one with the maximum length.
We can implement this recursively. For each element at index i, we make a choice: include it in the current subsequence (if it is greater than the last element we included) or skip it. We recurse forward and take the maximum length we can achieve from both choices.
This approach is conceptually simple but extremely slow. With n up to 2500, generating 2^2500 subsequences is utterly infeasible. However, it establishes the correct logic that we will optimize step by step.
Step-by-Step Explanation
Let's trace through a smaller example: nums = [3, 1, 4, 2]
We recursively try including or excluding each element, keeping track of the last element included.
Step 1: Start at index 0, no previous element selected (prev = -∞). Element is 3.
- Choice A: Include 3 (3 > -∞ ✓). New prev = 3, move to index 1.
- Choice B: Skip 3. prev stays -∞, move to index 1.
Step 2 (from Choice A, prev=3): Index 1, element is 1.
- Include 1? 1 > 3? No ✗. Cannot include.
- Skip 1. Move to index 2 with prev still 3.
Step 3 (from Step 2, prev=3): Index 2, element is 4.
- Include 4? 4 > 3? Yes ✓. New prev = 4, move to index 3.
- Skip 4. Move to index 3 with prev still 3.
Step 4 (included 4, prev=4): Index 3, element is 2.
- Include 2? 2 > 4? No ✗. Cannot include.
- Skip 2. End of array. Subsequence [3, 4], length = 2.
Step 5 (skipped 4, prev=3): Index 3, element is 2.
- Include 2? 2 > 3? No ✗. Cannot include.
- Skip 2. End of array. Subsequence [3], length = 1.
Step 6 (from Choice B, prev=-∞): Index 1, element is 1.
- Include 1? 1 > -∞? Yes ✓. New prev = 1, move to index 2.
- Skip 1. Move to index 2 with prev = -∞.
Step 7 (included 1, prev=1): Index 2, element is 4.
- Include 4? 4 > 1? Yes ✓. New prev = 4, move to index 3.
- Index 3, element 2. 2 > 4? No. Skip. Subsequence [1, 4], length = 2.
- Skip 4. Index 3, element 2. 2 > 1? Yes. Include. Subsequence [1, 2], length = 2.
Step 8: After exploring all paths, the maximum length found is 2 (subsequences [3, 4], [1, 4], [1, 2] are all length 2).
Notice how we explore many overlapping paths — the same (index, prev) combinations are recomputed multiple times. This motivates memoization.
Brute Force Recursion — Exploring All Subsequences — Watch how the recursive brute force explores every include/skip choice for each element, creating an exponential tree of possibilities.
Algorithm
- Define a recursive function lis(index, prev_index) that returns the length of the longest increasing subsequence starting from position index, where prev_index is the index of the last element included
- At each index, we have two choices:
a. Skip the current element — recurse with lis(index+1, prev_index)
b. Include the current element (only if nums[index] > nums[prev_index] or prev_index is -1) — recurse with 1 + lis(index+1, index) - Return the maximum of both choices
- Base case: if index == n, return 0 (no more elements to consider)
- The answer is lis(0, -1)
Code
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
return solve(nums, 0, -1);
}
private:
int solve(vector<int>& nums, int index, int prevIndex) {
if (index == nums.size()) return 0;
// Choice 1: Skip current element
int skip = solve(nums, index + 1, prevIndex);
// Choice 2: Include current element (if valid)
int include = 0;
if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
include = 1 + solve(nums, index + 1, index);
}
return max(skip, include);
}
};class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
def solve(index: int, prev_index: int) -> int:
if index == len(nums):
return 0
# Choice 1: Skip current element
skip = solve(index + 1, prev_index)
# Choice 2: Include current element (if valid)
include = 0
if prev_index == -1 or nums[index] > nums[prev_index]:
include = 1 + solve(index + 1, index)
return max(skip, include)
return solve(0, -1)class Solution {
public int lengthOfLIS(int[] nums) {
return solve(nums, 0, -1);
}
private int solve(int[] nums, int index, int prevIndex) {
if (index == nums.length) return 0;
// Choice 1: Skip current element
int skip = solve(nums, index + 1, prevIndex);
// Choice 2: Include current element (if valid)
int include = 0;
if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
include = 1 + solve(nums, index + 1, index);
}
return Math.max(skip, include);
}
}Complexity Analysis
Time Complexity: O(2^n)
At each index, we make two recursive calls (include or skip). This creates a binary recursion tree of depth n, giving up to 2^n total calls. Many of these calls solve the same subproblems, but without memoization they are all recomputed.
Space Complexity: O(n)
The recursion stack goes at most n levels deep (one call per array element). No additional data structures are used.
Why This Approach Is Not Efficient
The brute force has O(2^n) time complexity. With n up to 2500, this means roughly 2^2500 operations — a number so astronomically large that even the fastest computers in the universe could not finish within the age of the universe.
The fundamental problem is that we solve the same subproblems repeatedly. For example, 'what is the longest increasing subsequence starting from index 5 with the last included element at index 3?' might be computed dozens of times through different recursion paths.
Key insight: the state of our recursion is fully determined by just two values — the current index and the index of the previous element included. There are at most n × n distinct (index, prevIndex) combinations. If we store (memoize) the result of each combination the first time we compute it, we avoid all redundant work. This is the idea behind Dynamic Programming.
Better Approach - Dynamic Programming (Tabulation)
Intuition
Instead of the top-down recursive approach, we can solve this bottom-up. The key idea is:
Define dp[i] = the length of the longest increasing subsequence that ends at index i (with nums[i] as its last element).
Why 'ends at index i'? Because by fixing the ending element, we can build up our answer incrementally. For each index i, we look at all previous indices j where j < i and nums[j] < nums[i]. If such a j exists, then we can extend the LIS that ends at j by appending nums[i] to it. So dp[i] = max(dp[j] + 1) for all valid j.
If no such j exists (no smaller element before i), then nums[i] starts its own subsequence of length 1. So every dp[i] is initialized to 1.
The final answer is the maximum value across the entire dp array, because the longest increasing subsequence could end at any index.
Think of it like building a chain. For each link (element), you look at all shorter chains that end with a smaller value, pick the longest one, and extend it by one link.
Step-by-Step Explanation
Let's trace through with nums = [10, 9, 2, 5, 3, 7, 101, 18]:
Initialize dp = [1, 1, 1, 1, 1, 1, 1, 1] (every element starts a subsequence of length 1).
Step 1: i=0, nums[0]=10. No elements before it. dp[0] = 1.
Step 2: i=1, nums[1]=9. Check j=0: nums[0]=10 > 9, not smaller. No valid j. dp[1] = 1.
Step 3: i=2, nums[2]=2. Check j=0: 10 > 2, no. Check j=1: 9 > 2, no. dp[2] = 1.
Step 4: i=3, nums[3]=5. Check j=0: 10 > 5, no. Check j=1: 9 > 5, no. Check j=2: 2 < 5 ✓ → dp[3] = max(1, dp[2]+1) = max(1, 2) = 2. dp[3] = 2.
Step 5: i=4, nums[4]=3. Check j=0: 10 > 3, no. j=1: 9 > 3, no. j=2: 2 < 3 ✓ → dp[4] = max(1, dp[2]+1) = 2. j=3: 5 > 3, no. dp[4] = 2.
Step 6: i=5, nums[5]=7. Check j=0: 10 > 7, no. j=1: 9 > 7, no. j=2: 2 < 7 ✓ → dp[5] = max(1, 2) = 2. j=3: 5 < 7 ✓ → dp[5] = max(2, dp[3]+1) = max(2, 3) = 3. j=4: 3 < 7 ✓ → dp[5] = max(3, dp[4]+1) = max(3, 3) = 3. dp[5] = 3.
Step 7: i=6, nums[6]=101. All previous elements are smaller. Best: dp[5]+1 = 4. dp[6] = 4.
Step 8: i=7, nums[7]=18. Check all j: best comes from j=5 (7<18, dp[5]=3) → dp[7] = 4. Also j=3 (5<18, dp[3]=2) and j=4 (3<18, dp[4]=2). Max is dp[5]+1=4. dp[7] = 4.
Final dp: [1, 1, 1, 2, 2, 3, 4, 4]. Maximum = 4.
DP Tabulation — Building LIS Lengths Bottom-Up — Watch how we fill the dp array left to right, checking all previous elements to find the longest increasing subsequence ending at each position.
Algorithm
- Create a dp array of size n, initialized to all 1s
- For each index i from 1 to n-1:
a. For each index j from 0 to i-1:- If nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1)
- Return the maximum value in the dp array
Code
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int maxLen = 0;
for (int val : dp) {
maxLen = Math.max(maxLen, val);
}
return maxLen;
}
}Complexity Analysis
Time Complexity: O(n²)
The outer loop runs n times. For each i, the inner loop runs up to i times, checking all previous elements. Total operations: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2, which is O(n²). With n up to 2500, this is about 3.1 million operations — fast enough to pass within time limits.
Space Complexity: O(n)
We use a single dp array of size n. No recursion stack is needed since this is an iterative bottom-up approach.
Why This Approach Is Not Efficient
The O(n²) DP approach works within the constraints (n ≤ 2500 gives ~3 million operations), but the problem explicitly asks: 'Can you come up with an O(n log n) algorithm?'
The bottleneck in the DP approach is the inner loop: for each element, we scan ALL previous elements to find the best predecessor. This linear scan is wasteful because we do not need to check every previous element — we only need to know the smallest possible ending value for each subsequence length.
Key insight: instead of tracking dp[i] (LIS length ending at each index), we can maintain a 'tails' array where tails[k] stores the smallest possible tail (ending value) of any increasing subsequence of length k+1. This array is always sorted, which means we can use binary search to find where each new element fits — reducing the inner loop from O(n) to O(log n).
Optimal Approach - Binary Search (Patience Sorting)
Intuition
Imagine you are playing a card game called Patience (Solitaire). You lay cards in a row one by one. For each card, you follow one rule:
- Place the card on the leftmost pile whose top card is greater than or equal to the current card.
- If no such pile exists, start a new pile.
The number of piles at the end equals the length of the longest increasing subsequence. This is not a coincidence — it is a proven mathematical result.
In our algorithm, instead of literal piles, we maintain an array called 'tails'. tails[i] represents the smallest possible ending value of an increasing subsequence of length i+1 discovered so far.
Why 'smallest possible ending value'? Because the smaller the ending value, the more room there is to extend the subsequence with future elements. If we have two increasing subsequences of length 3, one ending in 7 and one ending in 15, the one ending in 7 is strictly better — any element that extends the subsequence ending in 15 also extends the one ending in 7, but not vice versa.
A critical property: the tails array is always sorted in increasing order. This means for each new element, we can use binary search to find the correct position — either replacing an existing entry (keeping the tails array optimal) or extending it (growing the LIS length by 1).
Specifically, for each element x:
- If x is larger than all elements in tails, append it (LIS grows by 1).
- Otherwise, find the leftmost element in tails that is ≥ x and replace it with x (this keeps the subsequence endings as small as possible without changing any subsequence lengths).
Step-by-Step Explanation
Let's trace through nums = [10, 9, 2, 5, 3, 7, 101, 18]:
Step 1: Process 10. tails is empty. Append 10. tails = [10]. LIS length = 1.
Step 2: Process 9. Binary search in tails for leftmost value ≥ 9. Found 10 at index 0. Replace: tails[0] = 9. tails = [9]. LIS length = 1.
- Why? A subsequence of length 1 ending in 9 is better than one ending in 10, because 9 is smaller and easier to extend.
Step 3: Process 2. Binary search for leftmost ≥ 2. Found 9 at index 0. Replace: tails[0] = 2. tails = [2]. LIS length = 1.
Step 4: Process 5. Binary search for leftmost ≥ 5. No value ≥ 5 in tails (only 2, which is < 5). So 5 is larger than all — append. tails = [2, 5]. LIS length = 2.
Step 5: Process 3. Binary search for leftmost ≥ 3. Found 5 at index 1. Replace: tails[1] = 3. tails = [2, 3]. LIS length = 2.
- Why? [2, 3] is a better length-2 subsequence than [2, 5] because 3 < 5.
Step 6: Process 7. 7 > 3 (last in tails). Append. tails = [2, 3, 7]. LIS length = 3.
Step 7: Process 101. 101 > 7. Append. tails = [2, 3, 7, 101]. LIS length = 4.
Step 8: Process 18. Binary search for leftmost ≥ 18. Found 101 at index 3. Replace: tails[3] = 18. tails = [2, 3, 7, 18]. LIS length = 4.
- Why? If future elements are between 18 and 101, we can now extend. The LIS length stays 4.
Result: Length of tails = 4. The LIS has length 4.
Note: tails = [2, 3, 7, 18] is NOT an actual LIS from the input. It represents the optimal tail values for subsequences of each length. An actual LIS is [2, 3, 7, 101] or [2, 5, 7, 101].
Binary Search Patience Sorting — Building the Tails Array — Watch how we process each element, using binary search to either extend the tails array (LIS grows) or replace an element to keep subsequence endings optimal.
Algorithm
- Initialize an empty array called tails
- For each element x in nums:
a. Binary search tails for the leftmost position where tails[pos] ≥ x
b. If no such position exists (x is larger than all elements in tails), append x to tails
c. Otherwise, replace tails[pos] with x - Return the length of tails
Code
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
for (int x : nums) {
// Binary search for leftmost position
// where tails[pos] >= x
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) {
// x is larger than all tails -> extend LIS
tails.push_back(x);
} else {
// Replace to keep tails optimal
*it = x;
}
}
return tails.size();
}
};import bisect
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
tails = []
for x in nums:
# Binary search for leftmost position
# where tails[pos] >= x
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
# x is larger than all tails -> extend LIS
tails.append(x)
else:
# Replace to keep tails optimal
tails[pos] = x
return len(tails)class Solution {
public int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int x : nums) {
// Binary search for leftmost position
// where tails[pos] >= x
int pos = Collections.binarySearch(tails, x);
if (pos < 0) pos = -(pos + 1);
if (pos == tails.size()) {
// x is larger than all tails -> extend LIS
tails.add(x);
} else {
// Replace to keep tails optimal
tails.set(pos, x);
}
}
return tails.size();
}
}Complexity Analysis
Time Complexity: O(n log n)
We iterate through all n elements. For each element, we perform a binary search on the tails array, which has at most n elements. Binary search runs in O(log n) time. Total: n elements × O(log n) per element = O(n log n).
This is a significant improvement over the O(n²) DP approach. For n = 2500, we go from ~3.1 million operations down to ~2500 × 11 ≈ 27,500 operations.
Space Complexity: O(n)
The tails array can grow to at most n elements (in the case where the entire input is strictly increasing). No additional data structures are used beyond the tails array.