Longest Increasing Subsequence

Medium Problem 123 of 151 Java and Python

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.

Example 1

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

Example 2

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

Example 3

Input: nums = [7, 7, 7, 7]
Output: 1
Why: Equal values do not count as increasing.

Constraints

1 ≤ nums.length ≤ 2500
Follow-up: O(n log n).

Explanation

O(n²) DP: lis[i] = longest increasing subsequence ending at i = 1 + the best lis[j] among earlier j with nums[j] < nums[i].

O(n log n): keep tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. tails stays sorted, so for each number, binary-search where it goes: replace the first tail ≥ it, or append it if it is bigger than all.

Approach 1 · Better

DP over ending positions

Time O(n²)
Space O(n)

For each index, extend the best subsequence ending at any smaller earlier value.

lis[i] = 1 for all i.
For each i, for each j < i with nums[j] < nums[i]: lis[i] = max(lis[i], lis[j] + 1).
Return the maximum of lis.

Java

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] lis = new int[nums.length];
        Arrays.fill(lis, 1);
        int best = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
            best = Math.max(best, lis[i]);
        }
        return best;
    }
}

Python

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lis = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    lis[i] = max(lis[i], lis[j] + 1)
        return max(lis)

Approach 2 · Optimal

Tails array with binary search

Time O(n log n)
Space O(n)

Maintain the smallest tail for every subsequence length. Each number either extends the longest one or lowers a tail.

For each number, find the first index in tails whose value is ≥ it (lower bound).
If that index is the end, append the number; otherwise overwrite that tail.
Return the length of tails.

Java

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int num : nums) {
            int lo = 0;
            int hi = size;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails[mid] < num) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            tails[lo] = num;
            if (lo == size) {
                size++;
            }
        }
        return size;
    }
}

Python

from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for num in nums:
            i = bisect_left(tails, num)
            if i == len(tails):
                tails.append(num)
            else:
                tails[i] = num
        return len(tails)

Complexity compared

Approach	Time	Space
Better DP over ending positions	O(n²)	O(n)
Optimal Tails array with binary search	O(n log n)	O(n)

Key takeaways

tails is not an actual subsequence, only the best possible endings; its length is the answer.
Use lower bound (bisect_left) for strictly increasing, upper bound for non-decreasing.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem