Longest Increasing Subsequence

Problem Description

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

Examples

Constraints

• 1 ≤ nums.length ≤ 2500
• -10⁴ ≤ nums[i] ≤ 10⁴

Replacing Larger Values in a Monotonic List

A standard dynamic programming approach uses an array dp where dp[i] represents the length of the LIS ending at index i. For each node, we scan all previous nodes and update dp[i] = 1 + max(dp[j]) for all nums[j] < nums[i]. This runs in O(n²) time.

To optimize to O(n log n) time, we can maintain an active subsequence list sub. We iterate through nums:

• If the current number x is larger than the last element of sub, we append it to sub.
• If x is smaller or equal, we find the first element in sub that is greater than or equal to x (using binary search) and replace it with x.

Replacing a larger value with a smaller value does not change the length of our subsequence, but it decreases the values inside sub, making it easier for future numbers to be appended. At the end of the scan, the length of sub is the length of the LIS.

Solution 1: Dynamic Programming (O(n²) Baseline)

Use a DP array to store the maximum LIS ending at each index.

import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        dp = [1] * n
        max_len = 1

        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], 1 + dp[j])
            max_len = max(max_len, dp[i])

        return max_len

#include <vector>
#include <algorithm>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        std::vector<int> dp(n, 1);
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = std::max(dp[i], 1 + dp[j]);
                }
            }
            maxLen = std::max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

Complexity Analysis:

• Time Complexity: O(n²). Nested loops check all previous indices for each element.
• Space Complexity: O(n) to store the DP array.

Where it breaks: If the array size is 10⁵, this quadratic solution will time out. The binary search approach below is required for large inputs.

Solution 2: Binary Search / Patience Sorting (O(n log n) Optimal)

Maintain a list sub of active LIS candidate elements. Use binary search to find insertion points for replacements.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> sub = new ArrayList<>();
        for (int x : nums) {
            int idx = Collections.binarySearch(sub, x);
            if (idx < 0) idx = -(idx + 1); // convert insertion point

            if (idx == sub.size()) {
                sub.add(x); // append if larger than all elements
            } else {
                sub.set(idx, x); // replace to optimize boundaries
            }
        }
        return sub.size();
    }
}

import bisect


class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        sub = []
        for x in nums:
            idx = bisect.bisect_left(sub, x)
            if idx == len(sub):
                sub.append(x)  # append if larger than all elements
            else:
                sub[idx] = x  # replace to optimize boundaries
        return len(sub)

#include <vector>
#include <algorithm>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        std::vector<int> sub;
        for (int x : nums) {
            auto it = std::lower_bound(sub.begin(), sub.end(), x);
            if (it == sub.end()) {
                sub.push_back(x); // append if larger than all elements
            } else {
                *it = x; // replace to optimize boundaries
            }
        }
        return sub.size();
    }
};

Complexity Analysis:

• Time Complexity: O(n log n). We iterate through the n elements, running a binary search lower_bound O(log n) at each step.
• Space Complexity: O(n) to store the sub array in the worst case (already sorted array).

Where it breaks: The elements inside sub at the end do not represent the actual longest increasing subsequence values (e.g. [10, 2, 5] yields sub = [2, 5], which matches the length of 2 but is not the only representation). It only guarantees correct length tracking. If you need to print the actual subsequence, you must track predecessor index arrays.

Common Mistakes

• Incorrectly converting the binary search return value in Java. Collections.binarySearch returns -(insertion point) - 1 if the value is not found. You must restore it as -(idx + 1) before inserting.
• Using upper_bound instead of lower_bound in C++. lower_bound finds the first element >= x, which enforces the strictly increasing condition. upper_bound finds elements > x, which permits duplicate values in the subsequence.
• Thinking that sub stores the actual LIS values. The values inside sub are intermediate boundary optimizations. Do not use them as the final path.

Frequently Asked Questions

Why does replacing elements keep the length correct? Replacing a larger value with a smaller value decreases the threshold for future nodes to append. For example, if we have sub = [10] and process 2, we update to sub = [2]. The length remains 1, but future values (like 5) can now be appended.

What is this algorithm called? It is often referred to as Patience Sorting, which originates from the card game Patience.

What does this problem test in interviews? It tests your capability to transition from simple O(n²) DP tabulation to optimal O(n log n) structures using binary search insertion.

← All Problems