Longest Increasing Subsequence Ii - Leetcode Solution

Problem statement:

Given an unsorted array of integers, find the length of longest 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

Approach:

One approach could be to use dynamic programming to solve the problem. We can keep an array of size n where n is the length of the input array. The idea is to use this array to store the length of the longest increasing subsequence so far ending at a particular index of the input array. For each index i of the input array, we loop through all the indices j from 0 to i-1 and if nums[i]>nums[j], we update the value of dp[i] as max(dp[i],dp[j]+1).

At the end, we return the maximum value in the dp array which will give us the length of the longest increasing subsequence.

We can further optimize this solution by using binary search. Instead of looping through all the indices j from 0 to i-1, we can use binary search to find the index j such that dp[j] is just less than dp[i]. Since dp array is always sorted in increasing order, we can use binary search to find the index j in logn time.

Solution:

The code for the solution using dynamic programming and binary search is given below:

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); int dp[n]; int length=0; for(int i=0;i<n;i++){ int low=0,high=length-1; while(low<=high){ int mid=(low+high)/2; if(dp[mid]<nums[i]){ low=mid+1; } else{ high=mid-1; } } dp[low]=nums[i]; if(low==length){ length++; } } return length; } };

Time Complexity:

The time complexity of this solution is O(nlogn) since we are using binary search to find the index j in logn time for each index i of the input array.

Space Complexity:

The space complexity of this solution is O(n) since we are keeping an array of size n to store the length of the longest increasing subsequence so far ending at a particular index of the input array.

1