Longest Increasing Subsequence: Patience Sorting

The longest increasing subsequence (LIS) problem asks: given a sequence of numbers, find the longest subsequence where each element is strictly greater than its predecessor. The subsequence doesn’t need to be contiguous—gaps are allowed as long as the ordering is preserved. A naive solution compares all pairs, giving O(n²) time; but a clever algorithm using patience sorting and binary search achieves O(n log n), transforming what’s often an interview showstopper into an elegant demonstration of optimizing beyond the obvious.

The key insight is that the minimum ending value for all increasing subsequences of length k can be tracked in a tails array. Processing each element, we binary search where it would fit in this array. Smaller ending values allow longer sequences to extend further, so we update only when we find a better (smaller) tail. The length of the tails array at the end is the LIS length.

Introduction

The longest increasing subsequence (LIS) problem asks a deceptively simple question: given a sequence of numbers, what is the longest subsequence where each element is strictly greater than its predecessor? The answer reveals an elegant algorithm that achieves O(n log n) time—dramatically better than the naive O(n²) comparison-based approach. This isn’t just a theoretical improvement; it’s the difference between solving problems with n up to 10⁵ versus being limited to n below a few thousand.

LIS appears in diverse applications: stacking boxes with dimensions, scheduling to maximize non-overlapping intervals, and even protein folding problems in computational biology. The key insight is that patience sorting—the same algorithm used to sort a deck of cards—naturally discovers the LIS length through the mechanics of binary search on a “tails” array. Each element placed into the right pile reveals how long an increasing sequence ending at that value can be.

This guide covers the O(n log n) patience sorting algorithm with full implementation details, explains why the tails array invariant holds, and shows how to reconstruct the actual subsequence when needed. You’ll understand the crucial difference between bisect_left and bisect_right for strict versus non-strict increasing sequences, and learn when the O(n²) DP approach is actually preferable despite its worse asymptotic complexity.

When to Use

LIS applies when:

• Box stacking problems — Stacking boxes where each has dimensions
• Maximum non-overlapping intervals — Finding largest subset of non-overlapping segments
• Hotel renovation planning — Maximum guests in hotel given check-in/check-out times
• Russian doll envelope problems — Nesting objects with multiple constraints
• Online judge problems with n up to 10⁵ — O(n²) too slow, need O(n log n)

When Not to Use

• When you need the actual subsequence, not just its length (the O(n log n) algorithm doesn’t directly reconstruct)
• Problems where elements are unique isn’t guaranteed (strict vs non-strict inequality matters)
• When O(n²) is fast enough for small inputs

Architecture: Patience Sorting + Binary Search

graph TD
    A["Input: arr = [3,1,4,2,5]"] --> B[Initialize tails array]
    B --> C[Process each element]
    C --> D{Insert position?}
    D -->|Binary search| E["Update tails[pos] = element"]
    E --> F{"tails[pos] updated?"}
    F -->|Yes| G[Length unchanged]
    F -->|"No (append)"| H[Length increases]
    G --> C
    H --> C
    C --> I["LIS length = len(tails)"]

Each element is placed at the position of the first tails element >= it. Smaller tails values leave more room for future elements to extend.

Implementation

O(n log n) LIS Using Binary Search

import bisect

def lis_length(nums):
    """
    Find LIS length in O(n log n) time using patience sorting.
    Returns the length of the longest increasing subsequence.
    """
    if not nums:
        return 0

    tails = []

    for num in nums:
        # Find position where num should be inserted
        pos = bisect.bisect_left(tails, num)

        if pos == len(tails):
            # num extends longest subsequence
            tails.append(num)
        else:
            # num improves (smaller) tail for length pos+1
            tails[pos] = num

    return len(tails)

Reconstruct Actual LIS

def lis_reconstruct(nums):
    """
    Find actual LIS in O(n log n) time.
    Returns one valid LIS (not necessarily unique).
    """
    if not nums:
        return []

    # Phase 1: Find LIS length and track positions
    tails = []
    tail_positions = []  # Which index in original nums ended each tail

    for i, num in enumerate(nums):
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
            tail_positions.append(i)
        else:
            tails[pos] = num
            tail_positions[pos] = i

    # Phase 2: Reconstruct by backtracking
    lis_length = len(tails)
    lis = [0] * lis_length
    prev_value = float('-inf')
    pos = len(tails) - 1

    # Find the actual LIS by tracing from the largest tail
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] < prev_value:
            continue
        if pos >= 0 and i == tail_positions[pos]:
            lis[pos] = nums[i]
            prev_value = nums[i]
            pos -= 1
            if pos < 0:
                break

    return lis

O(n²) DP Approach (for reference)

def lis_length_dp(nums):
    """
    O(n²) DP approach - easier to understand but slower.
    dp[i] = LIS length ending at index i.
    """
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n

    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)

Production Failure Scenarios

Failure	Cause	Mitigation
Wrong binary search variant	Using bisect_right instead of bisect_left	Use bisect_left for strictly increasing, bisect_right for non-decreasing
Off-by-one in reconstruction	Mismatched index tracking	Test carefully with duplicate values
Strict vs non-strict confusion	”Increasing” vs “non-decreasing”	Clarify problem: strictly increasing (<) or non-decreasing (<=)
Negative numbers	Not handling negative input correctly	Algorithm works for any comparable elements

Common Pitfalls / Anti-Patterns

1. Confusing bisect_left vs bisect_right — For strict increasing, use bisect_left; for non-decreasing (allow equal), use bisect_right
2. Not handling empty input — LIS of empty array is 0
3. Reconstruction complexity — The O(n log n) algorithm finds length only; reconstruction requires additional tracking
4. Multiple valid LIS — Algorithm returns one valid LIS, not necessarily the lexicographically smallest

Trade-off Analysis

Approach	Time Complexity	Space Complexity	Finds Length	Reconstructs LIS	Counts LIS
O(n²) DP	O(n²)	O(n)	Yes	Yes	Yes
O(n log n) Patience Sorting	O(n log n)	O(n)	Yes	With tracking	No
O(n log n) Fenwick Tree	O(n log n)	O(n)	Yes	Yes	Yes

Choosing the Right Approach

• Use O(n²) DP when n ≤ 1000 and you need the actual subsequence with minimum code complexity
• Use O(n log n) Patience Sorting when n is large (up to 10⁵) and you only need the length
• Use O(n log n) Fenwick Tree when you need counts, full reconstruction, or coordinate compression is natural

Quick Recap Checklist

• tails[pos] = smallest ending value of length (pos+1) subsequence
• bisect_left finds first >=, enabling strict increasing property
• len(tails) at end = LIS length
• For non-strict increasing, use bisect_right instead
• Test with: all decreasing, all same, already increasing, single element

Interview Questions

Further Reading

• Dynamic Programming: States and Transitions — Learn how to design DP states for LIS-like problems
• Russian Doll Envelopes (LeetCode 354) — Classic 2D LIS application
• Number of Longest Increasing Subsequence (LeetCode 673) — Count distinct LIS using Fenwick tree
• Patience Sorting on Wikipedia — Detailed explanation of the card game analogy
• Longest Increasing Subsequence on CP-Algorithms — Comprehensive algorithmic treatment
• Minimum Number of Operations to Make Array Increasing (LeetCode 1964) — Variation requiring LIS thinking

Conclusion

The key to O(n log n) LIS is the tails array: tails[i] holds the smallest ending value of any increasing subsequence of length i+1. Use bisect_left for strictly increasing sequences. When you need the actual subsequence, track positions during construction and backtrack from the end. For box-stacking and envelope problems, sort one dimension and apply LIS to the other. For more on optimization tricks, see Dynamic Programming: States and Transitions.