Longest Increasing Subsequence

1. The Problem

Given an integer array, find the length of the longest strictly increasing subsequence. A subsequence can skip elements but must preserve order.

# [10,9,2,5,3,7,101,18]  →  4  (e.g. [2,3,7,101] or [2,5,7,101])
# [0,1,0,3,2,3]           →  4  ([0,1,2,3])
# [7,7,7,7]               →  1  (strictly increasing — no ties)

2. Solution 1 — O(n²) DP

dp[i] = length of the longest increasing subsequence ending at index i. For each i, look back at all earlier elements smaller than nums[i].

def lis_dp(nums):
    if not nums: return 0
    dp = [1] * len(nums)  # Every element alone is length 1

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

print(lis_dp([10,9,2,5,3,7,101,18]))  # 4

Time: O(n²). Space: O(n). Good enough to pass most interviews — the binary search solution is a bonus.

3. The Patience Sort Insight

Imagine playing solitaire. You deal cards left to right and place each card on the leftmost pile whose top card is ≥ the new card. If no such pile exists, start a new pile. The number of piles equals the LIS length.

# nums = [10, 9, 2, 5, 3, 7, 101, 18]
#
# tails = []  (tails[i] = smallest tail of all LIS of length i+1)
#
# 10  → no pile, start one.    tails=[10]
# 9   → 9 < 10, replace 10.   tails=[9]
# 2   → 2 < 9, replace 9.     tails=[2]
# 5   → 5 > 2, new pile.      tails=[2,5]
# 3   → 3 < 5, replace 5.     tails=[2,3]
# 7   → 7 > 3, new pile.      tails=[2,3,7]
# 101 → 101 > 7, new pile.    tails=[2,3,7,101]
# 18  → 18 < 101, replace.    tails=[2,3,7,18]
#
# 4 piles = LIS length 4  ✓

tails is always sorted, so finding where to place each new element is a binary search — O(log n) per element.

4. Solution 2 — O(n log n) with Binary Search

import bisect

def lis(nums):
    tails = []
    for num in nums:
        # Find leftmost position in tails where tails[pos] >= num
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)  # Extend LIS
        else:
            tails[pos] = num    # Replace to keep tails as small as possible
    return len(tails)

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

5. Summary