Longest Increasing Subsequence: O(n log n) Solution
The Longest Increasing Subsequence (LIS) problem asks a deceptively simple question: given an array of integers, find the length of the longest subsequence where elements are in strictly increasing...
Key Insights
- The O(n log n) LIS solution replaces linear search with binary search by maintaining a “tails” array where each position stores the smallest possible tail element for subsequences of that length.
- You don’t need to store actual subsequences—only the tail elements matter for determining where new elements can extend existing chains.
- Reconstructing the actual subsequence requires additional bookkeeping with parent pointers, which adds O(n) space but preserves the O(n log n) time complexity.
Introduction & Problem Definition
The Longest Increasing Subsequence (LIS) problem asks a deceptively simple question: given an array of integers, find the length of the longest subsequence where elements are in strictly increasing order. A subsequence doesn’t require contiguous elements—you can skip elements, but you must maintain relative order.
This problem appears everywhere. Version control systems use LIS variants to compute diffs efficiently. Patience sorting, a card-sorting algorithm, directly implements LIS. Bioinformatics uses it for DNA sequence alignment. Any time you need to find the longest monotonic trend in data, LIS is your tool.
The naive O(n²) dynamic programming solution works fine for small inputs. But when you’re processing sequences with millions of elements—genomic data, time series, or large file diffs—that quadratic complexity becomes a wall. Dropping to O(n log n) means the difference between seconds and hours.
Quick Recap: The O(n²) Dynamic Programming Approach
Before optimizing, let’s understand what we’re improving. The classic DP approach defines dp[i] as the length of the longest increasing subsequence ending at index i. For each element, we look at all previous elements and extend the best valid subsequence.
def lis_quadratic(nums: list[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [1] * n # Every element is a subsequence of length 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
The bottleneck is obvious: for each of the n elements, we scan all previous elements (up to n) to find the best predecessor. That nested loop gives us O(n²).
The insight for optimization: instead of asking “what’s the best subsequence I can extend?”, ask “where does this element fit among the current best candidates?” That question can be answered with binary search.
Key Insight: Binary Search + Active Lists
Here’s the mental model that makes the O(n log n) solution click. Imagine you’re maintaining multiple “active” increasing subsequences simultaneously. For each subsequence length k, you only care about the one with the smallest tail element—because a smaller tail gives you more room to extend.
Consider the array [10, 9, 2, 5, 3, 7, 101, 18]. Let’s trace through:
Process 10: tails = [10]
- First element starts a length-1 subsequence
Process 9: tails = [9]
- 9 < 10, so replace. A subsequence ending in 9 is "better" than one ending in 10
Process 2: tails = [2]
- 2 < 9, replace again. [2] beats [9] as a length-1 candidate
Process 5: tails = [2, 5]
- 5 > 2, so extend. Now we have length-1 ending in 2, length-2 ending in 5
Process 3: tails = [2, 3]
- 3 > 2 but 3 < 5. Replace 5 with 3. Length-2 subsequence ending in 3 is better
Process 7: tails = [2, 3, 7]
- 7 > 3, extend to length 3
Process 101: tails = [2, 3, 7, 101]
- 101 > 7, extend to length 4
Process 18: tails = [2, 3, 7, 18]
- 18 > 7 but 18 < 101. Replace 101 with 18
Final answer: length 4. The tails array always stays sorted, which is why binary search works.
Critical point: the tails array does NOT represent an actual subsequence. After processing, [2, 3, 7, 18] isn’t necessarily achievable from the original array in that order. It represents: “the best length-1 subsequence ends in 2, the best length-2 ends in 3, the best length-3 ends in 7, the best length-4 ends in 18.”
The O(n log n) Algorithm Implementation
The algorithm has two cases for each element:
- If the element is larger than all tails, append it (extend the longest subsequence)
- Otherwise, find the smallest tail that’s ≥ the element and replace it
Python’s bisect module handles the binary search. Use bisect_left for strictly increasing (finding where to insert to maintain sorted order).
from bisect import bisect_left
def length_of_lis(nums: list[int]) -> int:
if not nums:
return 0
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
Here’s the equivalent in Java:
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] tails = new int[nums.length];
int size = 0;
for (int num : nums) {
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
if (left == size) size++;
}
return size;
}
Why does replacement work? When we replace tails[pos] with a smaller value, we’re not invalidating any existing subsequence. We’re saying: “there exists a subsequence of length pos + 1 that ends in this smaller value.” Future elements have a better chance of extending it.
Reconstructing the Actual Subsequence
Returning just the length is often insufficient. To reconstruct the actual subsequence, track two pieces of information:
- The index in the original array for each tail position
- A parent pointer for each element showing which element precedes it in the LIS
from bisect import bisect_left
def find_lis(nums: list[int]) -> list[int]:
if not nums:
return []
n = len(nums)
tails = [] # Stores values (for binary search)
tail_indices = [] # Stores indices in original array
parent = [-1] * n # parent[i] = index of previous element in LIS ending at i
for i, num in enumerate(nums):
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
tail_indices.append(i)
else:
tails[pos] = num
tail_indices[pos] = i
# Set parent pointer
if pos > 0:
parent[i] = tail_indices[pos - 1]
# Reconstruct the subsequence by following parent pointers
lis = []
idx = tail_indices[-1] # Start from the last element of LIS
while idx != -1:
lis.append(nums[idx])
idx = parent[idx]
return lis[::-1] # Reverse to get correct order
# Example usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(find_lis(nums)) # Output: [2, 3, 7, 18] or [2, 3, 7, 101]
The parent pointer for element at index i points to the tail of the best subsequence of length pos - 1 at the time we processed nums[i]. This creates a chain we can follow backward.
Complexity Analysis & Edge Cases
Time Complexity: O(n log n). We iterate through n elements, and each binary search takes O(log n). The reconstruction phase is O(n) for following parent pointers.
Space Complexity: O(n). We store the tails array (at most n elements), tail_indices (at most n), and parent array (exactly n).
Handle these edge cases explicitly:
def length_of_lis_robust(nums: list[int]) -> int:
# Empty array
if not nums:
return 0
# Single element
if len(nums) == 1:
return 1
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
# Test edge cases
assert length_of_lis_robust([]) == 0 # Empty
assert length_of_lis_robust([5]) == 1 # Single element
assert length_of_lis_robust([5, 4, 3, 2, 1]) == 1 # All decreasing
assert length_of_lis_robust([2, 2, 2, 2]) == 1 # All equal
assert length_of_lis_robust([1, 2, 3, 4, 5]) == 5 # Already sorted
For non-decreasing subsequences (allowing duplicates), use bisect_right instead of bisect_left:
from bisect import bisect_right
def longest_non_decreasing(nums: list[int]) -> int:
tails = []
for num in nums:
pos = bisect_right(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
Variations & Practice Problems
Once you’ve mastered the basic LIS, these variations test deeper understanding:
Number of Longest Increasing Subsequences (LeetCode 673): Count how many distinct LIS exist. Requires tracking counts alongside lengths—still O(n log n) with careful bookkeeping using segment trees or BIT.
Russian Doll Envelopes (LeetCode 354): 2D LIS variant. Sort by width ascending, then by height descending within same width. Run LIS on heights. The descending sort prevents using multiple envelopes with the same width.
Longest Increasing Subsequence II (LeetCode 2407): Adds a constraint that adjacent elements differ by at most k. Requires segment tree for range maximum queries.
Minimum Operations to Make a Subsequence (LeetCode 1713): Given target and source arrays, find minimum insertions to make target a subsequence of source. Reduce to LIS using coordinate compression.
For practice, start with LeetCode 300 (basic LIS), then 673 (counting), then 354 (2D). The pattern recognition from these problems transfers directly to interview settings and real systems work.
The O(n log n) LIS algorithm is a perfect example of how rethinking the question—from “find the best predecessor” to “find the right bucket”—unlocks algorithmic improvements. Master this pattern, and you’ll recognize similar opportunities in other sequence problems.