Longest Increasing Subsequence - Solution & Explanation
Problem Statement
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.
The code initializes a dp array to store the length of the longest subsequence ending at each index. The outer loop considers each element, and the inner loop checks against elements before the current one to update the dp array. Finally, the maximum length found in the dp array is returned as the result.
Complexity
Time Complexity: O(n^2) where n is the length of the input array. Space Complexity: O(n) for storing the dp array.
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'.
This C solution uses a lowerBound function which acts similarly to std::lower_bound in C++. It finds the position to insert (or replace) each element of nums in the 'ends' list, effectively forming the required subsequences.
Complexity
Time Complexity: O(n log n). Space Complexity: O(n).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) where n is the length of the input array. Space Complexity: O(n) for storing the dp array. |
| Optimized DP with Binary Search (Patience Sorting) | Time Complexity: O(n log n). Space Complexity: O(n). |
| Default Approach | — |
Detailed 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. |
Video Solution
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300 • NeetCode • 537,928 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Increasing Subsequence easy or hard?
Longest Increasing Subsequence Python/Java solution
How to solve Longest Increasing Subsequence in O(n log n)?
What is the best approach for Longest Increasing Subsequence?
Is Longest Increasing Subsequence asked at Google/Amazon/Meta?
What data structure is used in Longest Increasing Subsequence?
What is the time complexity of Longest Increasing Subsequence?
Ready to solve this problem?
Practice Longest Increasing Subsequence with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor