Longest Increasing Subsequence

Medium Dynamic Programming 1D DP Original on LeetCode

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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(2^n)Each index branches into take and skip.
SpaceO(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.

  1. solve(i, prev) = longest subsequence using indices i..n-1 when the last taken index is prev (-1 for none).
  2. Skip: solve(i + 1, prev). Take (if prev == -1 or nums[prev] < nums[i]): 1 + solve(i + 1, i).
  3. 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;
    }
}

21D DP (ending at each index)

TimeO(n²)Every pair (j, i) with j < i is checked once.
SpaceO(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].

  1. Fill best with 1.
  2. For each i, for each j < i with nums[j] < nums[i]: best[i] = max(best[i], best[j] + 1).
  3. 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;
    }
}

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.