Longest Increasing Subsequence: DP and Binary Search

Given an array of integers, find the length of the longest strictly increasing subsequence. A subsequence does not have to be contiguous. You can skip elements, but the ones you pick must be in the original order and each must be larger than the last.

This is LeetCode 300: Longest Increasing Subsequence, and it is one of the most frequently asked dynamic programming problems in interviews. It also has a beautiful O(n log n) solution using binary search that is worth understanding deeply. We will cover both.

Why the longest increasing subsequence matters

The longest increasing subsequence (LIS) problem is a cornerstone of dynamic programming. It shows up directly in interviews, and the techniques it teaches apply to many related problems: longest chain problems, envelope nesting, scheduling with dependencies, and more.

What makes LIS dynamic programming interesting is that, unlike Climbing Stairs or Coin Change where the DP state is a single value you build up left to right, here the decision at each index depends on scanning back through all previous indices. That makes the brute force DP O(n^2), and the clever binary search optimization that gets you to O(n log n) is a technique you will see in other contexts too.

The O(n^2) DP approach

The idea is straightforward. Define dp[i] as the length of the longest increasing subsequence that ends at index i. Every element is at least an LIS of length 1 by itself. For each index i, look at every earlier index j. If arr[j] < arr[i], then we could extend the subsequence ending at j by appending arr[i]. So dp[i] = max(dp[j] + 1) for all valid j.

The answer is the maximum value in the entire dp array.

Let's trace through the classic example: [10, 9, 2, 5, 3, 7, 101, 18].

At the end, the maximum value in the dp array is 4, so the longest increasing subsequence has length 4. One such subsequence is [2, 3, 7, 101]. Another is [2, 3, 7, 18]. There can be multiple valid answers, but the length is always 4.

def length_of_lis(nums):
    n = len(nums)
    dp = [1] * n

    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). For each of the n elements, we scan all previous elements.

Space: O(n). The dp array.

This is clean and correct. For arrays up to a few thousand elements, it works fine. But LeetCode's constraints allow n up to 2500, and interviewers sometimes ask for the O(n log n) approach. Let's get there.

The O(n log n) binary search approach

The O(n^2) approach is solid, but we can do better. The trick is to maintain a separate array called tails, where tails[i] stores the smallest possible tail element for an increasing subsequence of length i + 1.

Here is the key insight: as we process each number, we either extend the longest subsequence we have found so far, or we replace an element in tails to keep future options open. The decision is made with a binary search.

For each number num in the array:

1. If num is larger than every element in tails, append it. We found a longer subsequence.
2. Otherwise, find the leftmost element in tails that is greater than or equal to num, and replace it with num. This does not change any subsequence length, but it makes that slot "cheaper" for future extensions.

The length of tails at the end is the LIS length.

Let's trace through the same example, [10, 9, 2, 5, 3, 7, 101, 18]:

• Process 10: tails = [10]
• Process 9: 9 replaces 10 (smaller tail for length-1). tails = [9]
• Process 2: 2 replaces 9. tails = [2]
• Process 5: 5 > 2, extend. tails = [2, 5]
• Process 3: 3 replaces 5 (smaller tail for length-2). tails = [2, 3]
• Process 7: 7 > 3, extend. tails = [2, 3, 7]
• Process 101: 101 > 7, extend. tails = [2, 3, 7, 101]
• Process 18: 18 replaces 101 (smaller tail for length-4). tails = [2, 3, 7, 18]

Final length of tails = 4. That is our answer.

Why does replacing elements work? Think of it this way: by keeping the smallest possible tail for each length, you are maximizing your chances of extending the subsequence later. If you encounter a number that could fit as a length-3 tail but the current length-3 tail is bigger, swapping in the smaller value never hurts. It either helps later or changes nothing.

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)
        else:
            tails[pos] = num

    return len(tails)

Time: O(n log n). We process each of the n elements once, and each binary search over tails takes O(log n).

Space: O(n). The tails array, in the worst case, holds all n elements (if the array is already sorted).

The bisect_left function finds the leftmost position where num could be inserted to keep tails sorted. If that position is at the end, num extends the subsequence. Otherwise, it replaces an existing entry.

This technique is sometimes called "patience sorting" because it resembles the card game Patience (Solitaire), where you place cards on piles following specific rules. The number of piles at the end equals the length of the LIS.

Complexity analysis

Both approaches use O(n) space. The binary search version is strictly better on time. In practice, the O(n^2) solution passes on LeetCode because n is at most 2500, but the O(n log n) solution is what interviewers typically want to see for this problem.

Edge cases to watch for

• Empty array: return 0. Some implementations assume len(nums) >= 1, so check the constraints.
• Single element: return 1. The element itself is an LIS of length 1.
• Already sorted: e.g., [1, 2, 3, 4, 5]. The entire array is the LIS. The O(n log n) approach just keeps appending.
• Strictly decreasing: e.g., [5, 4, 3, 2, 1]. Every element starts a new length-1 subsequence. Answer is 1.
• Duplicates: e.g., [2, 2, 2, 2]. The subsequence must be strictly increasing, so the answer is 1. Using bisect_left (not bisect_right) handles this correctly because it finds the position of the existing equal element and replaces it.
• All same except one: e.g., [1, 1, 1, 1, 5]. Answer is 2 (pick any 1 and the 5).

The building blocks

This problem is built on two reusable patterns.

The first is linear DP with variable lookback. Unlike Climbing Stairs where each cell depends on a fixed number of previous cells, here dp[i] depends on every earlier cell where the array value is smaller. The transition scans backward across the entire prefix. This same structure appears in several other problems:

• Russian Doll Envelopes (LeetCode 354): sort by one dimension, then find the LIS in the other dimension.
• Number of Longest Increasing Subsequences (LeetCode 673): same DP, but also track how many subsequences achieve each length.
• Longest String Chain (LeetCode 1048): sort words by length, then run LIS-style DP with a "predecessor" check instead of a simple less-than comparison.

The second building block is binary search on a maintained sequence. The O(n log n) approach uses binary search to find where each element belongs in a sorted structure, then updates that structure in place. This is the same idea behind:

• Patience sorting for finding LIS length
• Binary search insertion patterns used in problems like Search Insert Position (LeetCode 35)
• Maintaining sorted invariants that show up in median-finding and interval problems

Once you can recognize "scan all predecessors and take the best" as LIS-style DP, and "maintain a sorted auxiliary array with binary search" as the optimization layer, you have two bricks that snap together across many problems.

From understanding to recall

You have just walked through two complete solutions to the longest increasing subsequence problem. The O(n^2) DP version is intuitive once you see the scan-back pattern. The O(n log n) version is cleverer and takes a bit more work to internalize, especially the "why does replacing elements work?" intuition.

Here is the problem: understanding both approaches right now does not mean you will be able to reproduce them next week. In an interview, you need to write the DP recurrence from scratch, explain why it works, and then pivot to the binary search optimization if asked. That takes practice, not just comprehension.

Spaced repetition is the most efficient way to close that gap. You revisit the LIS problem at increasing intervals, and each time you write the solution from memory. After a few reps, the scan-back DP pattern and the patience sorting trick become automatic. You stop thinking about them and just write them.

LIS dynamic programming is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually beats random grinding every time.

Related posts

• Climbing Stairs - The simplest DP problem, and the best place to start before tackling LIS
• Coin Change - Another classic DP problem where the transition considers multiple choices at each step

---

Visual Learner? The O(n log n) solution uses binary search — see it explained visually in our Binary Search Guide.