Longest Increasing Subsequence
Problem
Given an integer array nums, return the length of the longest strictly increasing subsequence.
- 1 ≤ nums.length ≤ 2500
- −10⁴ ≤ nums[i] ≤ 10⁴
Example
nums = [10,9,2,5,3,7,101,18]4The longest increasing subsequence is [2,3,7,101], which has length 4. The algorithm uses recursion with memoization to compute the LIS ending at each index. For example, at index 6 (value 101), it checks all previous indices with smaller values (like 7 at index 5) and builds upon their LIS lengths. The critical moment is recognizing that the LIS ending at index 6 is 1 plus the maximum LIS among all indices with smaller values before it. Memoization avoids redundant recomputation by caching results for each index.
Approach
Straightforward Solution
A brute-force approach tries all subsequences, which is exponential in time and infeasible for large inputs.
Core Observation
The length of the longest increasing subsequence ending at position i depends on the lengths of all increasing subsequences ending at positions before i with smaller values. This exhibits optimal substructure and overlapping subproblems, making it a natural fit for dynamic programming.
Path to Optimal
Recognizing the problem's optimal substructure allows defining a recursive function dp(i) that returns the LIS length ending at index i. For each i, dp(i) is 1 plus the maximum dp(j) for all j < i where nums[j] < nums[i]. Memoization caches these results to avoid recomputation, reducing the complexity drastically.
Optimal Approach
Implement a top-down recursive DP with memoization. For each index i, compute dp(i) by checking all previous indices j < i where nums[j] < nums[i], and take the maximum dp(j) + 1. The final answer is the maximum dp(i) over all indices. This approach runs in O(n^2) time and O(n) space.
Time
O(n^2)
For each index i, the algorithm checks all previous indices j < i, resulting in a nested loop behavior. Memoization ensures each dp(i) is computed once, leading to O(n^2) total computations.
Space
O(n)
The memo dictionary stores one entry per index, and the recursion stack depth is at most n, resulting in O(n) auxiliary space.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When a problem asks for an optimal subsequence or substructure that depends on previous states, define a recursive function representing the solution for a subproblem and cache results to avoid redundant work, transforming exponential recursion into polynomial time.
Solution
| 1 | class Solution:
|
| 2 | def lengthOfLIS(self, nums: list[int]) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i):
|
| 6 | if i in memo:
|
| 7 | return memo[i]
|
| 8 |
|
| 9 | max_len = 1
|
| 10 | for j in range(i):
|
| 11 | if nums[i] > nums[j]:
|
| 12 | max_len = max(max_len, 1 + dp(j))
|
| 13 |
|
| 14 | memo[i] = max_len
|
| 15 | return max_len
|
| 16 |
|
| 17 | if not nums:
|
| 18 | return 0
|
| 19 | return max(dp(i) for i in range(len(nums))) |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | class Solution { |
| 5 | public int lengthOfLIS(int[] nums) { |
| 6 | Map<Integer, Integer> memo = new HashMap<>(); |
| 7 | |
| 8 | if (nums.length == 0) { |
| 9 | return 0; |
| 10 | } |
| 11 | |
| 12 | class Helper { |
| 13 | int dp(int i) { |
| 14 | if (memo.containsKey(i)) { |
| 15 | return memo.get(i); |
| 16 | } |
| 17 | |
| 18 | int maxLen = 1; |
| 19 | for (int j = 0; j < i; j++) { |
| 20 | if (nums[i] > nums[j]) { |
| 21 | maxLen = Math.max(maxLen, 1 + dp(j)); |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | memo.put(i, maxLen); |
| 26 | return maxLen; |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | Helper helper = new Helper(); |
| 31 | int maxLength = 0; |
| 32 | for (int i = 0; i < nums.length; i++) { |
| 33 | maxLength = Math.max(maxLength, helper.dp(i)); |
| 34 | } |
| 35 | return maxLength; |
| 36 | } |
| 37 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <algorithm> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | int lengthOfLIS(vector<int>& nums) { |
| 10 | unordered_map<int, int> memo; |
| 11 | if (nums.empty()) { |
| 12 | return 0; |
| 13 | } |
| 14 | |
| 15 | // Define a recursive lambda with explicit std::function type |
| 16 | struct Helper { |
| 17 | unordered_map<int, int>& memo; |
| 18 | vector<int>& nums; |
| 19 | int dp(int i) { |
| 20 | if (memo.find(i) != memo.end()) { |
| 21 | return memo[i]; |
| 22 | } |
| 23 | |
| 24 | int max_len = 1; |
| 25 | for (int j = 0; j < i; ++j) { |
| 26 | if (nums[i] > nums[j]) { |
| 27 | max_len = max(max_len, 1 + dp(j)); |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | memo[i] = max_len; |
| 32 | return max_len; |
| 33 | } |
| 34 | } helper{memo, nums}; |
| 35 | |
| 36 | int max_length = 0; |
| 37 | for (int i = 0; i < (int)nums.size(); ++i) { |
| 38 | max_length = max(max_length, helper.dp(i)); |
| 39 | } |
| 40 | return max_length; |
| 41 | } |
| 42 | }; |
| 1 | var lengthOfLIS = function(nums) { |
| 2 | const memo = new Map(); |
| 3 | |
| 4 | if (nums.length === 0) { |
| 5 | return 0; |
| 6 | } |
| 7 | |
| 8 | function dp(i) { |
| 9 | if (memo.has(i)) { |
| 10 | return memo.get(i); |
| 11 | } |
| 12 | |
| 13 | let maxLen = 1; |
| 14 | for (let j = 0; j < i; j++) { |
| 15 | if (nums[i] > nums[j]) { |
| 16 | maxLen = Math.max(maxLen, 1 + dp(j)); |
| 17 | } |
| 18 | } |
| 19 | |
| 20 | memo.set(i, maxLen); |
| 21 | return maxLen; |
| 22 | } |
| 23 | |
| 24 | let maxLength = 0; |
| 25 | for (let i = 0; i < nums.length; i++) { |
| 26 | maxLength = Math.max(maxLength, dp(i)); |
| 27 | } |
| 28 | return maxLength; |
| 29 | }; |
Step-by-Step Solution
Handle Empty Input Edge Case
| 17 | if not nums:
|
| 18 | return 0
|
Objective
To immediately return 0 if the input array is empty, as no subsequence exists.
Key Insight
An empty input means there are no elements to form any subsequence, so the longest increasing subsequence length is zero. Handling this edge case upfront prevents unnecessary recursion and potential errors.
Interview Quick-Check
State & Boundaries
Check if nums is empty before any processing to handle trivial input cases correctly.
Compute LIS Lengths Using Memoized Recursion
| 3 | memo = {}
|
| 5 | def dp(i):
|
| 6 | if i in memo:
|
| 7 | return memo[i]
|
| 9 | max_len = 1
|
| 10 | for j in range(i):
|
| 11 | if nums[i] > nums[j]:
|
| 12 | max_len = max(max_len, 1 + dp(j))
|
| 14 | memo[i] = max_len
|
| 15 | return max_len
|
Objective
To recursively compute the length of the longest increasing subsequence ending at each index, caching results to avoid redundant work.
Key Insight
The recursive function dp(i) captures the LIS length ending at index i by exploring all previous indices j < i where nums[j] < nums[i]. By taking the maximum dp(j) + 1, it builds the solution from smaller subproblems. Memoization ensures each dp(i) is computed once, converting exponential recursion into efficient polynomial time.
Interview Quick-Check
Core Logic
The dp(i) function returns the LIS length ending at i by checking all j < i with nums[j] < nums[i], taking the max dp(j) + 1, and memoizing results.
State & Boundaries
Memoization cache prevents recomputation of dp(i) for the same index, ensuring O(n^2) time instead of exponential.
Common Pitfalls & Bugs
Forgetting to memoize results leads to exponential time due to repeated subproblem evaluations.
Aggregate Final Result from All Subproblems
| 19 | return max(dp(i) for i in range(len(nums))) |
Objective
To find the overall longest increasing subsequence length by taking the maximum dp(i) over all indices.
Key Insight
Since the LIS can end at any index, the final answer is the maximum value among all dp(i). The generator expression efficiently computes dp(i) for all i and returns the maximum, leveraging memoization to avoid redundant computations.
Interview Quick-Check
Core Logic
The final LIS length is the maximum dp(i) for i in [0, n-1], as the subsequence can end anywhere.
Complexity
Computing dp(i) for all i with memoization ensures each subproblem is solved once, maintaining O(n^2) time.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if i in memo:Return cached result if dp(i) has been computed before.
This memoization check prevents repeated work and is the key optimization that reduces time complexity from exponential to polynomial.
max_len = max(max_len, 1 + dp(j))Update max_len by considering the LIS ending at j plus nums[i].
This line embodies the core DP recurrence: the LIS ending at i is 1 plus the maximum LIS ending at any smaller previous element, capturing optimal substructure.
return memo[i]Return the cached LIS length for index i.
Returning the cached value immediately avoids unnecessary recursion and ensures correctness by reusing previously computed results.
memo[i] = max_lenCache the computed LIS length for index i.
Storing the result in memo ensures that future calls to dp(i) return instantly, preventing recomputation and enabling efficient top-down DP.
memo = {}Initialize a memoization dictionary to cache LIS lengths for each index.
Memoization is essential to avoid redundant recursive calls, transforming exponential recursion into polynomial time by storing results of subproblems.
if nums[i] > nums[j]:Check if nums[i] can extend the subsequence ending at nums[j].
Only elements smaller than nums[i] can be predecessors in an increasing subsequence, ensuring strict increase.
return max(dp(i) for i in range(len(nums)))Return the maximum LIS length over all indices in nums.
Since the LIS can end at any index, taking the maximum dp(i) over all i yields the overall longest increasing subsequence length.
def dp(i):Define the recursive function dp that computes LIS length ending at index i.
Encapsulating the LIS computation in a recursive function with memoization captures the problem's optimal substructure and overlapping subproblems cleanly.
max_len = 1Initialize max_len to 1, representing the LIS length including only nums[i].
Every element alone forms an increasing subsequence of length 1, serving as the base case for the recursion.
return max_lenReturn the LIS length ending at index i.
Returning the computed value completes the recursive step, allowing the caller to build upon this result.
for j in range(i):Iterate over all indices j before i to find smaller elements.
Checking all previous indices allows building the LIS ending at i by extending smaller subsequences found earlier.
if not nums:Check if the input array is empty.
Handling empty input early prevents errors and unnecessary computation, as no subsequence exists in an empty array.
return 0Return 0 for empty input, indicating no subsequence.
The longest increasing subsequence length for an empty array is zero by definition.
Test Your Understanding
Why does memoization significantly improve the performance of the recursive LIS solution?
Because it caches the results of subproblems (LIS lengths at each index), preventing repeated computations of the same states and reducing the exponential recursion tree to a polynomial number of computations.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Longest Increasing Subsequence from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Increasing Subsequence drill