LIS Optimization with Binary Search

Welcome back! In our last lesson, we developed a solid $O(N^2)$ dynamic programming solution for the Longest Increasing Subsequence (LIS) problem. We identified that the main performance bottleneck was the inner loop, which had to scan all previous elements to find the best subsequence to extend.

Today, we will address that bottleneck head-on. Our goal is to optimize the LIS solution to run in $O(N\log N)$ time. To achieve this, we will reframe the problem with a new, clever perspective that allows us to replace the linear scan with a much faster binary search. This pattern is a powerful tool for your algorithmic toolkit and is a classic example of how a change in perspective can lead to significant performance gains.

1. A More Promising Strategy

In the $O(N^2)$ approach, our subproblem was "What is the length of the LIS ending at index i?" This forced us to look backwards at every step. Let's try a different approach.

Imagine you are building increasing subsequences as you iterate through the input array. Suppose you have two increasing subsequences of the same length, say length 2: (2, 6) and (2, 4). If you have to choose one to continue building upon, which one is more promising?

The (2, 4) subsequence is better. Why? Because its smaller ending number (4) leaves more room for future elements to extend it. Any number that can extend (2, 6) (e.g., 7) can also extend (2, 4). However, a number like 5 could extend (2, 4) but not (2, 6). This leads to a powerful greedy strategy.

The video below from the Techdose channel provides an excellent visualization of this core idea.

The key insight is this: For a given length k, the only increasing subsequence we need to care about is the one that ends with the smallest possible value. This is because this subsequence is the easiest to extend.

2. The $O(N\log N)$ Algorithm: Building with Patience

This greedy strategy is often explained using an analogy called "Patience Sorting," where you deal cards into piles. The rules are:

1. A new card can be placed on top of a pile only if it's smaller than the card currently on top.
2. You always place the card on the leftmost pile where it can legally go.
3. If no pile can take the card, you start a new pile to the right.

The length of the LIS turns out to be the total number of piles you create. In our algorithm, the "top card" of each pile represents the smallest ending element for an increasing subsequence of a certain length.

Let's formalize this. We will maintain an auxiliary array, let's call it tails. This array will store the smallest tail (ending element) of all increasing subsequences found so far, indexed by length. Specifically, tails[i] will be the smallest tail of an increasing subsequence of length i+1.

A crucial property of the tails array is that it will always be sorted in increasing order. Can you see why? If we had tails[i] >= tails[i+1], it would imply that we have an increasing subsequence of length i+2 ending in tails[i+1]. By removing the last element, we would get a subsequence of length i+1 ending in a value smaller than tails[i+1], which is also smaller than tails[i]. This would contradict the definition of tails[i] as the smallest tail for a subsequence of length i+1.

The article from CP-Algorithms provides a clear, formal description of this new DP state and the process.

As we process each number num from the input array, we have two cases:

1. num is greater than the last element of tails: This means num can extend the longest increasing subsequence found so far. We append num to the end of tails, effectively creating a new, longer LIS. The length of our LIS increases by one.

2. num is not greater than the last element of tails: This means num cannot extend the current longest subsequence. However, it might be a better (smaller) ending for a subsequence of some shorter length. We find the position in tails where num could replace an existing element to form an increasing subsequence of the same length but with a smaller tail.

This "replacement" step is the most clever part. We are not modifying a real subsequence; we are updating our tails array to say, "We have found a way to make an increasing subsequence of length k that ends with a smaller number, which will be more useful for future elements."

The video below from the "take U forward" channel brilliantly explains this idea of overwriting elements in a temporary array, emphasizing that we are only concerned with finding the final length.

3. Unleashing the Power of Binary Search

So, how do we efficiently perform the "replacement" step? We need to find the smallest element in tails that is greater than or equal to num. Since the tails array is always sorted, this is a perfect use case for binary search.

This is the optimization that gets us from $O(N^2)$ to $O(N\log N)$. Instead of a linear scan, we perform a logarithmic-time search. In C++, this is done with std::lower_bound, and in Python, with bisect.bisect_left.

Let's look at the implementation and trace it with an example.

import bisect

def length_of_lis_optimized(nums: list[int]) -> int:
    if not nums:
        return 0
    
    # This array will store the smallest tail of all increasing subsequences
    # tails[i] is the smallest ending element of an LIS of length i+1
    tails = []
    
    for num in nums:
        # Find the insertion point for 'num' in 'tails'
        # This is the index of the first element >= num
        idx = bisect.bisect_left(tails, num)
        
        if idx == len(tails):
            # num is greater than all elements in tails.
            # It extends the LIS, so we append it.
            tails.append(num)
        else:
            # We found a position to potentially improve an existing LIS.
            # Replace the element at idx with num. This gives us a
            # subsequence of the same length but with a smaller tail,
            # which is more promising for future elements.
            tails[idx] = num
            
    return len(tails)

# Example from the previous lesson
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"For {nums}, LIS length is: {length_of_lis_optimized(nums)}") # Expected: 4

# Another example
nums2 = [5, 15, 8, 7, 4, 10, 20, 19, 7, 25, 29, 12]
print(f"For {nums2}, LIS length is: {length_of_lis_optimized(nums2)}") # Expected: 6

Walkthrough with nums = [10, 9, 2, 5, 3, 7, 101, 18]

• num = 10: tails is empty. idx = 0. tails becomes [10].
• num = 9: bisect_left([10], 9) returns idx = 0. We replace tails[0]. tails becomes [9].
• num = 2: bisect_left([9], 2) returns idx = 0. We replace tails[0]. tails becomes [2].
• num = 5: bisect_left([2], 5) returns idx = 1. idx == len(tails), so we append. tails becomes [2, 5].
• num = 3: bisect_left([2, 5], 3) returns idx = 1. We replace tails[1]. tails becomes [2, 3]. (Note: (2,3) is more promising than (2,5))
• num = 7: bisect_left([2, 3], 7) returns idx = 2. idx == len(tails), so we append. tails becomes [2, 3, 7].

• num = 101: bisect_left([2, 3, 7], 101) returns idx = 3. Append. tails becomes [2, 3, 7, 101].
• num = 18: bisect_left([2, 3, 7, 101], 18) returns idx = 3. Replace tails[3]. tails becomes [2, 3, 7, 18].

The final tails array is [2, 3, 7, 18]. Its length is 4, which is the correct answer. Notice that [2, 3, 7, 18] is a valid LIS, but this is not always guaranteed. The tails array is a tool to find the length, not the sequence itself.

The image below illustrates the step-by-step execution of a similar algorithm. The green array, arr[LISArr[i]], is analogous to our tails array, showing how it is built up and modified over time.

This visualization shows the state of the auxiliary arrays as the algorithm processes the input. The green array represents the smallest ending values for increasing subsequences of growing lengths, similar to our tails array.

4. Complexity Analysis

• Time Complexity: $O(N\log N)$. We iterate through the N elements of the input array. In each iteration, we perform a binary search (bisect_left) on the tails array. The tails array can grow to a maximum size of N. Therefore, each binary search takes at most $O(\log N)$ time. The total time complexity is $O(N\log N)$.

• Space Complexity: $O(N)$. In the worst case (a strictly increasing input array), the tails array will store all N elements. Thus, the space complexity is $O(N)$.

This is a significant improvement over the $O(N^2)$ solution, especially for large inputs where $N$ might be $10^5$ or more, which are common constraints in competitive programming and interviews.

Conclusion

In this lesson, we transformed our approach to the LIS problem. By shifting our focus from "LIS ending at index i" to "the smallest end element for an LIS of length k," we unlocked a powerful optimization.

Key Takeaways:

• Greedy Choice: When considering subsequences of the same length, the one with the smallest ending element is always more promising.
• The tails Array: We maintain a sorted array tails where tails[i] stores the smallest ending element of an increasing subsequence of length i+1.
• Binary Search is Key: Because tails is always sorted, we can use binary search (bisect_left) to find the correct position for the current number in $O(\log N)$ time.
• Final Answer: The length of the LIS is simply the final length of the tails array. The tails array itself is an auxiliary structure and does not necessarily represent an actual LIS from the input.
• Complexity: The optimized algorithm runs in $O(N\log N)$ time and $O(N)$ space.

This pattern of using a sorted auxiliary array with binary search is not just for LIS; it appears in related problems, like the "Russian Doll Envelopes" problem on LeetCode. Recognizing this underlying structure is a key step toward algorithmic mastery.

In our next lesson, we will switch gears from subsequences to substrings and explore another common pattern: solving the Longest Palindromic Substring problem using the elegant "expand-around-center" technique.