Home/Questions/Q 3524
Next
In Process

RTSALL Latest Articles

Ahmedelkomy
Asked: 2026-09-11T09:52:00-05:00 In: ,

Why does Patience Sorting solve Longest Increasing Subsequence in O(N log N) instead of O(N^2)?

The standard DP solution for Longest Increasing Subsequence (LIS) uses two nested loops: for each element i, scan all previous elements j < i. That takes O(N^2) time, which times out when N = 100,000.

Everyone says the optimal solution is O(N log N) using Patience Sorting and Binary Search (bisect_left). But the tails array does NOT store the actual LIS sequence! How can an array that doesn’t hold the subsequence correctly tell us the exact length of the LIS?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhishek
    Begginer

    Here is the clean C++20 Patience Sorting LIS using std::lower_bound. On 100,000 integers, this executes in approximately 12 milliseconds.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <algorithm>

int lengthOfLIS(const std::vector<int>& nums) {
    if (nums.empty()) return 0;
    std::vector<int> tails;
    tails.reserve(nums.size());

    for (int x : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return static_cast<int>(tails.size());
}

int main() {
    std::vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << "Length of LIS: " << lengthOfLIS(arr) << "n";
    return 0;
}

    Complexity: Time is O(N log N) and space is O(N). std::lower_bound runs binary search with branchless comparison intrinsics.

    • 0
  2. Abhay Tiwari
    Begginer

    This is one of the most common points of confusion when studying LIS. Let’s clear up the mystery of why the tails array works even though its contents look ‘wrong’.

    1. What does the `tails` array actually represent?

    In Patience Sorting (inspired by solitaire card games):

    tails[k] stores the SMALLEST ending value of an increasing subsequence of length k + 1 found so far.

    Why do we care about the smallest ending value? Because in an increasing subsequence, the smaller the number you end with, the easier it is for future numbers to be bigger than it! You want to keep your options as open as possible.

    2. The Step-by-Step Card Dealing Analogy

    Suppose our array is: [10, 9, 2, 5, 3, 7, 101, 18].

    1. See 10: tails = [10] (Best subsequence of len 1 ends with 10).
    2. See 9: 9 < 10. Replace 10 with 9: tails = [9] (Ending with 9 is strictly better than ending with 10).
    3. See 2: 2 < 9. Replace 9 with 2: tails = [2].
    4. See 5: 5 > 2! Extend! tails = [2, 5] (Best len 1 ends in 2, best len 2 ends in 5).
    5. See 3: 3 < 5. Replace 5 with 3: tails = [2, 3] (Now best len 2 ends in 3!).
    6. See 7: 7 > 3! Extend! tails = [2, 3, 7] (Len 3).
    7. See 101: Extend! tails = [2, 3, 7, 101] (Len 4).
    8. See 18: 18 < 101. Replace 101 with 18: tails = [2, 3, 7, 18].

    Total length of tails is 4. The answer is 4!

    3. Why the array contents might look scrambled, but length is ALWAYS correct

    Imagine if after [2, 3, 7, 18] we saw 1. We would replace 2 with 1, resulting in tails = [1, 3, 7, 18].

    Notice that [1, 3, 7, 18] might not be a valid subsequence from the original array. And that doesn’t matter!

    Replacing 2 with 1 only prepares the board for a hypothetical future subsequence that starts with 1. It does not change the fact that a valid subsequence of length 4 ([2, 3, 7, 18]) was already locked in!

    The length of tails only increases when a number is strictly greater than ALL existing tail values. Replacements never shrink the array length!

    Clean Python 3.12 Implementation with bisect_left

    from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
    """Calculates length of LIS in O(N log N) time and O(N) space."""
    tails = []

    for x in nums:
        # Binary search: find first element in tails >= x
        idx = bisect_left(tails, x)
        
        if idx == len(tails):
            # x is strictly greater than all existing tails -> extend length!
            tails.append(x)
        else:
            # Found smaller tail candidate -> update in-place
            tails[idx] = x

    return len(tails)

    Complexity Breakdown

    • Time Complexity: O(N log N). We iterate through N elements, and for each element we perform binary search over tails (at most length N). N * log(N). For 100,000 elements, this finishes in 0.02 seconds (compared to ~45 seconds for O(N^2)).
    • Space Complexity: O(N) to hold the tails array.
    • 0