Longest Increasing Subsequence
Longest Increasing Subsequence is a medium dynamic programming problem solved with the 1d dp pattern.
The best approach, optimal (tails + binary search), runs in O(n log n) time and O(n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (pick / not pick) up.
Problem
Given an integer array nums, return the length of its longest strictly increasing subsequence.
A subsequence keeps some of the elements (possibly all) in their original order and drops the rest; the kept elements do not need to be next to each other.
Examples
Example 1
- Input
nums = [4,1,8,2,6,3,9]- Output
4- Why
- One longest choice is 1, 2, 3, 9 (another is 1, 2, 6, 9).
Example 2
- Input
nums = [6,6,6]- Output
1- Why
- The values must strictly increase, so equal values cannot be chained.
Example 3
- Input
nums = [10,20,5,30,1,40]- Output
4- Why
- 10, 20, 30, 40 skips the 5 and the 1.
Constraints
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (pick / not pick) | O(2^n) | O(n) |
| 1D DP (ending at each index) | O(n²) | O(n) |
| Optimal (tails + binary search) | O(n log n) | O(n) |
1Brute force (pick / not pick)
O(2^n)Each index branches into take and skip.O(n)Recursion depth is n.Walk the array and, at each index, either take the value (only allowed if it is larger than the last value taken) or skip it. Return the best length over all choices.
- solve(i, prev) = longest subsequence using indices i..n-1 when the last taken index is prev (-1 for none).
- Skip: solve(i + 1, prev). Take (if prev == -1 or nums[prev] < nums[i]): 1 + solve(i + 1, i).
- Return the larger; solve(n, prev) = 0.
class Solution {
public int lengthOfLIS(int[] nums) {
return solve(nums, 0, -1);
}
private int solve(int[] nums, int i, int prev) {
if (i == nums.length) return 0;
int best = solve(nums, i + 1, prev);
if (prev == -1 || nums[prev] < nums[i])
best = Math.max(best, 1 + solve(nums, i + 1, i));
return best;
}
}class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
def solve(i: int, prev: int) -> int:
if i == n:
return 0
best = solve(i + 1, prev)
if prev == -1 or nums[prev] < nums[i]:
best = max(best, 1 + solve(i + 1, i))
return best
return solve(0, -1)class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
return solve(nums, 0, -1);
}
private:
int solve(vector<int>& nums, int i, int prev) {
if (i == (int)nums.size()) return 0;
int best = solve(nums, i + 1, prev);
if (prev == -1 || nums[prev] < nums[i])
best = max(best, 1 + solve(nums, i + 1, i));
return best;
}
};function lengthOfLIS(nums) {
const n = nums.length;
function solve(i, prev) {
if (i === n) return 0;
let best = solve(i + 1, prev);
if (prev === -1 || nums[prev] < nums[i])
best = Math.max(best, 1 + solve(i + 1, i));
return best;
}
return solve(0, -1);
}21D DP (ending at each index)
O(n²)Every pair (j, i) with j < i is checked once.O(n)One length per index.best[i] is the longest increasing subsequence that ends at index i. It is 1 on its own, or one more than any best[j] with j < i and a smaller value. The answer is the largest best[i].
- Fill best with 1.
- For each i, for each j < i with nums[j] < nums[i]: best[i] = max(best[i], best[j] + 1).
- Return the maximum of best.
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length, ans = 0;
int[] best = new int[n];
for (int i = 0; i < n; i++) {
best[i] = 1;
for (int j = 0; j < i; j++)
if (nums[j] < nums[i]) best[i] = Math.max(best[i], best[j] + 1);
ans = Math.max(ans, best[i]);
}
return ans;
}
}class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
best = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i] and best[j] + 1 > best[i]:
best[i] = best[j] + 1
return max(best)class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size(), ans = 0;
vector<int> best(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i]) best[i] = max(best[i], best[j] + 1);
ans = max(ans, best[i]);
}
return ans;
}
};function lengthOfLIS(nums) {
const n = nums.length;
const best = new Array(n).fill(1);
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++)
if (nums[j] < nums[i]) best[i] = Math.max(best[i], best[j] + 1);
ans = Math.max(ans, best[i]);
}
return ans;
}3Optimal (tails + binary search)
O(n log n)One binary search over at most n tails per element.O(n)The tails array. Note it is not itself a valid subsequence; only its length matters.Keep tails, where tails[k] is the smallest last value seen so far of any increasing subsequence of length k + 1. It is always strictly increasing. For each value, find the first tail that is greater than or equal to it: replace that tail with the value (a cheaper ending for that length), or append the value if every tail is smaller (a new, longer subsequence). The length of tails is the answer.
- tails = empty list.
- For each x: binary search the first index k with tails[k] >= x.
- If k == tails.size(), append x; otherwise set tails[k] = x.
- Return tails.size().
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int lo = 0, hi = size;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == size) size++;
}
return size;
}
}class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for x in nums:
k = bisect.bisect_left(tails, x)
if k == len(tails):
tails.append(x)
else:
tails[k] = x
return len(tails)class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return tails.size();
}
};function lengthOfLIS(nums) {
const tails = [];
for (const x of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
}
return tails.length;
}Edge cases to test
- A single element (answer 1)
- All values equal (answer 1)
- Strictly decreasing array (answer 1)
- Already strictly increasing array (answer n)
- Negative values
Hints
Hint 1
Let best[i] be the length of the longest increasing subsequence that ends exactly at index i. How does it relate to earlier indices?
Hint 2
best[i] = 1 + max(best[j]) over j < i with nums[j] < nums[i]. That gives an O(n²) solution.
Hint 3
For O(n log n), keep tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. That array is sorted, so each new value can find its place with binary search.
FAQ
What is the best time complexity for Longest Increasing Subsequence?
Optimal (tails + binary search) runs in O(n log n) time and O(n) extra space. One binary search over at most n tails per element.
Which pattern does Longest Increasing Subsequence use?
It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).
Is there a brute force solution for Longest Increasing Subsequence?
Yes. Brute force (pick / not pick) takes O(2^n) time and O(n) space. Walk the array and, at each index, either take the value (only allowed if it is larger than the last value taken) or skip it.
Which edge cases should I test for Longest Increasing Subsequence?
A single element (answer 1); All values equal (answer 1); Strictly decreasing array (answer 1); Already strictly increasing array (answer n); Negative values.