Longest Increasing Subsequence
MedPrompt
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: 4Example 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?
Approaches
4 approaches with complexity analysis and trade-offs.
The brute force approach involves generating all possible subsequences and finding the longest one that is strictly increasing. We can use recursion to explore all possibilities.
Algorithm
- Define a recursive function
findLIS(nums, index, prev)that returns the length of the LIS starting fromindexwith the previous element beingprev - Base case: If
indexreaches the end of the array, return 0 - For each position, consider two options:
- Skip the current element and move to the next index
- Include the current element if it's greater than the previous element
- Return the maximum of these two options
Walkthrough
In this approach, we consider each element and make two choices: either include it in the subsequence or exclude it. However, we can only include an element if it's greater than the last element we included.
For each position, we recursively try both including the current element (if valid) and excluding it, then return the maximum length found.
public int lengthOfLIS(int[] nums) { // Start the recursion from index 0 with no previous element return findLIS(nums, 0, Integer.MIN_VALUE);} private int findLIS(int[] nums, int index, int prev) { // Base case: reached the end of the array if (index == nums.length) { return 0; } // Option 1: Skip the current element int skip = findLIS(nums, index + 1, prev); // Option 2: Include the current element if it's greater than the previous element int include = 0; if (nums[index] > prev) { include = 1 + findLIS(nums, index + 1, nums[index]); } // Return the maximum of the two options return Math.max(skip, include);}This solution will work correctly but is extremely inefficient for larger inputs due to the exponential number of recursive calls.
Complexity
Time
O(2^n) - For each element, we have two choices (include or exclude), leading to an exponential number of recursive calls
Space
O(n) - The recursion stack can go as deep as the length of the array
Trade-offs
Pros
Simple to understand and implement
Correctly finds the longest increasing subsequence
Cons
Extremely inefficient for larger inputs
Many overlapping subproblems are recomputed
Will exceed time limit for the given constraints
We can optimize the recursive approach by using memoization to avoid recomputing the same subproblems multiple times. This is a top-down dynamic programming approach.
Algorithm
- Define a recursive function
findLIS(nums, index, prevIndex, memo)that returns the length of the LIS starting fromindexwith the previous element atprevIndex - Use a memoization array
memo[index][prevIndex+1]to store computed results - Base case: If
indexreaches the end of the array, return 0 - If the result for the current state is already in memo, return it
- For each position, consider two options:
- Skip the current element and move to the next index
- Include the current element if it's greater than the previous element
- Store the maximum of these two options in memo and return it
Walkthrough
The recursive approach has many overlapping subproblems. We can use memoization to store the results of these subproblems and reuse them when needed.
We'll use a 2D array memo where memo[index][prevIndex] represents the length of the LIS starting from index with the previous element at prevIndex. Since we need to track the actual previous element's index (not just its value), we'll modify our approach slightly.
public int lengthOfLIS(int[] nums) { // Initialize memoization array with -1 (indicating not computed yet) Integer[][] memo = new Integer[nums.length][nums.length + 1]; return findLIS(nums, 0, -1, memo);} private int findLIS(int[] nums, int index, int prevIndex, Integer[][] memo) { // Base case: reached the end of the array if (index == nums.length) { return 0; } // If result is already computed, return it if (memo[index][prevIndex + 1] != null) { return memo[index][prevIndex + 1]; } // Option 1: Skip the current element int skip = findLIS(nums, index + 1, prevIndex, memo); // Option 2: Include the current element if it's greater than the previous element int include = 0; if (prevIndex == -1 || nums[index] > nums[prevIndex]) { include = 1 + findLIS(nums, index + 1, index, memo); } // Store the result in memo and return memo[index][prevIndex + 1] = Math.max(skip, include); return memo[index][prevIndex + 1];}By using memoization, we significantly reduce the time complexity from exponential to polynomial.
Complexity
Time
O(n²) - We have n positions and for each position, we might consider up to n previous indices
Space
O(n²) - For the memoization array and recursion stack
Trade-offs
Pros
Significantly faster than the brute force approach
Avoids recomputing overlapping subproblems
Still maintains the recursive structure which is easy to understand
Cons
Still not the most efficient solution possible
Uses more space than necessary
The recursion can lead to stack overflow for very large inputs
We can use a bottom-up dynamic programming approach to solve this problem more efficiently. This eliminates the recursion overhead and is generally more space-efficient.
Algorithm
- Create a dp array of size n, where dp[i] represents the length of the LIS ending at index i
- Initialize all values in dp to 1 (minimum LIS length is 1)
- For each position i from 1 to n-1:
- For each previous position j from 0 to i-1:
- If nums[i] > nums[j], update dp[i] = max(dp[i], dp[j] + 1)
- Update the maximum LIS length found so far
- For each previous position j from 0 to i-1:
- Return the maximum length
Walkthrough
In this approach, we define dp[i] as the length of the longest increasing subsequence ending at index i. For each position i, we look at all previous positions j (where j < i). If nums[i] > nums[j], we can extend the subsequence ending at j by including the element at i.
public int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; // Initialize dp array with 1 (minimum LIS length is 1) Arrays.fill(dp, 1); int maxLength = 1; // Fill dp array 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); } } maxLength = Math.max(maxLength, dp[i]); } return maxLength;}This approach is more efficient than the recursive approach with memoization because it eliminates the overhead of recursion and directly computes the results in a bottom-up manner.
Complexity
Time
O(n²) - We have two nested loops, each iterating through the array
Space
O(n) - We only need an array of size n to store the dp values
Trade-offs
Pros
More efficient than the recursive approach
No recursion overhead
Straightforward implementation
Guaranteed to work within the given constraints
Cons
Still not the optimal solution in terms of time complexity
For large arrays, O(n²) might still be too slow
We can achieve O(n log n) time complexity using a technique similar to patience sort, which uses binary search to efficiently build the longest increasing subsequence.
Algorithm
- Create an array
tailswheretails[i]represents the smallest ending value of all increasing subsequences of length i+1 - Initialize
size = 0to track the current number of piles - For each number in the input array:
- Use binary search to find the correct position for the current number in the tails array
- Place the current number in that position
- If we created a new pile (i.e., the position is at the end), increment the size
- Return the final size, which is the length of the LIS
Walkthrough
This approach maintains a list of piles, where each pile represents the smallest ending value of an increasing subsequence of a certain length. We process each element in the array and use binary search to find the correct pile to place it.
The key insight is that we don't need to keep track of the entire subsequence, just the smallest ending value for subsequences of each length.
public int lengthOfLIS(int[] nums) { int n = nums.length; if (n == 0) return 0; // tails[i] = smallest ending value of all increasing subsequences of length i+1 int[] tails = new int[n]; int size = 0; // current number of piles for (int num : nums) { // Binary search to find the correct position for the current number int left = 0, right = size; while (left < right) { int mid = left + (right - left) / 2; if (tails[mid] < num) { left = mid + 1; } else { right = mid; } } // Place the current number in the correct position tails[left] = num; // If we created a new pile, increment the size if (left == size) { size++; } } return size;}This approach is based on the patience sort algorithm. The length of the final tails array (or the number of piles) is the length of the longest increasing subsequence.
Note that the tails array doesn't necessarily represent the actual LIS, but its length is the same as the length of the LIS.
Complexity
Time
O(n log n) - We process each of the n elements and perform a binary search (log n) for each one
Space
O(n) - We need an array of size n to store the tails
Trade-offs
Pros
Optimal time complexity of O(n log n)
Works efficiently for large inputs
Uses less space than the memoization approach
Meets the follow-up challenge requirement
Cons
More complex to understand than the DP approaches
The tails array doesn't directly represent the actual LIS (just its length)
Requires understanding of patience sort and binary search concepts
Solutions
Solution
class Solution { public int lengthOfLIS ( int [] nums ) { int [] s = nums . clone (); Arrays . sort ( s ); int m = 0 ; int n = s . length ; for ( int i = 0 ; i < n ; ++ i ) { if ( i == 0 || s [ i ] != s [ i - 1 ]) { s [ m ++] = s [ i ]; } } BinaryIndexedTree tree = new BinaryIndexedTree ( m ); for ( int x : nums ) { x = search ( s , x , m ); int t = tree . query ( x - 1 ) + 1 ; tree . update ( x , t ); } return tree . query ( m ); } private int search ( int [] nums , int x , int r ) { int l = 0 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( nums [ mid ] >= x ) { r = mid ; } else { l = mid + 1 ; } } return l + 1 ; } } class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] = Math . max ( c [ x ], v ); x += x & - x ; } } public int query ( int x ) { int mx = 0 ; while ( x > 0 ) { mx = Math . max ( mx , c [ x ]); x -= x & - x ; } return mx ; } }class BinaryIndexedTree { public: BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int v ) { while ( x <= n ) { c [ x ] = max ( c [ x ], v ); x += x & - x ; } } int query ( int x ) { int mx = 0 ; while ( x ) { mx = max ( mx , c [ x ]); x -= x & - x ; } return mx ; } private: int n ; vector < int > c ; }; class Solution { public: int lengthOfLIS ( vector < int >& nums ) { vector < int > s = nums ; sort ( s . begin (), s . end ()); s . erase ( unique ( s . begin (), s . end ()), s . end ()); BinaryIndexedTree tree ( s . size ()); for ( int x : nums ) { x = lower_bound ( s . begin (), s . end (), x ) - s . begin () + 1 ; int t = tree . query ( x - 1 ) + 1 ; tree . update ( x , t ); } return tree . query ( s . size ()); } };# find the largest end element in tails that is smaller than nums[i] # and then replace it with nums[i] and discard the list in the same length # which is implemented by `tail[idx] = num` class Solution ( object ): def lengthOfLIS ( self , nums ): """ :type nums: List[int] :rtype: int """ tail = [] for num in nums : # if using bisect_right(tail, num), # then input=[7,7,7,7,7,7,7] will output 7 but expected result is 1 idx = bisect . bisect_left ( tail , num ) if idx == len ( tail ): # same as in java: if (i == len) len++; tail . append ( num ) else : tail [ idx ] = num return len ( tail ) # implementation of bisect.bisect_left() # similar to Leetcode-302, find left/right/top/bottom callable def bisect_left ( a , x , lo = 0 , hi = None ): if hi is None : hi = len ( a ) while lo < hi : mid = ( lo + hi ) // 2 if a [ mid ] < x : lo = mid + 1 else : hi = mid return lo ############ class BinaryIndexedTree : def __init__ ( self , n : int ): self . n = n self . c = [ 0 ] * ( n + 1 ) def update ( self , x : int , v : int ): while x <= self . n : self . c [ x ] = max ( self . c [ x ], v ) x += x & - x def query ( self , x : int ) -> int : mx = 0 while x : mx = max ( mx , self . c [ x ]) x -= x & - x return mx class Solution : def lengthOfLIS ( self , nums : List [ int ]) -> int : s = sorted ( set ( nums )) m = len ( s ) tree = BinaryIndexedTree ( m ) for x in nums : x = bisect_left ( s , x ) + 1 t = tree . query ( x - 1 ) + 1 tree . update ( x , t ) return tree . query ( m )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.