Maximal Ascending Sequence Length

You're midway through a Google phone screen when the interviewer asks: "Given an array of integers, find the length of the longest strictly increasing subsequence." You recognize it immediately. This is one of the most heavily tested dynamic programming problems in the industry, appearing at Google, Amazon, Apple, Adobe, and Meta with a combined frequency north of 120 interview occurrences. The trick is that the obvious O(n^2) DP approach works, but the interviewer is almost certainly going to follow up with, "Can you do better?"

TL;DR

Maintain a tails array where tails[i] holds the smallest possible tail element of any increasing subsequence of length i + 1. For each number in the input, binary search tails to find where it belongs. If the number is larger than every element in tails, append it (the LIS just got longer). Otherwise, replace the first element that is greater than or equal to it (keeping future options open). The final answer is tails.length. This runs in O(n log n) time and O(n) space.

Why This Problem Matters

The Longest Increasing Subsequence (LIS) is a textbook dynamic programming problem that doubles as a test of your optimization instincts. Most candidates can reach the O(n^2) DP solution. What separates strong candidates is recognizing that the inner linear scan can be replaced with binary search, dropping the time complexity to O(n log n). That jump from quadratic to near-linear is the kind of insight interviewers look for at companies like Google and Amazon.

Beyond interviews, LIS appears in real systems: version control (finding the longest chain of compatible commits), bioinformatics (sequence alignment), and scheduling (longest chain of non-overlapping intervals).

Understanding the Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from the array by deleting zero or more elements without changing the order of the remaining elements. Critically, the selected elements do not need to be adjacent.

Example 1:

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

One valid LIS is [2, 3, 7, 101]. Another is [2, 3, 7, 18]. Both have length 4, and no strictly increasing subsequence of length 5 exists.

Example 2:

Input:  nums = [0, 1, 0, 3, 2, 3]
Output: 4

Example 3:

Input:  nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1

All elements are equal, so no pair is strictly increasing. The best we can do is a single element.

Constraints:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Edge Cases

1. Already sorted (e.g., [1, 2, 3, 4, 5]): The entire array is the LIS. Answer = n.
2. Sorted in reverse (e.g., [5, 4, 3, 2, 1]): No two elements form an increasing pair. Answer = 1.
3. All duplicates (e.g., [7, 7, 7]): Strictly increasing means no ties. Answer = 1.
4. Two elements (e.g., [3, 2]): Descending, so the answer is 1.

Solution Approach

Starting Point: The O(n^2) DP

The standard DP formulation defines dp[i] as the length of the longest increasing subsequence ending at index i. For each i, you scan all earlier indices j < i and check whether nums[j] < nums[i]. If so, dp[i] = max(dp[i], dp[j] + 1). The answer is the maximum value across all of dp.

This works, but the inner scan is O(n), making the total O(n^2). For n = 2500, that is roughly 6.25 million operations, which passes within time limits but leaves room for improvement. The interviewer will typically ask: "Can you do better?"

The Optimization: Binary Search on Tails

The key observation is that instead of tracking a full DP array, we can maintain a separate array called tails. At any point during the scan, tails[i] stores the smallest tail element of all increasing subsequences of length i + 1 found so far.

Why does this help? Because the tails array is always sorted. If we find a subsequence of length 3 with tail 7, and a subsequence of length 4 with tail 5, that would mean we have a length-4 subsequence ending at 5 that contains a length-3 prefix ending at something less than 5, which is already less than 7. So tails is sorted, and we can binary search it.

For each new number num from the input:

• Binary search tails for the leftmost position where tails[pos] >= num.
• If pos == tails.length, num is larger than everything in tails. Append it. The LIS just grew by one.
• Otherwise, replace tails[pos] with num. This does not change the LIS length, but it keeps tails[pos] as small as possible, leaving room for future elements to extend the sequence.

Tracing Through the Example

For nums = [10, 9, 2, 5, 3, 7, 101, 18], here is how tails evolves:

The first three elements (10, 9, 2) each replace tails[0] because they are all smaller than or equal to the current tail. When 5 arrives, it is larger than 2, so it gets appended.

After processing all eight elements, tails = [2, 3, 7, 18] and its length is 4. That is our answer.

Replacement vs. Append

Understanding when we replace vs. append is the core of this algorithm.

Replace (keeps the LIS length the same but opens up future possibilities):

Here, 9 replaces 10 at position 0. The LIS length stays at 1, but future elements only need to beat 9 instead of 10 to extend the sequence.

Append (the LIS length increases by one):

5 is larger than every element in tails, so it extends the sequence from length 1 to length 2.

The All-Equal Case

When all elements are the same, every number replaces tails[0] and the length never exceeds 1:

This correctly handles the "strictly increasing" constraint since equal values do not count.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {
  public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }

    // tails[i] = smallest tail element of any increasing
    // subsequence of length (i + 1)
    List<Integer> tailElements = new ArrayList<>();

    for (int num : nums) {
      // Binary search for the leftmost position where
      // tailElements[pos] >= num
      int position = Collections.binarySearch(tailElements, num);

      // Collections.binarySearch returns a negative value
      // when not found: -(insertion point) - 1
      if (position < 0) {
        position = -(position + 1);
      }

      if (position == tailElements.size()) {
        // num is larger than all current tails - extend the LIS
        tailElements.add(num);
      } else {
        // Replace to keep the tail as small as possible
        tailElements.set(position, num);
      }
    }

    return tailElements.size();
  }
}

Step-by-Step Breakdown

1. Null/empty check: Return 0 immediately for empty input.
2. Initialize tailElements: An ArrayList that will hold the smallest tail values, one per subsequence length.
3. Iterate through each number: For every element in nums, decide whether to extend or replace.
4. Binary search: Collections.binarySearch returns the index if found, or -(insertion point) - 1 if not found. We convert the negative result to the actual insertion point.
5. Append or replace: If the insertion point equals the list size, num is larger than all existing tails, so we append. Otherwise, we replace the element at that position.
6. Return the length: After processing all elements, the size of tailElements is the LIS length.

Complexity Analysis

Time Complexity: O(n log n)

The outer loop iterates through each of the n elements once. Inside the loop, binary search on the tails array costs O(log n) in the worst case (when tails grows to length n for a fully sorted input). Total: O(n log n).

For n = 2500, this amounts to roughly 28,000 operations, compared to 6.25 million for the O(n^2) approach.

Space Complexity: O(n)

The tails array can grow to at most n elements (when the input is already sorted). No other auxiliary data structures are used.

Common Pitfalls

1. Confusing subsequence with subarray: A subsequence does not require contiguous elements. If you try a sliding-window approach, you are solving a different problem.

2. Using bisect_right instead of bisect_left: Using the right variant (or upper_bound in C++) means equal values get placed after existing duplicates, which would allow ties in the subsequence. The problem requires strictly increasing, so you need bisect_left / lower_bound.

3. Assuming the tails array is the actual LIS: The tails array stores the smallest possible tail for each subsequence length, not one specific subsequence. For input [3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12], the final tails array might not correspond to any single valid increasing subsequence.

4. Forgetting the strictly increasing constraint: Equal elements do not extend the subsequence. Binary search with bisect_left / lower_bound handles this correctly by placing equal values at the same position (replacing, not appending).

Interview Tips

1. Start with the O(n^2) DP: Explain the dp[i] formulation clearly. This shows you understand the problem before optimizing.

2. Transition to the optimization: Point out that the inner scan can be replaced with binary search because the tails array is always sorted. Explain why it is sorted (a longer subsequence cannot have a smaller tail than a shorter one, given how we maintain minimums).

3. Mention patience sorting: If the interviewer seems interested, relate the algorithm to the card game Patience. Each "pile" corresponds to an entry in tails, and binary search finds the correct pile. This analogy demonstrates depth of understanding.

4. Know both approaches: Some interviewers prefer the O(n^2) DP because it is easier to verify correctness and extend (e.g., "now count the number of LIS solutions"). Having both in your toolbox gives you flexibility.

5. Test with edge cases: Walk through the all-equal case [7, 7, 7] and the fully sorted case [1, 2, 3, 4, 5] to show your solution handles boundaries.

Key Takeaways

• The O(n^2) DP defines dp[i] as the LIS length ending at index i and scans all previous indices. It is correct and easy to implement but quadratic.
• The O(n log n) approach maintains a sorted tails array and uses binary search (bisect_left / lower_bound) to decide whether to append or replace. The length of tails at the end is the answer.
• Replacements do not change the LIS length but keep tail values as small as possible, leaving room for future elements to extend the sequence.
• The tails array is always sorted because a longer subsequence cannot have a smaller minimum tail than a shorter one.
• For strictly increasing order, use bisect_left / lower_bound. Using the right variant would incorrectly allow equal elements in the subsequence.

Practice Makes Perfect

Once you are comfortable with this problem, these related challenges build directly on the same ideas:

• Longest Non-Decreasing Subsequence: Switch from bisect_left to bisect_right to allow equal elements.
• Number of Longest Increasing Subsequences: Track counts alongside lengths in the DP formulation.
• Russian Doll Envelopes: Sort envelopes by width, then apply LIS on heights.
• Longest Chain of Pairs: Sort by second element, then apply a greedy/LIS approach.

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed offers at top tech companies. The spaced-repetition system helps you retain these patterns long-term, so they are second nature when interview day arrives.

Solutions in Other Languages

Python

Python's bisect module provides bisect_left, which maps directly to the algorithm. No manual binary search needed.

from typing import List
import bisect

class Solution:
    def length_of_lis(self, nums: List[int]) -> int:
        if not nums:
            return 0

        lis = []
        for num in nums:
            pos = bisect.bisect_left(lis, num)
            if pos == len(lis):
                lis.append(num)
            else:
                lis[pos] = num

        return len(lis)

JavaScript

JavaScript does not have a built-in binary search, so we implement it inline with a standard left/right loop.

class Solution {
  lengthOfLIS(nums) {
    if (nums.length === 0) return 0;

    const tailElements = [];

    for (const num of nums) {
      let left = 0, right = tailElements.length;
      while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (tailElements[mid] < num) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }

      if (left === tailElements.length) {
        tailElements.push(num);
      } else {
        tailElements[left] = num;
      }
    }

    return tailElements.length;
  }
}

TypeScript

Identical logic to JavaScript with explicit type annotations.

class Solution {
  lengthOfLIS(nums: number[]): number {
    if (nums.length === 0) return 0;

    const tailElements: number[] = [];

    for (const num of nums) {
      let left = 0, right = tailElements.length;
      while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (tailElements[mid] < num) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }

      if (left === tailElements.length) {
        tailElements.push(num);
      } else {
        tailElements[left] = num;
      }
    }

    return tailElements.length;
  }
}

C++

C++ provides std::lower_bound, which performs the binary search for us on a sorted container.

#include <vector>
#include <algorithm>

class Solution {
public:
  int lengthOfLIS(std::vector<int> &nums) {
    if (nums.empty()) return 0;

    std::vector<int> lis;
    for (int num : nums) {
      auto it = std::lower_bound(lis.begin(), lis.end(), num);
      if (it == lis.end()) {
        lis.push_back(num);
      } else {
        *it = num;
      }
    }
    return lis.size();
  }
};

Go

Go lacks a built-in lower_bound, so we implement binary search manually with a left/right loop.

package solution

func (s *Solution) LengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    tails := make([]int, 0, len(nums))

    for _, num := range nums {
        left, right := 0, len(tails)
        for left < right {
            mid := left + (right-left)/2
            if tails[mid] < num {
                left = mid + 1
            } else {
                right = mid
            }
        }
        if left == len(tails) {
            tails = append(tails, num)
        } else {
            tails[left] = num
        }
    }

    return len(tails)
}

type Solution struct{}

Scala

Scala's mutable ArrayBuffer paired with a manual binary search loop keeps the approach consistent.

class Solution {
  def lengthOfLIS(nums: Array[Int]): Int = {
    if (nums.isEmpty) return 0

    val tailElements = scala.collection.mutable.ArrayBuffer[Int]()

    for (num <- nums) {
      var left = 0
      var right = tailElements.length

      while (left < right) {
        val mid = left + (right - left) / 2
        if (tailElements(mid) < num) {
          left = mid + 1
        } else {
          right = mid
        }
      }

      if (left == tailElements.length) {
        tailElements += num
      } else {
        tailElements(left) = num
      }
    }

    tailElements.length
  }
}

Kotlin

Kotlin's binarySearch on a MutableList returns a negative insertion-point encoding, similar to Java's Collections.binarySearch.

class Solution {
  fun lengthOfLIS(nums: IntArray): Int {
    if (nums.isEmpty()) {
      return 0
    }

    val tailElements = mutableListOf<Int>()

    for (num in nums) {
      var position = tailElements.binarySearch(num)

      if (position < 0) {
        position = -(position + 1)
      }

      if (position == tailElements.size) {
        tailElements.add(num)
      } else {
        tailElements[position] = num
      }
    }

    return tailElements.size
  }
}

Ruby

Ruby's bsearch_index with a block finds the leftmost element satisfying the condition, returning nil when no element qualifies (meaning num is larger than all tails).

class Solution
  def length_of_lis(nums)
    return 0 if nums.nil? || nums.empty?

    tail_elements = []

    nums.each do |num|
      position = tail_elements.bsearch_index { |x| x >= num }

      if position.nil?
        tail_elements << num
      else
        tail_elements[position] = num
      end
    end

    tail_elements.size
  end
end

Rust

Rust's partition_point on a slice returns the index of the first element for which the predicate returns false, functioning as lower_bound.

pub struct Solution;

impl Solution {
    pub fn length_of_lis(&self, nums: Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }

        let mut tail_elements: Vec<i32> = Vec::new();

        for &num in &nums {
            let position = tail_elements.partition_point(|&x| x < num);

            if position == tail_elements.len() {
                tail_elements.push(num);
            } else {
                tail_elements[position] = num;
            }
        }

        tail_elements.len() as i32
    }
}

Swift

Swift has no built-in lower-bound function, so a manual binary search loop handles the lookup.

import Foundation

class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }

        var tailElements: [Int] = []

        for num in nums {
            var left = 0
            var right = tailElements.count

            while left < right {
                let mid = (left + right) / 2
                if tailElements[mid] < num {
                    left = mid + 1
                } else {
                    right = mid
                }
            }

            if left == tailElements.count {
                tailElements.append(num)
            } else {
                tailElements[left] = num
            }
        }

        return tailElements.count
    }
}

C#

C#'s List<T>.BinarySearch returns a bitwise-complement negative value when the element is not found, similar to Java's convention.

using System.Collections.Generic;

public class Solution {
    public int LengthOfLIS(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }

        var tailElements = new List<int>();

        foreach (int num in nums) {
            int position = tailElements.BinarySearch(num);

            if (position < 0) {
                position = ~position;
            }

            if (position == tailElements.Count) {
                tailElements.Add(num);
            } else {
                tailElements[position] = num;
            }
        }

        return tailElements.Count;
    }
}

Dart

Dart uses integer division (~/) for the midpoint calculation in the manual binary search.

class Solution {
  int lengthOfLIS(List<int> nums) {
    if (nums.isEmpty) {
      return 0;
    }

    List<int> tailElements = [];

    for (int num in nums) {
      int left = 0, right = tailElements.length;
      while (left < right) {
        int mid = (left + right) ~/ 2;
        if (tailElements[mid] < num) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }

      if (left == tailElements.length) {
        tailElements.add(num);
      } else {
        tailElements[left] = num;
      }
    }

    return tailElements.length;
  }
}

PHP

PHP requires a manual binary search since the language has no built-in lower-bound function for sorted arrays.

<?php

class Solution {
    public function lengthOfLIS(array $nums): int {
        if (empty($nums)) {
            return 0;
        }

        $tailElements = [];

        foreach ($nums as $num) {
            $left = 0;
            $right = count($tailElements);

            while ($left < $right) {
                $mid = $left + intdiv($right - $left, 2);
                if ($tailElements[$mid] < $num) {
                    $left = $mid + 1;
                } else {
                    $right = $mid;
                }
            }

            if ($left === count($tailElements)) {
                $tailElements[] = $num;
            } else {
                $tailElements[$left] = $num;
            }
        }

        return count($tailElements);
    }
}