Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1 Codex Max· openaiHugging Face Frontier Reasoning Traces

Implement longest increasing subsequence using the patience sorting approach in O(n log…

  1. User

    Implement longest increasing subsequence using the patience sorting approach in O(n log n). Maintain a list of active pile tails and for each number binary search to find the first pile top >= the number and replace it, or start a new pile.

  2. Assistant

    Implementing LIS with patience sorting

    The algorithm maintains active pile tails representing the smallest possible tail for increasing subsequences of each length. For each number, it binary searches the tails to find the first tail ≥ the number to replace or appends it if none is found. The final number of tails is the length of the longest increasing subsequence.

    from bisect import bisect_left
    
    def longest_increasing_subsequence(nums):
        tails = []
        for num in nums:
            i = bisect_left(tails, num)
            if i == len(tails):
                tails.append(num)
            else:
                tails[i] = num
        return len(tails)
    
    # Example usage
    if __name__ == "__main__":
        sequence = [10, 9, 2, 5, 3, 7, 101, 18]
        print(longest_increasing_subsequence(sequence))  # Output: 4
    ```</think>
    A patience‑sorting based LIS keeps, for every possible subsequence length, the smallest tail value seen so far. When a new element arrives you either start a new pile (subsequence) or replace the tail of an existing one; the length of the pile list at the end is the LIS length.
    
    Here's an \(O(n\log n)\) implementation in Python:
    
    ```python
    from bisect import bisect_left
    
    def lis_length(seq):
        tails = []  # tails[i] = minimum possible tail of an IS of length i+1
        for x in seq:
            # find leftmost tail >= x
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)   # start a new pile
            else:
                tails[i] = x      # replace pile top
        return len(tails)
    
    # example
    data = [10, 9, 2, 5, 3, 7, 101, 18]
    print(lis_length(data))  # prints 4 (e.g. [2,3,7,18])
    

    If you prefer to see the binary search explicitly:

    def lis_length(seq):
        tails = []
        for x in seq:
            lo, hi = 0, len(tails)
            while lo < hi:
                mid = (lo + hi) // 2
                if tails[mid] >= x:
                    hi = mid
                else:
                    lo = mid + 1
            if lo == len(tails):
                tails.append(x)
            else:
                tails[lo] = x
        return len(tails)
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.