Generated by Codex with GPT-5

Quick facts

What the problem is really asking

An array of integers is given. The task is to find the length of the longest subsequence whose values are strictly increasing.

The key word is subsequence, not subarray.

That means elements can be skipped, but their relative order must stay the same. So the real challenge is deciding which earlier values are worth keeping because they make it easier to extend the sequence later.

The first correct idea

The most natural dynamic programming state is:

dp[i] = length of the longest increasing subsequence that ends at index i

To compute dp[i], look at every earlier index j:

  • if nums[j] < nums[i], then nums[i] can extend an increasing subsequence ending at j
  • so dp[i] = max(dp[j] + 1) over all valid j

If no earlier value is smaller, then the best subsequence ending at i is just the element itself, so dp[i] = 1.

This gives a simple and correct solution:

  • Time: O(n^2)
  • Space: O(n)

It is a strong interview starting point because the state definition is easy to justify.

Why the optimal solution is faster

The O(n^2) DP asks, for every number, which earlier ending point is best.

The faster idea stops caring about the full subsequence and only keeps one summary per length:

smallest_tail_by_length[k] = the smallest possible tail value of an increasing subsequence of length k + 1 seen so far

That summary is enough because a smaller tail is always better than a larger tail for future extension.

For example, if there are two increasing subsequences of length 4 and one ends in 12 while the other ends in 7, the one ending in 7 is more useful. Any future number that can extend 12 can also extend 7, and some numbers can extend 7 but not 12.

How the tails array works

Process the numbers from left to right.

For each value:

  • if it is larger than every current tail, append it because a longer increasing subsequence has been found
  • otherwise replace the first tail that is greater than or equal to it

That replacement step is the whole trick.

It does not mean a real subsequence was greedily overwritten in the original array. It means the algorithm found a better representative tail for that subsequence length. The length stays the same, but the tail becomes smaller, which improves the chance of extending it later.

Because the tails array is always sorted, the replacement position can be found with binary search.

That gives:

  • Time: O(n log n)
  • Space: O(n)

For LeetCode 300, this is the best final answer.

How to derive this in an interview

A practical interview path is:

  1. Define the O(n^2) DP ending-at-i state because it matches the problem directly.
  2. Notice that the actual values of all candidate subsequences are not equally important. For each length, the smallest ending value is the most useful one to keep.
  3. Convert that observation into a tails array where each position stores the best tail seen for that length.
  4. Observe that tails stays sorted, so each update is a binary search.

That progression makes the optimal solution feel earned instead of magical.

Best approaches

There are two versions worth knowing.

The classic DP version:

  • Time: O(n^2)
  • Space: O(n)
  • Best use: deriving the recurrence and proving correctness clearly

The tails plus binary search version:

  • Time: O(n log n)
  • Space: O(n)
  • Best use: final implementation for the original problem

The important caveat is that the tails array directly gives the correct length, but by itself it does not reconstruct the actual subsequence. That is a common follow-up.

Python solution

The implementation below uses the optimal tails approach.

smallest_tail_by_length[length - 1] stores the smallest ending value seen so far for an increasing subsequence of that length. For each new number, the code finds the earliest tail that is greater than or equal to it:

  • if no such tail exists, the number extends the longest subsequence found so far
  • otherwise the number replaces that tail and becomes a better candidate ending value for the same length

This works because replacing a tail with a smaller value never hurts future extensions and can only help.

from bisect import bisect_left
from typing import List


def find_replacement_index(sorted_tails: List[int], value: int) -> int:
    """Return the first position whose tail is >= value."""
    return bisect_left(sorted_tails, value)


def length_of_longest_increasing_subsequence(numbers: List[int]) -> int:
    """
    Compute the LIS length in O(n log n) time.

    smallest_tail_by_length[length - 1] stores the smallest ending value
    seen so far for any increasing subsequence of that length.
    """
    smallest_tail_by_length: List[int] = []

    for number in numbers:
        replacement_index = find_replacement_index(
            smallest_tail_by_length,
            number,
        )

        if replacement_index == len(smallest_tail_by_length):
            smallest_tail_by_length.append(number)
            continue

        # A smaller tail for the same subsequence length is always better.
        smallest_tail_by_length[replacement_index] = number

    return len(smallest_tail_by_length)


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        """LeetCode entry point."""
        return length_of_longest_increasing_subsequence(nums)

Interview follow-ups

Can you return the actual subsequence, not just its length?

Yes. The usual answer is to keep parent pointers and the index of the best tail for each subsequence length. When a number extends or replaces a tail, record which earlier index it should point back to. After the scan finishes, walk backward from the last index of the longest subsequence and reverse the collected values. This works because the binary-search solution still identifies a valid predecessor chain if those indices are tracked carefully. The tradeoff is implementation complexity: the length-only solution is short and clean, while reconstruction requires extra arrays and more careful bookkeeping.

What changes if the problem asks for a non-decreasing subsequence instead of a strictly increasing one?

The high-level idea stays the same, but the binary-search condition changes. For a strictly increasing subsequence, a value replaces the first tail that is greater than or equal to it, which is why bisect_left is the right tool. For a non-decreasing subsequence, equal values are allowed to extend the sequence, so the replacement should happen at the first tail that is strictly greater than the current value, which corresponds to bisect_right. The complexity stays O(n log n), but the comparison rule must match the exact wording of the problem.

How would you count how many longest increasing subsequences there are?

The tails trick is excellent for the length, but it does not preserve enough information to count all optimal subsequences. The standard answer is a dynamic programming approach where each index keeps both the best length ending there and the number of ways to achieve that length. When nums[j] < nums[i], updating i depends on whether extending j creates a longer subsequence than previously known or ties the current best. This works because counting depends on combining many predecessor paths, not just keeping the smallest tail per length. The typical solution takes O(n^2) time and O(n) space, which is acceptable for the counting variant even though it is slower than the original length-only problem.