18 minute read

“Finding the longest upward trend in chaos.”

TL;DR

LIS starts with O(N^2) DP where dp[i] stores the LIS length ending at index i. The optimal O(N log N) solution maintains a tails array of smallest tail elements for each LIS length, using binary search (bisect_left) to find insertion points. This is equivalent to patience sorting from card games. The tails array length equals the LIS length, but it is not the actual subsequence. For reconstruction, track parent pointers. The same idea powers git diff --patience and the anchor-chaining step in whole-genome aligners, and it is a handy tool for aligning long transcripts.

1. Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], length = 4.

Example 2:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: [0, 1, 2, 3]

2. Approach 1: Dynamic Programming O(N^2)

Intuition:

  • Let dp[i] = length of LIS ending at index i.
  • For each i, look at all previous elements j < i.
  • If nums[j] < nums[i], we can extend the LIS ending at j by including nums[i].
  • dp[i] = max(dp[j] + 1) for all valid j.
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        dp = [1] * n  # Every element is an LIS 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)

Complexity:

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

3. Approach 2: Binary Search + Greedy O(N log N)

Key Insight:

  • Maintain an array tails where tails[i] is the smallest tail element of all increasing subsequences of length i+1.
  • For each new number, use binary search to find where it fits.

Why does this work?

  • If we want to build a longer LIS, we should keep the tail as small as possible.
  • Example: [4, 5, 1, 2, 3]
    • After processing [4, 5], tails = [4, 5].
    • 1 replaces 4 → tails = [1, 5]. 2 replaces 5 → tails = [1, 2].
    • 3 extends it → tails = [1, 2, 3], so the answer is 3.
    • Had we kept [4, 5] as the only candidate, 3 could not extend anything and we would answer 2.
import bisect
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        
        for num in nums:
            # Find the leftmost position where num can be placed
            pos = bisect.bisect_left(tails, num)
            
            if pos == len(tails):
                tails.append(num)  # Extend the LIS
            else:
                tails[pos] = num   # Replace to keep tail small
        
        return len(tails)

Complexity:

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

Both versions were checked against a brute-force enumeration on 2,000 random small arrays and agree on every case.

4. Why the Tails Array Stays Sorted

Binary search only works because tails is always sorted. Proof by induction:

  1. Base case: After the first element, tails = [nums[0]]. Sorted.
  2. Inductive step: Assume tails is sorted before processing x = nums[i], and let pos = bisect_left(tails, x).
    • If pos == len(tails), every entry is smaller than x, so appending keeps the order.
    • Otherwise bisect_left guarantees tails[pos-1] < x (when pos > 0) and x ≤ tails[pos]. After the replacement, tails[pos-1] < x ≤ old tails[pos] < tails[pos+1], so the array is still sorted.

5. Patience Sorting

The binary search approach is the card game patience sorting in disguise.

Game rules:

  1. Deal cards one by one.
  2. Place each card on the leftmost pile whose top card is greater than or equal to it.
  3. If no such pile exists, start a new pile on the right.

Connection to LIS:

  • Number of piles = length of the LIS.
  • In the order cards were placed (bottom to top), each pile is non-increasing.
  • The top cards of the piles, read left to right, are increasing. They are exactly the tails array.

6. Reconstructing the LIS

The binary search approach only gives the length. To get an actual sequence, remember which index currently ends each length, and give every element a pointer to its predecessor:

import bisect

def findLIS(nums):
    if not nums:
        return []
    n = len(nums)
    tails = []
    parent = [-1] * n  # Track predecessor
    tail_indices = []  # Index of the element that ends each tail
    
    for i, num in enumerate(nums):
        pos = bisect.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
        if pos > 0:
            parent[i] = tail_indices[pos - 1]
    
    # Backtrack to reconstruct LIS
    lis = []
    k = tail_indices[-1]
    while k != -1:
        lis.append(nums[k])
        k = parent[k]
    
    return lis[::-1]

print(findLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # [2, 3, 7, 18]

7. Common Mistakes and Pitfalls

1. Confusing subsequence with subarray:

  • Subarray: Contiguous (e.g., [2, 5, 3] in [1, 2, 5, 3, 7]).
  • Subsequence: Non-contiguous (e.g., [2, 3, 7]).
  • Fix: Clarify with the interviewer immediately.

2. Incorrect reconstruction:

  • Mistake: Printing the tails array.
  • Fact: tails is NOT the LIS. It stores the smallest tail for each length.
  • Example: For [2, 5, 3, 7, 1], tails ends as [1, 3, 7], which is not even a subsequence because 1 comes last. A real LIS is [2, 3, 7].
  • Fix: Use the parent array backtracking method.

3. Not handling duplicates:

  • “Strictly increasing” vs “non-decreasing”.
  • Strictly: nums[j] < nums[i], and bisect_left in the binary search version.
  • Non-decreasing: nums[j] <= nums[i], and bisect_right.

4. 2D LIS sorting order:

  • For envelopes (w, h), sorting w ascending and h ascending is wrong.
  • Why? [2, 3] and [2, 4]. If sorted ascending, we might pick both. But [2, 3] cannot fit into [2, 4] (width must be strictly greater).
  • Fix: Sort w ascending, h descending.

8. Variants

8.1 Longest Decreasing Subsequence

Solution 1: Reverse the condition in the DP.

nums = [10, 9, 2, 5]
n = len(nums)
dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if nums[j] > nums[i]:  # Changed from <
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))  # 3: [10, 9, 2] or [10, 9, 5]

Solution 2: Negate all numbers and find the LIS.

  • The LIS of [-10, -9, -2, -5] is the LDS of [10, 9, 2, 5].

8.2 Number of LIS (LeetCode 673)

Problem: Count how many different LIS exist.

Approach: Extend the DP to track counts.

def findNumberOfLIS(nums):
    n = len(nums)
    dp = [1] * n  # Length of LIS ending at i
    count = [1] * n  # Number of LIS ending at i
    
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                if dp[j] + 1 > dp[i]:
                    # Found a longer LIS
                    dp[i] = dp[j] + 1
                    count[i] = count[j]
                elif dp[j] + 1 == dp[i]:
                    # Found another LIS of same length
                    count[i] += count[j]
    
    max_len = max(dp)
    return sum(c for l, c in zip(dp, count) if l == max_len)

print(findNumberOfLIS([1, 3, 5, 4, 7]))  # 2

8.3 Russian Doll Envelopes (LeetCode 354)

Problem: You have envelopes (w, h). An envelope can fit into another if both width and height are strictly greater. Find the maximum nesting depth.

Insight: This is 2D LIS.

  1. Sort by width ascending, height descending (crucial!).
  2. Find the LIS on heights.

Why descending height?

  • If two envelopes have the same width, they can’t nest.
  • Sorting heights descending within a width means they can never both appear in one increasing subsequence.
def maxEnvelopes(envelopes):
    # Sort by width asc, height desc
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    
    # Extract heights
    heights = [h for w, h in envelopes]
    
    # Find LIS on heights (Approach 2)
    return Solution().lengthOfLIS(heights)

print(maxEnvelopes([[5, 4], [6, 4], [6, 7], [2, 3]]))  # 3

8.4 Longest Bitonic Subsequence

A sequence that first increases, then decreases.

  • Example: [1, 11, 2, 10, 4, 5, 2, 1] → [1, 2, 10, 4, 2, 1] (length 6).
def longestBitonicSubsequence(nums):
    n = len(nums)
    
    # LIS ending at i
    lis = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                lis[i] = max(lis[i], lis[j] + 1)
    
    # LDS starting at i
    lds = [1] * n
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            if nums[j] < nums[i]:
                lds[i] = max(lds[i], lds[j] + 1)
    
    # Max of lis[i] + lds[i] - 1
    return max(lis[i] + lds[i] - 1 for i in range(n))

print(longestBitonicSubsequence([1, 11, 2, 10, 4, 5, 2, 1]))  # 6

8.5 Weighted LIS

Each element has a value and a weight. Maximize the total weight of an increasing subsequence.

def weightedLIS(nums, weights):
    n = len(nums)
    dp = [0] * n  # Max weight ending at i
    
    for i in range(n):
        dp[i] = weights[i]  # At least include itself
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + weights[i])
    
    return max(dp)

print(weightedLIS([1, 101, 2, 3, 100], [1, 101, 2, 3, 100]))  # 106: [1, 2, 3, 100]

8.6 Other relatives

  • Longest Divisible Subset (LeetCode 368): the same O(N^2) DP after sorting, with the condition nums[i] % nums[j] == 0.
  • Longest alternating subsequence: elements alternate up and down, e.g. [1, 5, 3, 8, 6, 9] (length 6). Solved with two DP arrays (ending on an up step, ending on a down step).
  • All LIS: compute dp as in Approach 1, then backtrack from every index with dp[i] == max_len. The output can be exponential in size.

8.7 LIS with a Fenwick tree or segment tree

The O(N^2) DP asks “what is the best dp[j] among earlier elements with a smaller value?”. After compressing values to ranks 1..N, a Fenwick tree (or segment tree) over ranks answers that prefix-maximum query in O(log N), which gives O(N log N) overall. Unlike the tails trick, this version extends directly to weighted LIS and, by storing (length, count) pairs, to counting LIS (LeetCode 673) in O(N log N).

9. Theory

9.1 Connection to Longest Common Subsequence (LCS)

LIS reduces to LCS:

  1. Make a copy of nums, sort it and remove duplicates: sorted_nums.
  2. Find the Longest Common Subsequence of nums and sorted_nums.

sorted_nums is strictly increasing, so any common subsequence is strictly increasing too, and every increasing subsequence of nums is also a subsequence of sorted_nums. Thus LCS(nums, sorted_nums) == LIS(nums). The cost is O(N^2), slower than Approach 2, but the reduction also runs the other way: the Hunt-Szymanski LCS algorithm turns LCS into an LIS over matching position pairs.

9.2 Mirsky’s theorem and the patience piles

Define a partial order on the positions of the array: i precedes j when i < j and nums[i] < nums[j].

  • A chain (every pair comparable) is a strictly increasing subsequence.
  • An antichain (no pair comparable) is a non-increasing subsequence.

Mirsky’s theorem says the length of the longest chain equals the minimum number of antichains needed to partition the set. For sequences:

The length of the LIS equals the minimum number of non-increasing subsequences needed to cover the array.

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

  • LIS: [2, 3, 7, 18] (length 4).
  • Patience sorting builds exactly four piles, each non-increasing: [10, 9, 2], [5, 3], [7], [101, 18].

Patience sorting is a constructive proof: each pile is a non-increasing subsequence, and the number of piles equals the LIS length.

Its dual, Dilworth’s theorem, swaps the roles: the minimum number of chains needed to cover a poset equals the size of the largest antichain. For sequences, the minimum number of strictly increasing subsequences needed to cover the array equals the length of the longest non-increasing subsequence.

9.3 Lower bounds and faster special cases

  • Comparison model: Fredman (1975) showed that any algorithm that only compares elements needs Ω(N log N) comparisons, even just to compute the LIS length. Approach 2 is therefore optimal in that model.
  • Integer inputs: If values are integers (after coordinate compression they lie in [1, N]), the binary search can be replaced by a predecessor query on a van Emde Boas tree, giving O(N log log N) in the word-RAM model. The Hunt-Szymanski LCS work already used this idea for permutations. In practice the constant factors of vEB trees rarely pay off, and O(N log N) is what you should implement.

10. Where LIS Shows Up in Practice

10.1 Patience diff

Git’s default diff uses the Myers algorithm, which computes a shortest edit script (closely related to LCS). git diff --patience instead matches lines that occur exactly once in both files and keeps the largest set of those matches that appear in the same order in both files. That set is an LIS over line positions, computed with patience sorting, which is where the name comes from. It often gives more readable diffs when large blocks of code change.

10.2 Whole-genome alignment (MUMmer)

The original MUMmer aligner (Delcher et al., 1999) finds maximal unique matches (MUMs) between two genomes, sorts them by position in the first genome, and then picks the longest set of matches whose positions in the second genome also increase. That chaining step is a variant of LIS (it also accounts for match lengths and overlaps), and it runs in O(k log k) for k matches. The number of matches can be large, so the O(N log N) algorithm matters.

10.3 Aligning long transcripts

The same anchor-chaining trick works for speech data. Suppose you need to line up a long ASR transcript (with word timestamps) against a reference text, for example to cut a long recording into training segments:

  1. Find words or short n-grams that occur exactly once in both texts. Each match is a pair (position_in_hypothesis, position_in_reference).
  2. Sort the pairs by hypothesis position and take the LIS of the reference positions. Misrecognized or repeated words that would cross other matches drop out.
  3. The surviving matches are reliable anchors. Align the short gaps between them with ordinary edit distance or forced alignment.

Speech alignment is monotonic (time only moves forward), which is exactly the “same order in both sequences” constraint LIS enforces. For the dense, frame-level version of monotonic alignment, see Dynamic Time Warping in acoustic pattern matching.

10.4 Streaming monotonicity checks

The tails array can be updated one element at a time, so you can track the LIS length of a growing stream in O(log N) per element:

import bisect

class StreamingLIS:
    def __init__(self):
        self.tails = []
    
    def add(self, num):
        """Add number to stream and return the current LIS length"""
        pos = bisect.bisect_left(self.tails, num)
        
        if pos == len(self.tails):
            self.tails.append(num)
        else:
            self.tails[pos] = num
        
        return len(self.tails)
    
    def reset(self):
        """Reset for new sequence"""
        self.tails = []

s = StreamingLIS()
print([s.add(x) for x in [10, 12, 15, 11, 80, 85]])  # [1, 2, 3, 3, 4, 5]

The ratio “LIS length / window length” is a simple non-parametric measure of how monotonic a window of metrics is. Two caveats: an LIS is a subsequence, not a contiguous run, so a high score does not mean the values rose without interruption; and removing the oldest element from tails is not supported, so a sliding window needs a recompute per window or a different statistic (a trend filter or a moving average). For many independent sequences, the work parallelizes trivially, for example with multiprocessing.Pool().map(Solution().lengthOfLIS, sequences).

11. Performance

The asymptotic gap is large in practice. On N = 10,000 random integers with CPython 3.14 on a 2017 laptop CPU (Intel i5-7360U), the O(N^2) DP took about 3.6 s and the binary search version about 2 ms. Expect different absolute numbers on your machine; the ratio is the point.

12. Interview Pro Tips

  1. Recognize the pattern: “Longest”, “Increasing”, “Subsequence” → think LIS.
  2. Start with DP: Explain the O(N^2) solution first.
  3. Optimize: Move to binary search for O(N log N), and explain why tails stays sorted.
  4. Variants: Be ready to adapt (decreasing, 2D, count, weighted).
  5. Reconstruction: Know how to print the actual sequence.

13. Summary

Approach Time Space Notes
DP O(N^2) O(N) Simple, easy to extend (count, weights, divisibility)
Binary Search (tails) O(N log N) O(N) Optimal in the comparison model; length plus reconstruction via parents
Fenwick / segment tree O(N log N) O(N) Handles weighted and counting variants

LIS starts as a standard DP exercise, turns into a greedy binary search, and connects to card games, order theory, diff tools, genome alignment and transcript alignment. Both main approaches are exact; the difference is only running time, and the O(N log N) version is the one to know cold.

FAQ

Why does the binary search approach maintain a sorted tails array?

The tails array stores the smallest possible tail element for each increasing subsequence length. When bisect_left finds a position to replace, the new value is smaller than or equal to the old value at that position but larger than the value at the previous position, maintaining sorted order. Appending only happens for values larger than all existing entries.

Is the tails array the actual longest increasing subsequence?

No. The tails array stores optimal tail values for each length, not the actual LIS elements. For input [2,5,3,7,1], tails ends as [1,3,7], which is not a subsequence at all because 1 comes last. To reconstruct an actual LIS, maintain a parent array tracking predecessors during each update.

How does patience sorting relate to LIS?

In the patience sorting card game, each card is placed on the leftmost pile whose top card is greater than or equal to the current card. If no such pile exists, a new pile is started. The number of piles formed equals the LIS length. Each pile is non-increasing in the order cards were placed, and the top cards form an increasing sequence corresponding to the tails array.

What is the Russian Doll Envelopes problem and how does it use LIS?

Given envelopes with width and height, find the maximum nesting depth. Sort by width ascending and height descending, then find the LIS of heights only. Sorting height in descending order within the same width prevents two envelopes with identical widths from appearing in the same subsequence, since their heights will be in decreasing order.