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.
1#include <stdio.h>
2#include <string.h>
3
4int lengthOfLIS(int* nums, int numsSize) {
5 if (
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.
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).
1
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.
Java's Collections.binarySearch is used to find the position to insert each element in the ends list. The position determines whether to extend or replace an element in the list.