Longest Subsequence Variants: LIS, Bitonic, Chain, Zigzag & Envelopes

The Longest Increasing Subsequence (LIS) is one of the most versatile DP problems. It appears directly in interviews and forms the backbone of many harder problems. This post covers six variants, from the classic LIS to 2D extensions.

1. Longest Increasing Subsequence (LIS)

Problem: Given an array nums, find the length of the longest strictly increasing subsequence. (LeetCode 300)

O(n^2) DP

dp[i] = length of the LIS ending at index i.

def length_of_lis_dp(nums):
    n = len(nums)
    if n == 0:
        return 0

    dp = [1] * n  # every element is an LIS of length 1

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

    return max(dp)

Time: O(n^2) | Space: O(n)

O(n log n) Patience Sorting

Maintain a list tails where tails[k] is the smallest tail element of all increasing subsequences of length k + 1. This array is always sorted, so we can binary search.

import bisect

def length_of_lis(nums):
    tails = []

    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)  # extend longest subsequence
        else:
            tails[pos] = num   # replace to keep tails as small as possible

    return len(tails)

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

Why Does This Work?

The tails array does not represent an actual subsequence. It represents the best possible tails for each length. When we replace tails[pos] = num, we are saying: “there exists an increasing subsequence of length pos + 1 that ends with num, which is smaller than the previous tail.”

Reconstructing the LIS

To get the actual subsequence, track which element replaced which:

import bisect

def find_lis(nums):
    n = len(nums)
    if n == 0:
        return []

    tails = []
    indices = []      # which index in nums produced each tail
    predecessors = [-1] * n  # for backtracking

    for i, num in enumerate(nums):
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
            indices.append(i)
        else:
            tails[pos] = num
            indices[pos] = i

        if pos > 0:
            predecessors[i] = indices[pos - 1]

    # Backtrack from the last element
    result = []
    idx = indices[len(tails) - 1]
    while idx != -1:
        result.append(nums[idx])
        idx = predecessors[idx]

    return result[::-1]

---

2. Longest Non-Decreasing Subsequence

For non-decreasing (allowing equal elements), change bisect_left to bisect_right:

import bisect

def length_of_lnds(nums):
    tails = []
    for num in nums:
        pos = bisect.bisect_right(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

---

3. Longest Bitonic Subsequence

Problem: A bitonic sequence first increases, then decreases. Find the longest bitonic subsequence.

Approach: LIS from Left + LIS from Right

1. Compute lis[i] = LIS ending at i (left to right)
2. Compute lds[i] = LIS ending at i (right to left, which is the longest decreasing suffix)
3. Answer = max(lis[i] + lds[i] - 1) for all i

import bisect

def longest_bitonic(nums):
    n = len(nums)
    if n <= 2:
        return n

    # LIS ending at each index
    lis = [1] * n
    tails = []
    for i in range(n):
        pos = bisect.bisect_left(tails, nums[i])
        if pos == len(tails):
            tails.append(nums[i])
        else:
            tails[pos] = nums[i]
        lis[i] = pos + 1

    # LDS (LIS from right) ending at each index
    lds = [1] * n
    tails = []
    for i in range(n - 1, -1, -1):
        pos = bisect.bisect_left(tails, nums[i])
        if pos == len(tails):
            tails.append(nums[i])
        else:
            tails[pos] = nums[i]
        lds[i] = pos + 1

    # Combine: element i is the peak of a bitonic sequence
    max_len = 0
    for i in range(n):
        # Must have at least one element on each side
        if lis[i] > 1 and lds[i] > 1:
            max_len = max(max_len, lis[i] + lds[i] - 1)

    return max_len

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

---

4. Longest Chain of Pairs

Problem: Given pairs (a, b) where a {'<'} b, find the longest chain such that for consecutive pairs (c, d) and (e, f), d {'<'} e. (LeetCode 646)

Greedy Approach (Optimal)

Sort by second element. Greedily pick the pair whose end is smallest.

def find_longest_chain(pairs):
    pairs.sort(key=lambda x: x[1])

    count = 1
    end = pairs[0][1]

    for i in range(1, len(pairs)):
        if pairs[i][0] > end:
            count += 1
            end = pairs[i][1]

    return count

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

DP Approach

Sort by first element. Then it becomes an LIS-like problem:

def find_longest_chain_dp(pairs):
    pairs.sort()
    n = len(pairs)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if pairs[j][1] < pairs[i][0]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Time: O(n^2) | Space: O(n)

Comparison: This is Activity Selection

The chain of pairs problem is equivalent to the activity selection problem (select maximum non-overlapping intervals). The greedy approach is optimal and preferred.

---

5. Longest Zigzag (Alternating) Subsequence

Problem: Find the longest subsequence where consecutive differences alternate between positive and negative. (LeetCode 376, also called “Wiggle Subsequence”)

O(n) Solution

Track two values:

• up = length of longest zigzag ending with an upward step
• down = length of longest zigzag ending with a downward step

def wiggle_max_length(nums):
    n = len(nums)
    if n <= 1:
        return n

    up = 1
    down = 1

    for i in range(1, n):
        if nums[i] > nums[i - 1]:
            up = down + 1
        elif nums[i] < nums[i - 1]:
            down = up + 1
        # if equal, both stay the same

    return max(up, down)

Time: O(n) | Space: O(1)

Why This Works

When nums[i] > nums[i-1], the best “ending up” sequence is the best “ending down” sequence plus this upward step. We do not need to track indices because the greedy choice is always correct for zigzag patterns.

Full DP Version (for understanding)

def wiggle_max_length_dp(nums):
    n = len(nums)
    if n <= 1:
        return n

    up = [1] * n
    down = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                up[i] = max(up[i], down[j] + 1)
            elif nums[i] < nums[j]:
                down[i] = max(down[i], up[j] + 1)

    return max(max(up), max(down))

Time: O(n^2) | Space: O(n)

---

6. Russian Doll Envelopes (2D LIS)

Problem: Given envelopes as (width, height) pairs, find the maximum number that can be nested (each envelope must be strictly larger in both dimensions). (LeetCode 354)

The Trick: Sort + 1D LIS

1. Sort envelopes by width ascending.
2. For same width, sort by height descending.
3. Run LIS on the heights.

Why descending height for same width? If two envelopes have the same width, they cannot nest inside each other. Sorting heights in descending order ensures LIS on heights will pick at most one envelope per width.

import bisect

def max_envelopes(envelopes):
    # Sort: width ascending, height descending for same width
    envelopes.sort(key=lambda x: (x[0], -x[1]))

    # LIS on heights
    tails = []
    for _, h in envelopes:
        pos = bisect.bisect_left(tails, h)
        if pos == len(tails):
            tails.append(h)
        else:
            tails[pos] = h

    return len(tails)

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

Example Walkthrough

Envelopes: [(5,4), (6,4), (6,7), (2,3)]

1. Sort: [(2,3), (5,4), (6,7), (6,4)]
2. Heights: [3, 4, 7, 4]
3. LIS on heights:
   • 3: tails = [3]
   • 4: tails = [3, 4]
   • 7: tails = [3, 4, 7]
   • 4: replace 7 -> tails = [3, 4, 4]
4. LIS length = 3

Answer: 3 envelopes can nest: (2,3) inside (5,4) inside (6,7).

---

Variant Comparison Table

Problem	Key Idea	Time	Space
LIS	Patience sorting	O(n log n)	O(n)
Non-decreasing	bisect_right instead	O(n log n)	O(n)
Bitonic	LIS left + LIS right	O(n log n)	O(n)
Chain of Pairs	Sort by end, greedy	O(n log n)	O(1)
Zigzag	up/down counters	O(n)	O(1)
Russian Doll	Sort trick + LIS	O(n log n)	O(n)

---

Common Mistakes

1. Using bisect_right for strict LIS. Strict increasing requires bisect_left. Non-decreasing uses bisect_right.
2. Forgetting the descending sort for same-width envelopes in Russian Doll.
3. Bitonic peak must have both sides. A purely increasing or decreasing sequence is not bitonic.
4. Chain of pairs: sorting by first element with DP works but is O(n^2). Sorting by second element with greedy is O(n log n).
5. Zigzag: treating equal elements as going up or down. Equal elements mean “no change.”

---

Practice Problems

Problem	Platform	Difficulty
Longest Increasing Subsequence	LeetCode 300	Medium
Number of LIS	LeetCode 673	Medium
Longest Bitonic Subsequence	GFG	Medium
Maximum Length of Pair Chain	LeetCode 646	Medium
Wiggle Subsequence	LeetCode 376	Medium
Russian Doll Envelopes	LeetCode 354	Hard
Longest String Chain	LeetCode 1048	Medium
Increasing Triplet Subsequence	LeetCode 334	Medium
Minimum Operations to Make Array Non-Decreasing	LeetCode 2771	Medium