Approach Summary
Patience sorting with binary search: maintain a tails array. Binary search to find where each element goes.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Dynamic Programming Tabulation | O(n^2) | O(n) | Compute dp[i] = max(dp[j] + 1) for all j < i where nums[i] > nums[j]. |
| 2 Approach 2: Patience Sorting & Binary Search (Optimal) | O(n log n) | O(n) | Maintain candidate tail elements in a sorted array and update via binary search in O(n log n). |
Step 1: Baseline
Approach 1: Dynamic Programming Tabulation
Time: O(n^2)
Space: O(n)
Initialize array dp of size n with all 1s since every element by itself forms an increasing subsequence of length 1. For every index i from 1 to n - 1, compare with all earlier elements j from 0 to i - 1. If nums[i] > nums[j], update dp[i] = max(dp[i], dp[j] + 1). Track the overall maximum across all dp entries.
Approach 1: Dynamic Programming Tabulation Implementation
Approach 1: Dynamic Programming Tabulation
class Solution {
public int lengthOfLIS(int[] nums) {
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;
}
}class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
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;
}
};class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
n = len(nums)
dp = [1] * n
max_len = 1
for i in range(1, n):
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_lenfunction lengthOfLIS(nums) {
const n = nums.length;
const dp = new Array(n).fill(1);
let maxLen = 1;
for (let i = 1; i < n; 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;
} Step 2: Most Optimized
Approach 2: Patience Sorting & Binary Search (Optimal)
Time: O(n log n)
Space: O(n)
Maintain an array temp containing the smallest tail of all increasing subsequences found so far. For each number x in nums: if x is strictly larger than the last element of temp, append it (expanding the LIS length). Otherwise, binary search for the first element in temp >= x (its ceiling) and replace it with x. Replacing allows future larger elements to form longer subsequences with lower thresholds without invalidating length.
Approach 2: Patience Sorting & Binary Search (Optimal) Implementation
Approach 2: Patience Sorting & Binary Search (Optimal)
class Solution {
public int cielBinarySearch(List<Integer> temp, int target) {
int left = 0;
int right = temp.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (temp.get(mid) == target) {
return mid;
} else if (temp.get(mid) < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public int lengthOfLIS(int[] nums) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[0]);
for (int i = 1; i < nums.length; i++) {
if (nums[i] > temp.get(temp.size() - 1)) {
temp.add(nums[i]);
} else {
int index = cielBinarySearch(temp, nums[i]);
temp.set(index, nums[i]);
}
}
return temp.size();
}
}class Solution {
public:
int cielBinarySearch(vector<int>& temp, int target) {
int left = 0;
int right = temp.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (temp[mid] == target) {
return mid;
} else if (temp[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
int lengthOfLIS(vector<int>& nums) {
vector<int> temp;
temp.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > temp.back()) {
temp.push_back(nums[i]);
} else {
int index = cielBinarySearch(temp, nums[i]);
temp[index] = nums[i];
}
}
return temp.size();
}
};class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
import bisect
temp = [nums[0]]
for i in range(1, len(nums)):
if nums[i] > temp[-1]:
temp.append(nums[i])
else:
idx = bisect.bisect_left(temp, nums[i])
temp[idx] = nums[i]
return len(temp)function lengthOfLIS(nums) {
function ceilBinarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = (left + right) >> 1;
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
const temp = [nums[0]];
for (let i = 1; i < nums.length; i++) {
if (nums[i] > temp[temp.length - 1]) {
temp.push(nums[i]);
} else {
const idx = ceilBinarySearch(temp, nums[i]);
temp[idx] = nums[i];
}
}
return temp.length;
}Edge Cases to Watch
- Array is strictly descending (e.g. [5, 4, 3, 2, 1]; LIS length is 1)
- Array is strictly ascending (e.g. [1, 2, 3, 4, 5]; LIS length is n)
- Array has duplicates (e.g. [7, 7, 7, 7]; strictly increasing condition requires unique values; LIS is 1)
- Single element array (returns 1 immediately)
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- LIS length
- Strictly increasing subsequence
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(n)
Tags
Array DP Binary Search
Frequently Asked Questions
What is the optimal time and space complexity for Longest Increasing Subsequence?
The optimal solution for Longest Increasing Subsequence achieves O(n log n) runtime complexity and requires O(n) auxiliary space. For Approach 1, nested loops yield O(n^2) time and O(n) space. For Approach 2, processing n elements with O(log n) binary search per element achieves O(n log n) time and O(n) space.
How do I identify that Longest Increasing Subsequence requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: LIS length; Strictly increasing subsequence. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Longest Increasing Subsequence?
Essential edge cases to verify include: Array is strictly descending (e.g. [5, 4, 3, 2, 1]; LIS length is 1); Array is strictly ascending (e.g. [1, 2, 3, 4, 5]; LIS length is n); Array has duplicates (e.g. [7, 7, 7, 7]; strictly increasing condition requires unique values; LIS is 1); Single element array (returns 1 immediately). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Longest Increasing Subsequence?
Longest Increasing Subsequence is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Google, Amazon, Microsoft.