Longest Increasing Subsequence - Video Solutions
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300
Longest Increasing Subsequence - Video Solution
Watch 10 video solutions for Longest Increasing Subsequence, a medium level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by NeetCode has 537,928 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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. |