Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [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.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Solution –
Let us just think about this question and make sure that we understand this. Longest increasing subsequence is the maximum count of numbers which are in increasing order in an array. We can skip some numbers in between but we can not change the order of the numbers.
For example- for a smaller array like [1, 2, 3, 4] longest common subsequence is 4 and for [1, 2, 4, 3] it is 3.
So for every case of input[i], the result is input[j] +1 if i > j and input[i] > input [j] otherwise 1 if input[i] <= input [j]
It is a case of overlapping subproblems. as for every i we have to calculate for i-1 and for every i-1 we have to calculate for i-2.
We can start thinking about the code.
- By default we know that for each one digit, longest common subsequence is 1. So initially we can create and array with same length as input and put 1 on each index.
- we can have two nested loops, one of i from 1 to n-1 and j from 0 to i-1.
- input is nums in our case. If nums[i] > nums[j] and helper[j]+1 > helper[i] then set helper[i] = helper[j]
- otherwise we don’t need to update helper[i] as it already has subsequence from lower indexes.
- In the end, return max value from the helper array.
Code is implemented in JavaScript but it will be same in other languages.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function(nums) { if(nums.length === 0) { return 0; } let helper = nums.map(()=>{return 1}); for(let i=1; i<nums.length; i++){ for(let j=0; j<nums.length && j<i ; j++) { if(nums[i] > nums[j] && helper[j]+1 > helper[i]) { helper[i] = helper[j]+1; } } } console.log(helper); return Math.max(...helper); }; |
Follow up question
Could you improve it to O(n log n) time complexity?
Yes, we can improve the complexity by using more space. At any point of time we maintain list of values in strict increasing order.
- If new number is greater then end element of list, we append it to list
- If new element is smaller then last element but larger than smallest element, we start a new list withe new element
- Else there is a new list with length 0.
- If there are two lists with same lengths then we should discard the one with larger last element