Longest Increasing Subsequence

The problem

Given an array of integers nums, return the length of its longest strictly increasing subsequence. A subsequence keeps some of the numbers in their original order, and may skip any others. Strictly increasing means each number is bigger than the one before it.

Example 1

Input: nums = [3, 1, 8, 2, 5, 9, 4]

Output: 4

1, 2, 5, 9 skips the 3, the 8 and the 4. No increasing subsequence has 5 numbers.

nums

30118223549546

Example 2

Input: nums = [7, 7, 7]

Output: 1

Equal numbers do not count as increasing, so the best is a single 7.

Example 3

Input: nums = [9, 4, 6, 2, 7]

Output: 3

4, 6, 7.

Constraints

• 1 ≤ nums.length ≤ 2500 (call it n)
• −10⁴ ≤ nums[i] ≤ 10⁴

Clarifying questions

Must the numbers be next to each other?

No. A subsequence may skip numbers, but must keep their order.

Do equal numbers count as increasing?

No. It must be strictly increasing.

Do we return the subsequence or its length?

Only the length.

Is there a faster way than O(n²)?

Yes, O(n log n). The follow-up usually asks for it.

Spot the pattern

The longest run that ends at a number is one more than the longest run ending at some smaller number before it. Answers built from earlier answers are dynamic programming. The faster version keeps a different kind of summary, sorted so that a binary search can place each new number.

Solutions

Table of runsO(n²)Smallest tailsO(n log n)

Show all

There is no brute force tab. Trying every subsequence means 2ⁿ of them, which is hopeless even for 30 numbers, and the table below is the natural first answer.

Table of runs O(n²)

The idea

Let longest_ending_at[i] be the length of the longest increasing subsequence that ends at nums[i]. On its own, nums[i] is a run of length 1. It can also be added to any run that ends at a smaller number before it. So:

longest_ending_at[i] = 1 + the largest longest_ending_at[j] over all j < i with nums[j] < nums[i], or 1 if there is none.

The answer is the largest value in longest_ending_at, because the best run ends somewhere.

Why it is correct: take the best run ending at nums[i]. Without its last number, it is a run ending at some smaller nums[j] before it, and longest_ending_at[j] is at least that long. The loop over j tries them all.

Walkthrough

nums

30118223549546

longest_ending_at

0123456

1. longest_ending_at = [1] * len(nums)
2. for i in 0 .. len(nums) - 1:
3. for j in 0 .. i - 1:
4. if nums[j] < nums[i]:
5. longest_ending_at[i] = max(longest_ending_at[i], longest_ending_at[j] + 1)
6. return max(longest_ending_at)

longest_ending_at[i] will be the length of the longest increasing subsequence that ends exactly at nums[i]. Each number on its own is a run of length 1.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Table: longestEndingAt[i] is the longest increasing subsequence that ends at nums[i].
    // It extends the best earlier one with a smaller last number. O(n²) time, O(n) space.
    public int lengthOfLIS(int[] nums) {
        int[] longestEndingAt = new int[nums.length];
        int best = 0;
        for (int i = 0; i < nums.length; i++) {
            longestEndingAt[i] = 1;
            for (int j = 0; j < i; j++) {
                // nums[i] can follow any smaller number that came before it.
                if (nums[j] < nums[i])
                    longestEndingAt[i] = Math.max(longestEndingAt[i], longestEndingAt[j] + 1);
            }
            best = Math.max(best, longestEndingAt[i]);
        }
        return best;
    }
}

Big O

Time O(n²)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The inner loop does one comparison and maybe one max. That is a fixed job, so each run of the inner loop counts as 1 step.

   1. longest_ending_at = [1] * len(nums)
   2. for i in 0 .. len(nums) - 1:
   3. for j in 0 .. i - 1:
   4. if nums[j] < nums[i]:
   5. longest_ending_at[i] = max(longest_ending_at[i], longest_ending_at[j] + 1)
   6. return max(longest_ending_at)

2. 2 Count the runs on Example 1

   The table has one column per i. Number i looks back at the i numbers before it.

   0 + 1 + 2 + 3 + 4 + 5 + 6 = 21 runs.

   i	0	1	2	3	4	5	6
   inner runs	0	1	2	3	4	5	6

   total

   0 + 1 + 2 + 3 + 4 + 5 + 6 = 21 runs

3. 3 Write the count for any n

   0 + 1 + … + (n − 1) = n × (n − 1) / 2 runs

   Check it with Example 1: 7 × 6 / 2 = 21. That matches the count.

4. 4 Keep only the part that grows fastest

   That is n² / 2 − n / 2. Drop the − n / 2 and the 1/2. What is left is n². For 2500 numbers, about 3 million steps: fine here, but the follow-up wants better.

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The longest_ending_at table has n slots. So the space is O(n).

   longest_ending_at (n)

Smallest tails O(n log n)

The idea

The table looks back at every earlier number. Instead, keep a short summary called tails:

tails[k] is the smallest number that can end an increasing run of length k + 1, among the numbers seen so far.

A smaller ending is always better, because more numbers can follow it. And tails is always sorted: a run of length k + 1 contains a run of length k that ends at an even smaller number.

For each new number, find the first tail that is not smaller than number, with a binary search.

• If there is none, number is bigger than every tail. It extends the longest run, so append it.
• Otherwise, replace that tail with number. A run of that length can now end at number, which is no bigger.

At the end, the number of tails is the length of the longest run.

Why it is correct: each step keeps the rule “tails[k] is the smallest possible end of a run of length k + 1” true. number can follow any run whose end is smaller than number, so the longest run it can extend is the one just before the first tail that is not smaller.

Walkthrough

nums

30118223549546

tails

0

1. tails = []
2. for number in nums:
3. low = first position with tails[low] >= number # binary search
4. if low == len(tails): tails.append(number)
5. else: tails[low] = number
6. return len(tails)

tails[k] holds the smallest number that can end an increasing run of length k + 1, among the numbers seen so far. A smaller ending is better, because more numbers can follow it. tails is always sorted.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Smallest tails with binary search: tails[k] is the smallest last number of
    // any increasing run of length k + 1 seen so far. It stays sorted. O(n log n) time, O(n) space.
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int number : nums) {
            // Find the first tail that is not smaller than x.
            int low = 0, high = size;
            while (low < high) {
                int middle = (low + high) >>> 1;
                if (tails[middle] < number) low = middle + 1;
                else high = middle;
            }
            // Past the end: x makes a longer run. Otherwise x is a smaller tail for that length.
            tails[low] = number;
            if (low == size) size++;
        }
        return size;
    }
}

Big O

Time O(n log n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The outer loop runs once per number and does a fixed job after the search: 1 step. Inside, the binary search halves the range on each look, and each look is 1 step.

   1. tails = []
   2. for number in nums:
   3. low = first position with tails[low] >= number # binary search
   4. if low == len(tails): tails.append(number)
   5. else: tails[low] = number
   6. return len(tails)

2. 2 Count the runs on Example 1

   The table has one column per number. The first number needs no look, since tails is empty. The others need 1 or 2, because tails never holds more than 4 numbers here.

   7 numbers + 0 + 1 + 1 + 2 + 1 + 2 + 2 = 16 steps.

   x	3	1	8	2	5	9	4
   binary search looks	0	1	1	2	1	2	2

   total

   7 numbers + 0 + 1 + 1 + 2 + 1 + 2 + 2 = 16 steps

3. 3 Write the count for any n

   tails holds at most n numbers, and halving a range of n numbers until it is empty takes at most ⌈log₂(n + 1)⌉ looks:

   n + n × ⌈log₂(n + 1)⌉ steps

   Check it with Example 1: 7 + 7 × 3 = 28 at most. The real run used 16, because tails stayed short.

4. 4 Keep only the part that grows fastest

   Drop the lone n and round the log. What is left is n log n. For 2500 numbers, about 30,000 steps instead of 3 million.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   tails holds at most n numbers. So the space is O(n).

   tails (up to n)

Common mistake

Reading tails as the answer

tails is not a subsequence of the array. In Example 1 it ends as 1, 2, 4, 9, but 4 comes after 9 in the array. Only its length is meaningful. Rebuilding the real run needs extra bookkeeping.

Tested at the limits

2,000 random arrays of 1 to 10 numbers from −3 to 3, so equal neighbors, which do not count as increasing, are common. The table of runs, the smallest tails and a check that tries every subsequence gave the same answer every time.

Largest inputs	Result
2,500 numbers (the most allowed), all rising, so tails grows to its full length. Smallest tails.	Under 0.01 s, and about 0.02 MB of extra memory: the tails list of 2,500 numbers, O(n).
The same 2,500 rising numbers. Table of runs, about 3 million pairs.	0.2 s, and about 0.09 MB of extra memory. That is over 100 times slower than the smallest tails.