Longest increasing subsequence n log n: how it works

In this article

1. Before you start
2. Why interviewers ask this
3. Longest increasing subsequence n log n from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the coding interview questions and the patterns behind them learning path.

Why interviewers ask this

The problem starts as a simple question: given an array of numbers, how long is the longest strictly increasing subsequence? An interviewer can use it to separate three levels of answer. A first answer checks every earlier value for every position, which is quadratic. A second answer reaches n log n but cannot say why binary search is allowed. A strong answer states the invariant that keeps the search array sorted.

The question also tests care. Duplicates, the choice of search function and the difference between the length and the sequence itself are the places where a correct-looking solution quietly fails. A candidate who names those three traps before the interviewer asks shows the kind of attention the round rewards. The same habit of keeping an ordered structure while scanning appears in the monotonic stack, which keeps its entries in monotone order as it reads the array.

Longest increasing subsequence n log n from first principles

Subsequence

A subsequence is a sequence made by deleting zero or more elements from an array without changing the order of the rest. It is not a substring, because its elements do not have to sit next to each other. It is increasing when each element is larger than the one before it.

Tails array

A tails array is a list in which entry k holds the smallest last value of any increasing subsequence of length k plus one found so far, counting k from zero. It is sorted by construction, and its length is the answer.

Patience sorting

Patience sorting is a card-pile procedure that deals each value onto the leftmost pile whose top card is at least as large, or starts a new pile. The number of piles equals the length of the longest increasing subsequence (Kiyomi et al., 2017, Section 3).

In plain words

Deal cards one at a time from left to right. Put each card on the leftmost pile whose top card is at least as high. If no pile qualifies, start a new pile on the right. When the cards run out, count the piles. That count is the length of the longest increasing subsequence.

The analogy breaks in one place. A real pile keeps every card, but the algorithm keeps only each pile's top card, because the tops are enough to compute the length (Kiyomi et al., 2017, Section 3.2). The tops, read left to right, are the tails array. In one precise sentence: the algorithm scans the array once, keeps the smallest possible last value for each length, and returns how many lengths exist.

Step 1: Keep one smallest tail per length

Start with an empty tails array. Entry 0 will hold the smallest last value of any increasing subsequence of length one, entry 1 the smallest last value of any such subsequence of length two, and so on. Smaller is better, because a smaller last value leaves more room to extend the subsequence later.

Take the array 10, 9, 2, 5, 3, 7, 101, 18, the standard example of this problem. After reading 10 the tails array is [10]. The value 9 is also a subsequence of length one with a smaller end, so it takes 10's place and the array becomes [9]. Then 2 does the same.¹ The array never needs the old values, only the best end for each length. You now know what the array stores; the next step shows where each new value goes.

Step 2: Binary-search the first tail that is at least the value

The tails array is strictly increasing at all times, so a new value can be placed by binary search. The reason is short. Take any increasing subsequence of length k plus two and drop its last element. That leaves an increasing subsequence of length k plus one whose end is smaller. So the best tail for the shorter length is smaller than the best tail for the longer one. Kiyomi et al. (2017, Section 3.2) state the same fact for pile tops.

The search target is the first tail that is at least the new value. Python's bisect_left returns exactly that position, because its insertion point comes before any equal entries (Python documentation). Use it for a strictly increasing result. With the input 2, 2, 2, bisect_left gives a length of 1 and bisect_right gives 3, which is the non-decreasing answer, not the strict one.¹ The binary search runs on the tails array, which is sorted, never on the input, which is not.

Step 3: Append or replace, never insert

Once the position is known, one of two things happens. A value larger than every tail is appended to the tails array. A value that is not larger than every tail replaces the first tail that is at least as large. Replacing keeps the array sorted and keeps every length's tail as small as possible.

from bisect import bisect_left

def lis_length(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)      # x extends the longest subsequence so far
        else:
            tails[i] = x         # x is a smaller end for length i + 1
    return len(tails)

The replacement is a plain assignment, which takes constant time. Do not use insort here: the Python documentation warns that its O(log n) search is dominated by a linear-time insertion step. For the standard example, 5 appends, 3 replaces 5, then 7 and 101 append, and finally 18 replaces 101.¹ The array ends at [2, 3, 7, 18].

Step 4: Read the length, and know what the array is not

The length of the tails array is the length of the longest increasing subsequence. For the standard example that length is 4.¹ Each step cost one binary search over at most n entries, so the whole scan costs O(n log n) (Kiyomi et al., 2017, Section 3.2).

The tails array is not the subsequence itself. For the array 2, 8, 4, 9, 5, 1, 7, 6, 3 the final tails are [1, 3, 5, 6], yet in the input the 3 comes after the 5 and the 6, so that list is not a subsequence at all.¹ A true longest subsequence there is 2, 4, 5, 6. To recover it, store each value's index and, when you place it, the index of the tail just to its left. Following those links back from the last tail gives one valid sequence. Several different answers can tie; only the length is unique.

1 · Smallest tail per length2 · Binary-search the tail3 · Append or replace4 · Read the lengthReplay

Step-by-step description

1. The tails array starts empty.
2. 10 starts the array; 9 and 2 each replace the only tail.
3. Larger values are appended.
4. 18 replaces 101; the length is 4.

• A value larger than every tail is appended to the tails array.
• A value that is not larger than every tail replaces the first tail that is at least as large.
• The tails array stays sorted, so binary search finds that position.
• The length of the tails array is the length of the longest increasing subsequence.

Worked example

Run the algorithm on 10, 9, 2, 5, 3, 7, 101, 18. The tails array after each value is [10], [9], [2], [2, 5], [2, 3], [2, 3, 7], [2, 3, 7, 101] and [2, 3, 7, 18], so the length is 4.¹ Four values extend the array (10, 5, 7 and 101), and the other four (9, 2, 3 and 18) each replace a tail. The script also ran the method against the quadratic version on 500 seeded random arrays with repeated values, and the lengths matched every time.¹

The speed gain is large. At 10,000 values the pair method makes 49,995,000 checks and n log2 n is 132,877.¹ The ratio of n(n−1)/2 to n log2 n is about 376, though n log2 n is a growth bound rather than an exact count of the tails method's steps.¹ The chart below shows three sizes.

Text description of the diagram

• At 10,000 values the pair method makes 49,995,000 checks and n log2 n is 132,877.
• The pair method grows with the square of the length, while n log2 n grows only a little faster than the length.

Trade-offs and edge cases

The baseline is dynamic programming. Dynamic programming is a method that solves a problem by storing answers to smaller versions of it. Here the stored answer is the best subsequence length ending at each position: dp[i] is 1 plus the largest dp[j] over earlier positions j with nums[j] < nums[i], or 1 if there is none, and the answer is the largest dp[i]. The pair method scans all earlier values for every value. The tails method binary-searches the tails array for every value. Both use memory proportional to n, and both need a predecessor array to return the sequence.

Text description of the diagram

• The pair method scans all earlier values for every value.
• The tails method binary-searches the tails array for every value.

Can you beat n log n?

Not with comparisons alone. Fredman (1975) showed that about n log₂ n − n log₂ log₂ n + O(n) comparisons are necessary and sufficient to compute the length, so n log n is best possible up to lower-order terms. When the answer has length k, the tails array has at most k entries, so each search costs O(log k) and the total is O(n log k). When the values are integers from a bounded range, Crochemore and Porat (2010) give O(n log log k). So "n log n is optimal" is true for comparison-based algorithms only.

Non-decreasing and other variants

If equal values may repeat in the subsequence, switch to bisect_right; the rest is unchanged. The same pattern is reused when the problem is turned into "stack boxes" or "nested envelopes" by sorting first: sort by width ascending and, for equal widths, height descending, then run the strict LIS on the heights. Sorting before a scan also drives the merge intervals solution.

How to answer it in an interview

The spoken structure: name the quadratic baseline, state the tails invariant, describe append or replace, give the cost, then name the length versus sequence trap.

Common mistakes

• "The tails array is the longest increasing subsequence." (wrong) The final tails can be out of order in the input. (right) "The length of the array is the answer; for the sequence I keep predecessor links."
• "I use bisect_right because it is the usual one." (wrong) It counts equal values as extending, which gives the non-decreasing answer. (right) "For a strict result I use bisect_left."
• "I binary-search the input array." (wrong) The input is not sorted. (right) "I search the tails array, which is sorted by construction."
• "I use insort to keep the list sorted." (wrong) Insertion in the middle costs linear time and breaks the bound. (right) "I replace a tail in place, which is constant time."
• "A subsequence has to be contiguous." (wrong) That describes a substring; a sliding-window problem such as the longest substring without repeating characters has different rules. (right) "A subsequence may skip elements."

Follow-up questions

What is the time complexity of the longest increasing subsequence in O(n log n)?

The scan visits n values and each does one binary search over at most n tails, so the time is O(n log n) and the extra space is O(n). The quadratic pair method needs 49,995,000 checks at 10,000 values.¹

How do you return the actual subsequence, not just the length?

Store, for every value, the index of the tail to its left when it is placed, and also the index of each length's current tail. After the scan, start from the last tail and follow the stored links backward, then reverse the list. This costs O(n) extra space.

How do you handle a non-decreasing subsequence?

Replace bisect_left with bisect_right. Equal values then extend the array instead of replacing a tail, as the 2, 2, 2 example shows.¹ Python's bisect functions are a common topic in Python interview questions.

Can you beat n log n?

For comparison-based algorithms, no: Fredman's bound shows that n log n is best possible up to lower-order terms. For integers from a bounded range, faster algorithms are known (Crochemore and Porat, 2010); the comparison bound itself is from Fredman (1975).

How is the longest increasing subsequence related to the longest common subsequence?

The longest common subsequence (LCS) of two strings is the longest sequence that appears, in order, in both. The LIS is a special case: it is the LCS of an array and a monotonically increasing sequence (Andoni et al., 2021). Other array problems where a stored structure replaces a nested loop include subarray sum equals k and the heap-versus-sort trade-off in k closest points to origin.

Sources

1. Space-Efficient Algorithms for Longest Increasing Subsequence (arXiv 1712.09230) — arXiv (Kiyomi, Ono, Otachi, Schweitzer, Tarui), 27 Dec 2017
2. bisect: Array bisection algorithm — Python Software Foundation documentation, 26 Oct 2026
3. On computing the length of longest increasing subsequences — Discrete Mathematics 11(1) (Fredman, 1975), abstract, 1 Jan 1975
4. Computing a longest increasing subsequence of length k in time O(n log log k) — Information and Computation 208(9) (Crochemore and Porat, 2010), 1 Sep 2010
5. Estimating the Longest Increasing Subsequence in Nearly Optimal Time (arXiv 2112.05106) — arXiv (Andoni, Nosatzki, Sinha, Stein), 1 Dec 2021