Longest Increasing Subsequence (LIS) | Binary Search & Intuition

The Longest Increasing Subsequence (LIS) problem is a classic algorithmic challenge. While standard Dynamic Programming solutions achieve an $O(n^2)$ time complexity, this approach becomes inefficient when constraints reach $N = 10^5$ (resulting in $10^{10}$ operations and hitting Time Limit Exceeded errors). This chapter explores how to optimize LIS to an $O(n \log n)$ time complexity using binary search, focusing deeply on the core mental model and intuition.

1. Why Do We Need This? (Problem Statement & Status Quo)

• The Constraint Bottleneck: When $N = 10^5$, an $O(n^2)$ tabulation or memoization approach requires $10^{10}$ operations, which exceeds standard time limits in competitive programming and technical interviews.
• Prior Limitations: Recursion, memoization, space-optimized tabulation, and standard algorithmic approaches max out at $O(n^2)$ time and $O(n)$ space.
• The Objective: We need an approach that drastically cuts down the time complexity to $O(n \log n)$ while preserving an $O(n)$ space complexity.

2. Core Mental Model: Subsequence Growth vs. Space Reuse

Real-Life Analogy: The Desktop Pile Analogy

Note: Imagine stacking incoming project files on your desk. If a new file has a higher priority number than the previous one, you place it neatly on top (growing the stack). If a smaller priority file comes in, rather than starting an entirely new separate pile (which takes up too much physical desk space), you slide it into the existing stack by replacing an older, larger number. You might mess up the exact chronological history of individual files, but the height (maximum length) of the stack remains completely accurate.

• What is a Subsequence? A subsequence is a sequence derived from an array by deleting some or no elements without changing the order of the remaining elements.
• Example Array: [1, 7, 8, 4, 5, 6, -1, 9]
• Valid Subsequence: 1 -> 8 -> 9 (increasing)
• Longest Increasing Subsequence: 1 -> 4 -> 5 -> 6 -> 9 (length 5)

3. Naive vs. Better Approach: Simulating Multiple Subsequences

If we simulate building all potential increasing subsequences step by step:

1. Start at 1: [1]
2. Encounter 7: Attach to form [1, 7]
3. Encounter 8: Attach to form [1, 7, 8]
4. Encounter 4: Cannot attach to 8, so we either start a new subsequence or attach to 1 ([1, 4]).
5. Continue this process for all elements, branching out multiple possible subsequences.

The Catch: Maintaining multiple independent active subsequences simultaneously consumes immense memory and time, making it impractical for large arrays.

4. Step-by-Step Evolution: Space Reuse Optimization

Instead of storing multiple active lists, what if we maintain only one active array/list and strategically overwrite elements when smaller numbers appear?

Let's trace the array [1, 7, 8, 4, 5, 6, -1, 9] using a single dynamic tracking array (temp):

Step 1: Process 1
   temp = [1] (Length: 1)

Step 2: Process 7 (7 > 1)
   temp = [1, 7] (Length: 2)

Step 3: Process 8 (8 > 7)
   temp = [1, 7, 8] (Length: 3)

Step 4: Process 4 (Can 4 extend [1, 7, 8]? No. Where does 4 fit?)
   - Overwrite 7 with 4 because 4 is smaller and can prime a better subsequence.
   temp = [1, 4, 8] (Length: 3)
   *(Note: [1, 4, 8] is NOT the actual LIS, but it maintains the correct length tracking).*

Step 5: Process 5 (5 replaces 8)
   temp = [1, 4, 5] (Length: 3)

Step 6: Process 6 (6 extends [1, 4, 5])
   temp = [1, 4, 5, 6] (Length: 4)

Step 7: Process -1 (-1 replaces 1 as the smallest starting element)
   temp = [-1, 4, 5, 6] (Length: 4)

Step 8: Process 9 (9 extends [-1, 4, 5, 6])
   temp = [-1, 4, 5, 6, 9] (Length: 5)

Final Answer: The size of our temp array at the end gives the exact length of the LIS ($5$).

5. Why Binary Search?

When evaluating an incoming element (e.g., 4), we need to find its correct insertion position inside our sorted temp array:

• If the element is larger than all elements in temp, it extends the array (appended to the back).
• If the element is smaller or equal, we find the first element greater than or equal to our current value and overwrite it.

Because our temp array is always sorted, we do not need a linear scan to find this position. We can use Binary Search (lower_bound in C++).

6. Complete Implementation Walkthrough (C++)

Here is the clean production-grade implementation using C++ and binary search:

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int longestIncreasingSubsequence(vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return 0;

    vector<int> temp;
    
    // Initialize with the first element
    temp.push_back(arr[0]);

    for (int i = 1; i < n; i++) {
        // If current element is greater than the last element in temp, extend it
        if (arr[i] > temp.back()) {
            temp.push_back(arr[i]);
        } else {
            // Otherwise, find the index of the first element >= arr[i] using binary search
            auto it = lower_bound(temp.begin(), temp.end(), arr[i]);
            int idx = it - temp.begin();
            
            // Overwrite to maintain optimal potential subsequence lengths
            temp[idx] = arr[i];
        }
    }

    // The size of temp represents the length of the Longest Increasing Subsequence
    return temp.size();
}

int main() {
    vector<int> arr = {1, 7, 8, 4, 5, 6, -1, 9};
    cout << "Length of LIS: " << longestIncreasingSubsequence(arr) << endl;
    return 0;
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Limitation of $O(n^2)$: Standard DP tabulation approaches fail with an TLE error when input constraints reach $N = 10^5$.
• The Power of Binary Search: Reduces time complexity from quadratic $O(n^2)$ to log-linear $O(n \log n)$.
• Space Reuse Strategy: We do not store the actual LIS elements in our temporary array; instead, we overwrite existing slots to maintain optimal thresholds for future element comparisons.
• The lower_bound Function: Essential for finding the exact replacement position (the first element greater than or equal to the current number) in logarithmic time.
• Sorted Invariant: The auxiliary temp array remains strictly sorted at all times, making binary search applicable throughout the execution.
• Length vs. Sequence: This optimized approach correctly outputs the length of the LIS, but recovering the exact subsequence requires additional tracking structures.