Introduction

For the general Longest Increasing Subsequence problem, O(n) is usually the wrong target. The standard optimal solution in the comparison model is O(n log n), and that is the result most people should aim to understand and implement.

That does not mean linear-time variants never exist. It means they require extra assumptions, such as bounded value ranges or specialized input structure. For arbitrary integer sequences, a true general O(n) LIS algorithm is not the normal answer.

The Problem Statement

Given an array, the LIS length is the longest subsequence whose values are strictly increasing while preserving original order. A subsequence is not required to be contiguous.

Example:

[10, 9, 2, 5, 3, 7, 101, 18]

One LIS is [2, 3, 7, 18], so the answer is 4.

The Classic O(n^2) Dynamic Programming Solution

The direct dynamic programming idea is:

• 'dp[i] = LIS length ending at index i'
• for each i, check all earlier j < i
• if arr[j] < arr[i], try extending dp[j]

1def lis_quadratic(nums):
2    if not nums:
3        return 0
4
5    dp = [1] * len(nums)
6
7    for i in range(len(nums)):
8        for j in range(i):
9            if nums[j] < nums[i]:
10                dp[i] = max(dp[i], dp[j] + 1)
11
12    return max(dp)
13
14print(lis_quadratic([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

This is easy to understand and perfectly fine for moderate input sizes. It is just not optimal.

The Standard O(n log n) Solution

The faster approach uses a tails array plus binary search. tails[k] stores the smallest possible tail value of an increasing subsequence of length k + 1.

1from bisect import bisect_left
2
3def lis_nlogn(nums):
4    tails = []
5
6    for x in nums:
7        i = bisect_left(tails, x)
8        if i == len(tails):
9            tails.append(x)
10        else:
11            tails[i] = x
12
13    return len(tails)
14
15print(lis_nlogn([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

This is the algorithm most interviewers and competitive programmers expect. It is fast, elegant, and broadly applicable.

Why General O(n) Is Not the Usual Answer

The key obstacle is that LIS needs order information across the sequence. In the general case, each new value may need to be compared against a dynamically changing frontier of best subsequence tails. That is why binary search appears naturally and why log n is hard to remove without additional assumptions.

If someone proposes a general O(n) algorithm for arbitrary inputs, the natural question is: what special structure is being exploited? Without extra structure, the usual answer remains O(n log n).

When Near-Linear Variants Can Exist

If values come from a small bounded range, data structures such as Fenwick trees or segment trees can make the complexity depend on value range instead of plain n. For example, a DP over compressed coordinates can run in O(n log V), where V is the number of distinct values.

That can feel close to linear if V is small, but it is not the same as a general unrestricted O(n) solution.

Similarly, if the input has special structure such as already sorted blocks or limited disorder, a tailored algorithm may do better in practice. Those are special cases, not the generic LIS result.

Common Pitfalls

Confusing subsequence with substring

LIS is about preserving order, not contiguity. If your algorithm only checks contiguous segments, you are solving a different problem.

Thinking tails stores the actual LIS

In the O(n log n) algorithm, tails helps compute the length, but it does not directly store a valid subsequence. Reconstructing the actual LIS requires parent pointers or additional bookkeeping.

Claiming O(n) after adding a tree structure

Fenwick trees and segment trees still cost logarithmic time per update or query. They are excellent tools, but they do not magically make the general problem linear.

Using the wrong binary search variant

For strictly increasing subsequences, bisect_left is usually correct. For non-decreasing variants, the search rule changes.

Summary

• The general LIS problem is not usually solved in O(n).
• The simple DP solution is O(n^2).
• The standard optimal comparison-based solution is O(n log n) using a tails array and binary search.
• Faster-looking variants need extra assumptions such as bounded value ranges or special input structure.
• If the goal is the general interview or production answer, learn the O(n log n) method first.