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
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 ; } }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.