Longest Increasing Subsequence

Tags

Longest Increasing Subsequence

Category

Dynamic Programming

Difficulty

Very Hard

Problem Statement

Given an array of integers, find the length of the longest strictly increasing subsequence (LIS). A subsequence is a sequence derived from the array by deleting zero or more elements without changing the order of the remaining elements. For example, in [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 101] with length 4.

Intuition

The classic O(n^2) DP defines dp[i] as the length of the LIS ending at index i and checks all prior elements. The O(n log n) approach is more subtle: we maintain an auxiliary array tails where tails[j] is the smallest possible tail element of an increasing subsequence of length j+1 found so far. This array is always sorted, so we can binary search for the correct position to place each new element. By keeping tail values as small as possible, we maximize the chance that future elements can extend the subsequence.

Approach

  1. Initialize an empty array tails.
  2. For each element num in the input array:
    • Binary search tails for the leftmost position pos where tails[pos] >= num.
    • If pos == length(tails), append num (it extends the longest subsequence found so far).
    • Otherwise, set tails[pos] = num (replace to keep the smallest possible tail).
  3. The length of tails at the end is the LIS length.
  4. To reconstruct the actual subsequence, maintain a parallel parent array and track which index placed each element in tails, then backtrack from the last element.

Pseudocode

function longestIncreasingSubsequence(array):
    if array is empty:
        return 0

    tails = []

    for num in array:
        pos = binarySearchLeft(tails, num)
        if pos == length(tails):
            append num to tails
        else:
            tails[pos] = num

    return length(tails)

function binarySearchLeft(arr, target):
    lo = 0
    hi = length(arr)
    while lo < hi:
        mid = (lo + hi) / 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Time & Space Complexity

  • Time: O(n log n). We iterate through n elements, and for each element we perform a binary search on tails which has at most n entries, costing O(log n) per search.
  • Space: O(n) for the tails array (and O(n) for reconstruction data if the actual subsequence is needed).

Key Insights

  • The tails array is not the LIS itself; it is an auxiliary structure that maintains the invariant that tails is sorted and tails[j] holds the smallest tail of any increasing subsequence of length j+1.
  • Replacing an element in tails does not shorten the LIS; it only improves future extensibility by lowering a tail value.
  • The binary search finds the first element in tails that is >= the current number (lower bound), which is where the current number should be placed.
  • The O(n^2) approach (dp[i] = 1 + max(dp[j] for j < i if array[j] < array[i])) is simpler to implement and sufficient for small inputs.
  • Patience sorting provides an alternative intuitive mental model: each pile's top card corresponds to a tails entry.

Edge Cases

  • Empty array: LIS length is 0.
  • Single element: LIS length is 1.
  • Already sorted (strictly increasing): LIS is the entire array.
  • Sorted in decreasing order: LIS length is 1 (any single element).
  • All elements equal: LIS length is 1 (strictly increasing means no ties).
  • Array with negative numbers: Works identically; the values just happen to be negative.
  • Duplicate values: Binary search finds the leftmost position >= the value, so duplicates correctly do not extend the LIS (since the problem requires strictly increasing).

Linked mentions