Longest Increasing Subsequence

medium
Dynamic ProgrammingArrayDynamic ProgrammingBinary Search

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.

Examples

Example 1

  • Input: nums = [10,9,2,5,3,7,101,18]
  • Output: 4
  • Explanation: The longest increasing subsequence is [2,3,7,101] with length 4.

Example 2

  • Input: nums = [0,1,0,3,2,3]
  • Output: 4
  • Explanation: The longest increasing subsequence is [0,1,2,3].

Example 3

  • Input: nums = [7,7,7,7,7,7,7]
  • Output: 1
  • Explanation: Every element is the same, so the longest increasing subsequence has length 1.

Constraints

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

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

We can generate all possible subsequences and check which ones are strictly increasing, returning the length of the longest one. For each element, we decide whether to include it (if it is greater than the previous element in the subsequence) or skip it. This explores all 2^n subsets, leading to exponential time.

Algorithm

  1. Define a recursive function with parameters: current index and the value of the last chosen element.
  2. At each index, either skip the element or include it (if it is greater than the last chosen element).
  3. Return the maximum length found among all valid choices.
TimeO(2^n)SpaceO(n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int helper(vector<int>& nums, int idx, int prev) {
        if (idx == nums.size()) return 0;
        int skip = helper(nums, idx + 1, prev);
        int take = 0;
        if (nums[idx] > prev) {
            take = 1 + helper(nums, idx + 1, nums[idx]);
        }
        return max(skip, take);
    }

    int lengthOfLIS(vector<int>& nums) {
        return helper(nums, 0, INT_MIN);
    }
};
Java 21
class Solution {
    private int helper(int[] nums, int idx, int prev) {
        if (idx == nums.length) return 0;
        int skip = helper(nums, idx + 1, prev);
        int take = 0;
        if (nums[idx] > prev) {
            take = 1 + helper(nums, idx + 1, nums[idx]);
        }
        return Math.max(skip, take);
    }

    public int lengthOfLIS(int[] nums) {
        return helper(nums, 0, Integer.MIN_VALUE);
    }
}
Python 3.12
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def helper(idx: int, prev: float) -> int:
            if idx == len(nums):
                return 0
            skip = helper(idx + 1, prev)
            take = 0
            if nums[idx] > prev:
                take = 1 + helper(idx + 1, nums[idx])
            return max(skip, take)

        return helper(0, float('-inf'))
Go 1.26
func lengthOfLIS(nums []int) int {
    var helper func(idx int, prev int) int
    helper = func(idx int, prev int) int {
        if idx == len(nums) {
            return 0
        }
        skip := helper(idx+1, prev)
        take := 0
        if nums[idx] > prev {
            take = 1 + helper(idx+1, nums[idx])
        }
        if skip > take {
            return skip
        }
        return take
    }
    return helper(0, -1<<31)
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Define dp[i] as the length of the longest increasing subsequence ending at index i. For each element, look at all previous elements: if nums[j] < nums[i], then we can extend the subsequence ending at j. The recurrence is dp[i] = max(dp[j] + 1) for all valid j < i. The answer is the maximum value in the dp array.

Algorithm

  1. Create array `dp` of size `n`, filled with `1` (each element is a subsequence of length 1).
  2. For each index `i` from 1 to `n-1`, iterate over all `j < i`.
  3. If `nums[j] < nums[i]`, update `dp[i] = max(dp[i], dp[j] + 1)`.
  4. Return the maximum value in `dp`.
TimeO(n^2)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
Java 21
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 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], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
Python 3.12
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
Go 1.26
func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    ans := 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
            }
        }
        if dp[i] > ans {
            ans = dp[i]
        }
    }
    return ans
}
Approach 3

Binary Search with Patience Sorting

Intuition

Maintain a list tails where tails[i] is the smallest tail element of all increasing subsequences of length i + 1. For each element in nums, use binary search to find its position in tails. If it is larger than all elements, append it; otherwise, replace the first element that is greater than or equal to it. The length of tails at the end is the answer.

Algorithm

  1. Initialize an empty array `tails`.
  2. For each number in `nums`, binary search for the leftmost position in `tails` where the value is `>= num`.
  3. If the position equals the length of `tails`, append the number; otherwise, replace `tails[pos]` with the number.
  4. Return the length of `tails`.
TimeO(n log n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int num : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), num);
            if (it == tails.end()) {
                tails.push_back(num);
            } else {
                *it = num;
            }
        }
        return tails.size();
    }
};
Java 21
class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int num : nums) {
            int pos = Collections.binarySearch(tails, num);
            if (pos < 0) pos = -(pos + 1);
            if (pos == tails.size()) {
                tails.add(num);
            } else {
                tails.set(pos, num);
            }
        }
        return tails.size();
    }
}
Python 3.12
from typing import List
import bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for num in nums:
            pos = bisect.bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num
        return len(tails)
Go 1.26
func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, num := range nums {
        pos := sort.SearchInts(tails, num)
        if pos == len(tails) {
            tails = append(tails, num)
        } else {
            tails[pos] = num
        }
    }
    return len(tails)
}

Frequently asked questions

What is the optimal time complexity of Longest Increasing Subsequence?

The most efficient approach in this guide ("Binary Search with Patience Sorting") runs in O(n log n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Longest Increasing Subsequence use?

Longest Increasing Subsequence is a medium-level Dynamic Programming problem involving Array, Dynamic Programming, Binary Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Longest Increasing Subsequence be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the recursion stack, while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[10,9,2,5,3,7,101,18]
Expected Output
4