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] <= 104Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
The Longest Increasing Subsequence (LIS) problem asks you to find the length of the longest strictly increasing subsequence in an array. A common starting point is the Dynamic Programming approach. For each index, compute the longest increasing subsequence ending at that position by checking all previous elements. If a previous value is smaller, update the length using dp[i] = max(dp[i], dp[j] + 1). This method is intuitive and works well for understanding the subsequence relationship.
For better performance, an optimized method uses Binary Search with a technique similar to patience sorting. Maintain an array that stores the smallest possible tail value for increasing subsequences of different lengths. For each number, use binary search to find its correct position and update the structure. This approach does not store the actual subsequence but efficiently tracks its length, improving performance significantly.
The dynamic programming solution runs in O(n²), while the optimized binary search approach reduces it to O(n log n) with O(n) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming | O(n²) | O(n) |
| Binary Search (Patience Sorting Technique) | O(n log n) | O(n) |
Tushar Roy - Coding Made Simple
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.
Time Complexity: O(n^2) where n is the length of the input array. Space Complexity: O(n) for storing the dp array.
1import java.util.*;
2
3public class LongestIncreasingSubsequence {
4 public int lengthOfLIS(int[] nums) {
5The Java solution follows the same logic as C and C++ solutions, using a dp array initialized to 1. It iterates over pairs of elements, updating the array to store the longest subsequence lengths found.
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'.
Time Complexity: O(n log n). Space Complexity: O(n).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Binary search helps quickly find the correct position to replace or extend a subsequence tail value in the tracking array. This keeps the array sorted and ensures the algorithm runs in O(n log n) time instead of O(n²).
Yes, the Longest Increasing Subsequence problem is a classic dynamic programming and binary search interview question. Variations of LIS frequently appear in coding interviews at companies like Google, Amazon, Meta, and Microsoft.
The optimal approach uses a greedy strategy combined with binary search, often called the patience sorting technique. It maintains a list of minimum tail values for increasing subsequences and updates positions using binary search, achieving O(n log n) time complexity.
Arrays or lists are typically used to store dynamic programming states or the tail values in the optimized method. Binary search is applied on this structure to maintain sorted order efficiently while processing the sequence.
Python solution makes use of the bisect module to apply binary search on the list 'ends'. This approach ensures finding the right position for each element in logarithmic time.