The Longest Increasing Subsequence (LIS) problem is a classic interview question frequently asked by top companies like Google, Amazon, and Meta. It tests dynamic programming and algorithm optimization skills.

Problem Statement

Given an integer array, nums, the task is to find the length of the longest strictly increasing subsequence in the array.

You only need to return the length of such a subsequence, not the subsequence itself.

Constraints:

• $1 \leq$ nums.length $\leq 2500$
• $−10^4 \leq$ nums[i] $\leq 10^4$

Examples

Breaking Down the Problem

At first glance, this problem may look similar to finding a longest increasing subarray. However, the key difference lies in the word subsequence.

In a subsequence, elements do not need to be adjacent. We are allowed to skip elements as long as the relative order is preserved. This significantly increases the number of possible combinations we need to consider.

What the problem is really asking is this:

If we can answer this question for every position, then the longest increasing subsequence in the entire array is simply the maximum of those answers.

Naive Approach

A straightforward way to think about the problem is to generate all possible subsequences of the array and check which ones are strictly increasing. Among those, we could track the maximum length.

While this idea works conceptually, it is not practical.

An array of length nnn has $2^{n}$ possible subsequences. Even for moderately sized inputs, this approach becomes infeasible due to exponential time complexity.

This limitation forces us to look for a more structured way to reuse previously computed results instead of recalculating them from scratch.

Improving the Naive Approach with Dynamic Programming

The main limitation of the naive approach is that it repeatedly solves the same subproblems. Many increasing subsequences share common prefixes, yet the brute-force method treats each possibility independently.

The key observation is that increasing subsequences have overlapping subproblems. If we already know the length of the longest increasing subsequence ending at earlier positions, we can reuse that information instead of recomputing it from scratch.

Rather than asking for the longest increasing subsequence in the entire array, we reframe the problem:

• What is the longest increasing subsequence ending at index 0?
• What is the longest increasing subsequence ending at index 1?
• And so on.

Once we have the answer for every index, the overall result is simply the maximum among them.

This leads to a dynamic programming solution that:

• Builds results incrementally from left to right
• Reuses previously computed information
• Avoids the redundant work present in the naive approach

Compared to brute force, this approach reduces the time complexity from exponential to polynomial. However, since each element still needs to be compared with all previous elements, the time complexity remains $O(n^{2})$, with an additional $O(n)$ space requirement to store intermediate results.

While this is a significant improvement and works well for moderate input sizes, the solution can be optimized further by reducing the number of comparisons.

Optimal Solution Using Binary Search

To improve upon the quadratic time complexity of the dynamic programming approach, we need a different way to think about how increasing subsequences grow. Instead of tracking the best subsequence ending at every index, we focus on keeping the most promising candidates for subsequences of different lengths.

The core idea is to maintain an auxiliary array where each position represents the smallest possible ending value of an increasing subsequence of a given length. Since this array is always kept in sorted order, we can use binary search to efficiently update it as we process each element in the input.

Step-by-Step Algorithm

The following steps describe how to compute the length of the longest increasing subsequence using binary search and a greedy strategy.

1. Initialize an empty list, tails, to store candidate subsequence endings.
2. Iterate through each element, num, in the input array:
   1. Use binary search on tails to find the leftmost index where num can be placed.
   2. If such an index exists within tails, replace the value at that index with num.
   3. Otherwise, append num to the end of tails.
3. After processing all elements, return the length of tails.

To better understand the solution, let’s walk through the algorithm using the illustration below:

1 / 6

Executable Python Implementation of the LIS Algorithm

The code below implements the algorithm described above.

def lengthOfLIS(nums):
    """
    Returns the length of the longest increasing subsequence
    using a binary search based approach.
    """
    if not nums:
        return 0

    # tails[i] will store the smallest possible ending value
    # of an increasing subsequence of length i + 1
    tails = []

    for num in nums:
        left, right = 0, len(tails)

        # Binary search to find the position where num fits
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid

        # If num is larger than all elements in tails, extend the list
        if left == len(tails):
            tails.append(num)
        else:
            # Otherwise, replace the existing value to keep tails optimal
            tails[left] = num

    return len(tails)

# Driver code
def main():
    test_cases = [
        [10, 9, 2, 5, 3, 7, 101, 18],
        [0, 1, 0, 3, 2, 3],
        [7, 7, 7, 7, 7],
        [5, 4, 3, 2, 1],
        [1, 3, 6, 7, 9, 4, 10, 5, 6]]

    for i, nums in enumerate(test_cases, 1):
        result = lengthOfLIS(nums)
        print(f"Test Case {i}:")
        print(f"\tInput: {nums}")
        print(f"\tOutput: {result}")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time Complexity

Each element in the input array is processed once. For every element, we perform a binary search on the tails array, which takes $O(log⁡n)$ time in the worst case. Therefore, the overall time complexity of the algorithm is $O(nlogn)$.

Space Complexity

The algorithm uses an auxiliary array tails to store candidate subsequence endings. In the worst case, this array can grow to the size of the input array, resulting in a space complexity of $O(n)$.

Common Pitfalls to Avoid

A frequent source of confusion in this problem is the difference between a subsequence and a subarray. The elements of a subsequence do not need to be contiguous, and overlooking this detail often leads to incorrect approaches.

Another common pitfall appears in the optimal solution. The auxiliary tails array does not represent the actual longest increasing subsequence. Instead, it stores the smallest possible ending values for subsequences of different lengths. Replacing values in this array may seem counterintuitive, but it never affects the final answer and is essential for achieving the $O(nlog⁡n)$ time complexity.

Keeping these points in mind helps avoid logical mistakes and makes the solution easier to reason about, especially in interview settings.