Longest Increasing Subseq

Problem

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

Approach

Patience sorting with binary search. Maintain a list of "tails" where tails[i] is the smallest tail element for an increasing subsequence of length i+1. For each number, use bisect_left to find its position and either extend or replace.

When to Use

Patience sorting / longest chain — "longest increasing subsequence", "longest chain of pairs", "box stacking". Binary search on tails array for O(n log n). Also: longest non-decreasing, envelope nesting.

Complexity

Time	O(n log n)
Space	O(n)

Implementation

SolutionTestsChallenge

longest_increasing_subseq

Longest Increasing Subsequence — length of LIS.

Problem

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

Approach

Patience sorting with binary search. Maintain a list of "tails" where tails[i] is the smallest tail element for an increasing subsequence of length i+1. For each number, use bisect_left to find its position and either extend or replace.

When to use

Patience sorting / longest chain — "longest increasing subsequence", "longest chain of pairs", "box stacking". Binary search on tails array for O(n log n). Also: longest non-decreasing, envelope nesting.

Complexity

Time: O(n log n) Space: O(n)

length_of_lis

length_of_lis(nums: Sequence[int]) -> int

Return the length of the longest strictly increasing subsequence.

length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) 4 length_of_lis([0, 1, 0, 3, 2, 3]) 4

Source code in src/algo/dp/longest_increasing_subseq.py

def length_of_lis(nums: Sequence[int]) -> int:
    """Return the length of the longest strictly increasing subsequence.

    >>> length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])
    4
    >>> length_of_lis([0, 1, 0, 3, 2, 3])
    4
    """
    if not nums:
        return 0

    tails: list[int] = []
    for n in nums:
        pos = bisect.bisect_left(tails, n)
        if pos == len(tails):
            tails.append(n)
        else:
            tails[pos] = n
    return len(tails)

tests/dp/test_longest_increasing_subseq.py

"""Tests for longest increasing subsequence."""

from hypothesis import given
from hypothesis import strategies as st

from algo.dp.longest_increasing_subseq import length_of_lis


class TestLengthOfLIS:
    def test_basic(self) -> None:
        assert length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) == 4

    def test_all_increasing(self) -> None:
        assert length_of_lis([1, 2, 3, 4, 5]) == 5

    def test_all_decreasing(self) -> None:
        assert length_of_lis([5, 4, 3, 2, 1]) == 1

    def test_single_element(self) -> None:
        assert length_of_lis([7]) == 1

    def test_empty(self) -> None:
        assert length_of_lis([]) == 0

    def test_duplicates(self) -> None:
        assert length_of_lis([0, 1, 0, 3, 2, 3]) == 4

    @given(
        data=st.lists(
            st.integers(min_value=-100, max_value=100), min_size=1, max_size=50
        ),
    )
    def test_result_within_bounds(self, data: list[int]) -> None:
        result = length_of_lis(data)
        assert 1 <= result <= len(data)

Implement it yourself

Run: just challenge dp longest_increasing_subseq

Then implement the functions to make all tests pass. Use just study dp for watch mode.

Reveal Solution

longest_increasing_subseq

Longest Increasing Subsequence — length of LIS.

Problem

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

Approach

Patience sorting with binary search. Maintain a list of "tails" where tails[i] is the smallest tail element for an increasing subsequence of length i+1. For each number, use bisect_left to find its position and either extend or replace.

When to use

Patience sorting / longest chain — "longest increasing subsequence", "longest chain of pairs", "box stacking". Binary search on tails array for O(n log n). Also: longest non-decreasing, envelope nesting.

Complexity

Time: O(n log n) Space: O(n)

length_of_lis

length_of_lis(nums: Sequence[int]) -> int

Return the length of the longest strictly increasing subsequence.

length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) 4 length_of_lis([0, 1, 0, 3, 2, 3]) 4

Source code in src/algo/dp/longest_increasing_subseq.py

def length_of_lis(nums: Sequence[int]) -> int:
    """Return the length of the longest strictly increasing subsequence.

    >>> length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])
    4
    >>> length_of_lis([0, 1, 0, 3, 2, 3])
    4
    """
    if not nums:
        return 0

    tails: list[int] = []
    for n in nums:
        pos = bisect.bisect_left(tails, n)
        if pos == len(tails):
            tails.append(n)
        else:
            tails[pos] = n
    return len(tails)