Longest Increasing Subsequence

Problem Statement

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

What to notice first

• A subsequence doesn’t need to be contiguous.
• The order of elements must be preserved from the original array.
• “Strictly increasing” means each element must be strictly greater than the previous.
• You only need to return the length, not the subsequence itself.

Examples

nums	Output	Explanation
[10,9,2,5,3,7,101,18]	4	The longest increasing subsequence is [2,3,7,101] with length 4
[0,1,0,4,4,4,3,2,1]	2	The longest increasing subsequence is [0,1] or [0,4] with length 2
[3,1,4,1,5,9,2,6,5,3,5]	4	One possible LIS: [1,4,5,9] or [1,2,5,9] or [1,2,3,5]

Constraints

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

Real-World Applications

Where this pattern appears

• Stock price analysis — finding the longest period of consistently rising prices.
• Data compression — identifying longest increasing runs in datasets.
• Seismic data processing — locating increasing event sequences.
• Version tracking — finding longest sequence of version improvements.

Complexity Comparison

Approach	Time	Space	Best For
DP	O(n²)	O(n)	Easier to understand and code
Binary Search	O(n log n)	O(n)	Large arrays, optimal complexity

Which approach should you learn first?

• Pick DP if you want the foundational approach and clearer logic.
• Pick Binary Search if you want optimal complexity and algorithmic sophistication.

Clearer Logic

DP

O(n²) time · O(n) space

Optimal Complexity

Binary Search

O(n log n) time · O(n) space

Approach 1: Dynamic Programming O(n²)

★ Recommended

dp[i] = length of the longest increasing subsequence ending at index i.

For each i, check all previous indices j where nums[j] < nums[i], and extend the best LIS found.

⏱ Time O(n²) Nested loops 💾 Space O(n) DP array

Pseudocode

function lisDP(nums):
    n = len(nums)
    dp = array of size n, all initialized to 1

    for i from 1 to n - 1:
        for j from 0 to i - 1:
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Solution Code

Python

longest_increasing_subsequence_dp_n2.py

from typing import List


def longest_increasing_subsequence_dp(nums: List[int]) -> int:
    """
    Find length of longest increasing subsequence using DP O(n²).

    Time Complexity: O(n²)
    Space Complexity: O(n)

    dp[i] = length of LIS ending at index i
    For each i, check all j < i where nums[j] < nums[i]
    dp[i] = max(dp[j]) + 1 for all valid j, or 1 if no such j exists
    """
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n  # Each element is a LIS of length 1

    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)


if __name__ == "__main__":
    print(longest_increasing_subsequence_dp([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
    print(longest_increasing_subsequence_dp([0, 1, 0, 4, 4, 4, 3, 2, 1]))   # 2
    print(longest_increasing_subsequence_dp([3, 1, 4, 1, 5, 9, 2, 6]))      # 4

C++

lis_dp_n2.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Find length of longest increasing subsequence using DP O(n²).
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n)
 */
int lisDP(vector<int>& nums) {
    if (nums.empty()) return 0;

    int n = nums.size();
    vector<int> dp(n, 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);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> test1 = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lisDP(test1) << endl;  // 4
    return 0;
}

Java

LIsDpN2.java

/**
 * Find length of longest increasing subsequence using DP O(n²).
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n)
 */
public class LIsDpN2 {
    public static int lisDP(int[] nums) {
        if (nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }

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

        int max = 0;
        for (int val : dp) {
            max = Math.max(max, val);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(lisDP(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));  // 4
    }
}

JavaScript

lis_dp_n2.js

/**
 * Find length of longest increasing subsequence using DP O(n²).
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n)
 */
function lisDP(nums) {
    if (nums.length === 0) return 0;

    const dp = new Array(nums.length).fill(1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp);
}

console.log(lisDP([10, 9, 2, 5, 3, 7, 101, 18]));  // 4

Rust

lis_dp_n2.rs

/**
 * Find length of longest increasing subsequence using DP O(n²).
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n)
 */
pub fn lis_dp(nums: Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut dp = vec![1; nums.len()];

    for i in 1..nums.len() {
        for j in 0..i {
            if nums[j] < nums[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }

    *dp.iter().max().unwrap()
}

fn main() {
    println!("{}", lis_dp(vec![10, 9, 2, 5, 3, 7, 101, 18]));  // 4
}

Go

lis_dp_n2.go

package main

import "fmt"

/*
 * Find length of longest increasing subsequence using DP O(n²).
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n)
 */
func lisDP(nums []int) int {
  if len(nums) == 0 {
    return 0
  }

  dp := make([]int, len(nums))
  for i := 0; i < len(nums); i++ {
    dp[i] = 1
  }

  for i := 1; i < len(nums); i++ {
    for j := 0; j < i; j++ {
      if nums[j] < nums[i] {
        if dp[i] < dp[j]+1 {
          dp[i] = dp[j] + 1
        }
      }
    }
  }

  maxVal := 0
  for _, val := range dp {
    if val > maxVal {
      maxVal = val
    }
  }
  return maxVal
}

func main() {
  fmt.Println(lisDP([]int{10, 9, 2, 5, 3, 7, 101, 18}))  // 4
}

Approach 2: Binary Search O(n log n)

🎯 Interview Favourite

Maintain a tails array where tails[i] is the smallest tail element of all LIS of length i+1.

For each number, use binary search to find its position in tails. If the position is at the end, we extend the longest LIS; otherwise, we update the tail to possibly get a better LIS.

⏱ Time O(n log n) Binary search per element 💾 Space O(n) Tails array

Key Insight

The tails array maintains the invariant that tails is strictly increasing and sorted. At any point, tails[i] contains the smallest possible tail value for an LIS of length i+1. This allows us to use binary search to efficiently find where a new number fits.

Pseudocode

function lisBinarySearch(nums):
    tails = empty array

    for num in nums:
        pos = binary_search_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(tails)

Solution Code

Python

longest_increasing_subsequence_bs.py

from typing import List
import bisect


def longest_increasing_subsequence_binary_search(nums: List[int]) -> int:
    """
    Find length of longest increasing subsequence using binary search O(n log n).

    Time Complexity: O(n log n)
    Space Complexity: O(n)

    Maintain array 'tails' where tails[i] = smallest tail of all LIS of length i+1
    For each num:
    - Find position in tails using binary search
    - If position = len(tails), extend the longest subsequence
    - Otherwise, replace the value at that position (better tail found)
    """
    if not nums:
        return 0

    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)


if __name__ == "__main__":
    print(longest_increasing_subsequence_binary_search([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
    print(longest_increasing_subsequence_binary_search([0, 1, 0, 4, 4, 4, 3, 2, 1]))   # 2
    print(longest_increasing_subsequence_binary_search([3, 1, 4, 1, 5, 9, 2, 6]))      # 4

C++

lis_binary_search.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Find length of longest increasing subsequence using binary search O(n log n).
 *
 * Time Complexity: O(n log n)
 * Space Complexity: O(n)
 */
int lisBinarySearch(vector<int>& nums) {
    if (nums.empty()) return 0;

    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();
}

int main() {
    vector<int> test1 = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lisBinarySearch(test1) << endl;  // 4
    return 0;
}

Java

LIsBinarySearch.java

import java.util.*;

/**
 * Find length of longest increasing subsequence using binary search O(n log n).
 *
 * Time Complexity: O(n log n)
 * Space Complexity: O(n)
 */
public class LIsBinarySearch {
    public static int lisBinarySearch(int[] nums) {
        if (nums.length == 0) return 0;

        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();
    }

    public static void main(String[] args) {
        System.out.println(lisBinarySearch(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));  // 4
    }
}

JavaScript

lis_binary_search.js

/**
 * Find length of longest increasing subsequence using binary search O(n log n).
 *
 * Time Complexity: O(n log n)
 * Space Complexity: O(n)
 */
function lisBinarySearch(nums) {
    if (nums.length === 0) return 0;

    const tails = [];

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

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

    return tails.length;
}

console.log(lisBinarySearch([10, 9, 2, 5, 3, 7, 101, 18]));  // 4

Rust

lis_binary_search.rs

/**
 * Find length of longest increasing subsequence using binary search O(n log n).
 *
 * Time Complexity: O(n log n)
 * Space Complexity: O(n)
 */
pub fn lis_binary_search(nums: Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut tails = Vec::new();

    for num in nums {
        let pos = tails.binary_search(&num).unwrap_or_else(|e| e);

        if pos == tails.len() {
            tails.push(num);
        } else {
            tails[pos] = num;
        }
    }

    tails.len() as i32
}

fn main() {
    println!("{}", lis_binary_search(vec![10, 9, 2, 5, 3, 7, 101, 18]));  // 4
}

Go

lis_binary_search.go

package main

import (
  "fmt"
  "sort"
)

/*
 * Find length of longest increasing subsequence using binary search O(n log n).
 *
 * Time Complexity: O(n log n)
 * Space Complexity: O(n)
 */
func lisBinarySearch(nums []int) int {
  if len(nums) == 0 {
    return 0
  }

  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)
}

func main() {
  fmt.Println(lisBinarySearch([]int{10, 9, 2, 5, 3, 7, 101, 18}))  // 4
}

Common mistakes

Watch for these pitfalls

• Confusing “subsequence” (non-contiguous, order-preserving) with “subarray” (contiguous).
• Initializing dp array to 0 instead of 1 (every element is a LIS of length 1).
• In binary search approach, using the wrong comparison or update logic.
• Forgetting that binary search requires the tails array to remain strictly increasing.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

longest_increasing_subsequence_space_optimized.py

"""
Solution for Longest Increasing Subsequence
"""

def solve():
    """Implementation for approach 3 of Longest Increasing Subsequence"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

longest_increasing_subsequence_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Longest Increasing Subsequence
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

LongestIncreasingSubsequenceSpaceOptimized.java

/**
 * Solution for Longest Increasing Subsequence
 * Approach 3
 */
public class LongestIncreasingSubsequenceSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

longest_increasing_subsequence_space_optimized.js

/**
 * Solution for Longest Increasing Subsequence
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

longest_increasing_subsequence_space_optimized.rs

/// Solution for Longest Increasing Subsequence
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

longest_increasing_subsequence_space_optimized.go

package main

import "fmt"

// Solution for Longest Increasing Subsequence
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Longest Continuous Increasing Subsequence ↗ Easy #674
• Longest Common Subsequence ↗ Medium #1143
• Russian Doll Envelopes ↗ Hard #354
• House Robber ↗ Medium #198

Interview Tips

Key trade-offs to discuss

• DP simplicity vs Binary Search efficiency: DP is easier to code but slower. Binary Search is faster but requires understanding of the tails invariant.
• Reconstructing the actual subsequence: Both approaches can be modified to track the actual indices. The DP version is slightly easier.
• Why binary search works: The tails array maintains a sorted, strictly increasing sequence. Inserting a smaller value at a position doesn’t break the invariant.
• Space optimization: Both use O(n) space. DP stores the full state; binary search stores minimal necessary information.

← Previous
#299 Bulls and Cows Next
#301 Remove Invalid Parentheses →