Dynamic Programming: 1D, 2D & Grid

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.