Longest Increasing Subsequence solution and explanation
TCS
Google
Infosys
9 more videos on this problem
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300NeetCode · 18:13 · 537K views
DP 43. Longest Increasing Subsequence | Binary Search | Intuitiontake U forward · 16:27 · 378K views
Longest Increasing Subsequence (LeetCode 300) | Detailed solution with animations and diagramsNikhil Lohia · 28:11 · 42K views
Longest Increasing Subsequence - Leetcode 300 - Dynamic Programming (Python)Greg Hogg · 8:32 · 24K views
Longest Increasing Subsequence Problem Explained | Leetcode 300 | Dynamic ProgrammingByteQuest · 5:06 · 11K views
Longest Increasing Subsequence NlogN | Leetcode #300 | LISTechdose · 21:00 · 8K views
LeetCode 300. Longest Increasing Subsequence - O(n log n)Kacy Codes · 10:24 · 6K views
Longest Increasing Subsequence - LeetCode 300 - Python - O(nlog(n))Deepti Talesra · 16:13 · 4K views
Longest Increasing Subsequence - LeetCode 300 - Binary Search - Coding InterviewOne Code Man · 8:35 · 3K views
Longest Increasing Subsequence | LeetCode 300 O(n log n)Destination FAANG · 25:15 · 1K views
The problem
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
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
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Approach overview
Problem Overview: Given an integer array nums, return the length of the longest strictly increasing subsequence (LIS). A subsequence does not need to be contiguous, but the relative order of elements must remain the same.
Approach 1: Dynamic Programming (O(n^2) time, O(n) space)
This approach builds the solution incrementally. Create a DP array where dp[i] stores the length of the longest increasing subsequence that ends at index i. For each element, iterate through all previous elements and check if nums[j] < nums[i]. If the condition holds, update dp[i] = max(dp[i], dp[j] + 1). The final answer is the maximum value in the DP array. This method works well for understanding how subsequences grow over time and is often the first solution expected in interviews when discussing Dynamic Programming. Time complexity is O(n^2) due to the nested loops, and space complexity is O(n) for the DP array.
Approach 2: Optimized DP with Binary Search (Patience Sorting) (O(n log n) time, O(n) space)
The optimized solution tracks the smallest possible tail value for increasing subsequences of different lengths. Maintain an array tails where tails[k] represents the minimum ending value of an increasing subsequence of length k+1. Iterate through the input array and use binary search to find the position where the current number should replace an element in tails. Replacing keeps subsequences flexible for future numbers while maintaining sorted order. The size of the tails array at the end equals the LIS length. Each insertion uses binary search, giving O(log n) per element and overall O(n log n) time with O(n) space. This method combines ideas from Binary Search and Array processing, and it is the standard optimal solution used in high-performance implementations.
Recommended for interviews: Start by explaining the O(n^2) dynamic programming approach. It clearly demonstrates how subsequences are formed and shows your reasoning process. Then move to the O(n log n) patience sorting optimization. Interviewers often expect candidates to recognize this improvement because it reduces quadratic scanning using binary search while preserving the subsequence length logic.
Approach 1: Dynamic Programming Approach
This approach uses dynamic programming to solve the problem in O(n^2) time complexity. We maintain a dp array where dp[i] represents the length of the longest increasing subsequence that ends with nums[i]. For each element, we iterate over all previous elements to see if they can be included in the subsequence ending at the current element, and update dp[i] accordingly.
class Solution:
def lengthOfLIS(self, nums):
if not nums:
return 0
dp = [1] * len(nums)
max_len = 1
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
max_len = max(max_len, dp[i])
return max_len
# Example usage:
nums = [10,9,2,5,3,7,101,18]
sol = Solution()
print(sol.lengthOfLIS(nums))import java.util.*;
public class LongestIncreasingSubsequence {
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[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
public static void main(String[] args) {
LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
int[] nums = {10,9,2,5,3,7,101,18};
System.out.println(lis.lengthOfLIS(nums));
}
}#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
int maxLen = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
int main() {
vector<int> nums = {10,9,2,5,3,7,101,18};
cout << lengthOfLIS(nums) << endl;
return 0;
}function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const dp = Array(nums.length).fill(1);
let maxLen = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
console.log(lengthOfLIS([10,9,2,5,3,7,101,18]));#include <stdio.h>
#include <string.h>
int lengthOfLIS(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int dp[numsSize];
memset(dp, 0, sizeof(dp));
int maxLen = 1;
for (int i = 0; i < numsSize; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
maxLen = maxLen > dp[i] ? maxLen : dp[i];
}
return maxLen;
}
int main() {
int nums[] = {10,9,2,5,3,7,101,18};
int length = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", lengthOfLIS(nums, length));
return 0;
}using System;
public class Solution {
public int LengthOfLIS(int[] nums) {
if (nums == null || nums.Length == 0) return 0;
int n = nums.Length;
int[] dp = new int[n];
Array.Fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
maxLen = Math.Max(maxLen, dp[i]);
}
return maxLen;
}
public static void Main() {
int[] nums = {10,9,2,5,3,7,101,18};
Solution sol = new Solution();
Console.WriteLine(sol.LengthOfLIS(nums));
}
}In Python, we use a list comprehension to initialize the dp array, then apply the nested loops to update the dp as in other examples.
Time Complexity: O(n^2). Space Complexity: O(n).
Approach 2: Optimized DP with Binary Search (Patience Sorting)
In this approach, we use a combination of dynamic programming and binary search to solve the problem in O(n log n) time. This is often called the 'patience sorting' technique where we maintain a list, 'ends', to store the smallest ending value of any increasing subsequence with length i+1 in 'ends[i]'. We use binary search to find the position where each element in nums can be placed in 'ends'.
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums):
ends = []
for num in nums:
pos = bisect_left(ends, num)
if pos < len(ends):
ends[pos] = num
else:
ends.append(num)
return len(ends)
# Example usage:
nums = [10,9,2,5,3,7,101,18]
sol = Solution()
print(sol.lengthOfLIS(nums))import java.util.*;
public class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
List<Integer> ends = new ArrayList<>();
for (int num : nums) {
int pos = Collections.binarySearch(ends, num);
if (pos < 0) pos = -(pos + 1);
if (pos < ends.size()) {
ends.set(pos, num);
} else {
ends.add(num);
}
}
return ends.size();
}
public static void main(String[] args) {
LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
int[] nums = {10,9,2,5,3,7,101,18};
System.out.println(lis.lengthOfLIS(nums));
}
}#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
vector<int> ends;
for (int num : nums) {
auto it = lower_bound(ends.begin(), ends.end(), num);
if (it == ends.end()) ends.push_back(num);
else *it = num;
}
return ends.size();
}
int main() {
vector<int> nums = {10,9,2,5,3,7,101,18};
cout << lengthOfLIS(nums) << endl;
return 0;
}function lengthOfLIS(nums) {
const ends = [];
for (let num of nums) {
let i = 0, j = ends.length;
while (i < j) {
let mid = Math.floor((i + j) / 2);
if (ends[mid] < num) i = mid + 1;
else j = mid;
}
if (i < ends.length) ends[i] = num;
else ends.push(num);
}
return ends.length;
}
console.log(lengthOfLIS([10,9,2,5,3,7,101,18]));#include <stdio.h>
#include <stdlib.h>
int comparator(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int lowerBound(int *arr, int size, int value) {
int low = 0, high = size;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
int lengthOfLIS(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int* ends = (int*)malloc(numsSize * sizeof(int));
int length = 0;
for (int i = 0; i < numsSize; ++i) {
int pos = lowerBound(ends, length, nums[i]);
ends[pos] = nums[i];
if (pos == length) {
length++;
}
}
free(ends);
return length;
}
int main() {
int nums[] = {10,9,2,5,3,7,101,18};
int length = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", lengthOfLIS(nums, length));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int LengthOfLIS(int[] nums) {
List<int> ends = new List<int>();
foreach (var num in nums) {
int idx = ends.BinarySearch(num);
if (idx < 0) idx = ~idx;
if (idx < ends.Count) {
ends[idx] = num;
} else {
ends.Add(num);
}
}
return ends.Count;
}
public static void Main() {
int[] nums = {10,9,2,5,3,7,101,18};
Solution sol = new Solution();
Console.WriteLine(sol.LengthOfLIS(nums));
}
}Python solution makes use of the bisect module to apply binary search on the list 'ends'. This approach ensures finding the right position for each element in logarithmic time.
Time Complexity: O(n log n). Space Complexity: O(n).
Approach 3: Default Approach
function lengthOfLIS(nums: number[]): number {
const n = nums.length;
const f: number[] = new Array(n).fill(1);
for (let i = 1; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
}
return Math.max(...f);
}func lengthOfLIS(nums []int) int {
n := len(nums)
f := make([]int, n)
for i := range f {
f[i] = 1
}
ans := 1
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
f[i] = max(f[i], f[j]+1)
ans = max(ans, f[i])
}
}
}
return ans
}impl Solution {
pub fn length_of_lis(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut f = vec![1; n];
for i in 1..n {
for j in 0..i {
if nums[j] < nums[i] {
f[i] = f[i].max(f[j] + 1);
}
}
}
*f.iter().max().unwrap()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2). Space Complexity: O(n). |
| Optimized DP with Binary Search (Patience Sorting) | Time Complexity: O(n log n). Space Complexity: O(n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n^2) | O(n) | Best for learning the LIS concept and explaining the logic step by step in interviews. |
| Optimized DP with Binary Search (Patience Sorting) | O(n log n) | O(n) | Preferred for large arrays and production-quality solutions where performance matters. |
Frequently asked questions
Is Longest Increasing Subsequence easy or hard?
Longest Increasing Subsequence is typically classified as a medium-level problem. The dynamic programming solution is conceptually straightforward, but recognizing and implementing the O(n log n) binary search optimization requires stronger algorithmic intuition.
Longest Increasing Subsequence Python/Java solution
Most implementations use either the O(n^2) DP approach or the O(n log n) binary search optimization. Both solutions are straightforward to implement in Python, Java, C++, and JavaScript using arrays and standard binary search utilities.
How to solve Longest Increasing Subsequence in O(n log n)?
Maintain an array called tails where tails[i] stores the smallest ending value of an increasing subsequence of length i+1. For each number in the input, perform a binary search on tails to find its position and replace the value there. The final size of the tails array equals the LIS length.
What is the best approach for Longest Increasing Subsequence?
The optimal approach uses a patience sorting technique with binary search. It maintains a tails array where each index represents the minimum possible ending value of an increasing subsequence of that length. Each element is placed using binary search, resulting in O(n log n) time and O(n) space complexity.
Is Longest Increasing Subsequence asked at Google/Amazon/Meta?
Longest Increasing Subsequence is a common dynamic programming interview problem asked at companies such as Google, Amazon, Meta, and Microsoft. Variations of LIS also appear in competitive programming and system design screening rounds because they test DP optimization skills.
What data structure is used in Longest Increasing Subsequence?
The basic solution uses a dynamic programming array to store subsequence lengths. The optimized solution uses an array combined with binary search to maintain the smallest possible tail values for subsequences of different lengths.
What is the time complexity of Longest Increasing Subsequence?
Two common solutions exist. The classic dynamic programming method runs in O(n^2) time with O(n) space by comparing each element with all previous elements. The optimized solution uses binary search and runs in O(n log n) time with O(n) space.