DP 41. Longest Increasing Subsequence | Memoization

Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3rVoIoq
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the LIS problem with DP. In the next video we have learnt about the next method using tabulation.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward

[@sahilgagan2242]

73% done …. this is the first time , that i pick a series and consistently practice and learn from it.... u make us doubtless striver.... ur way of explanation is 100x better than any paid courses.... thank god we have striver ....

[@parthsalat]

Thank striver, we have God

[@ShivangShandilyaa]

@@parthsalat what???

[@atanunayak6637]

@@parthsalat Bhai tunne alag level ka recursion seekh liya hai😂

[@piyushacharya7696]

@@atanunayak6637 😂😂😂😂

[@ashadahmad6493]

@@atanunayak6637 😂😂😂

[@vikasgupta6701]

Able to solve without watching the video. the concepts and basics that you taught so far is now helping me to tackle the problems on my own. Thanks striver!!

[@Nikkhil492]

The moment you said prev concept trust me striver bhaiya, i somehow was able to understand how to solve this. Thank you man you are a great teacher.

[@factfactorial632]

Thanks, striver bhaiya !!! Even the DP array of size n*n would work because the f(n,n-1) will never get stored in dp array because the moment index==n the base case would hit

[@ashutoshgupta1905]

Thanks, striver for the amazing clarity in explanation. Even though the concept and solution is correct, but it would be helpful to stick to bottom up (memoization) and top down (recursion) approach you had from the very beginning.

[@stith_pragya]

UNDERSTOOD.........Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@sauravchandra10]

clearly understood and was able to code it on my own, thanks a lot bhaiya ❤‍🔥!

[@vinayakgandhi5690]

instead of taking -1 as prev when there is no previous index, take prev same as index and check with condition (prev == index), this will not give memory exceed error as you will not need the n+1 2d array, just n will be enough.

[@takeUforward]

Smaller modifications I will leave it on you 😛

[@vinayakgandhi5690]

@@takeUforward Absolutely Sir, thanks for everything 🙂

[@pixelsbyme]

@Vinayak Gandhi can u please share the code of your approach, I am not able to implement it. Thank You!

[@vinayakgandhi5690]

class Solution { public int lengthOfLIS(int[] nums) { int[][] dp = new int[nums.length][nums.length]; for (int i = 0; i < nums.length; i++) { Arrays.fill(dp[i], -1); } int[] max = new int[] { 0 }; sol(0, 0, nums, dp, max); return max[0]; } private int sol(int ind, int prev, int[] nums, int[][] dp, int[] max) { if (ind == nums.length) { return 0; } if (dp[ind][prev] != -1) { return dp[ind][prev]; } int w = -1; int wo = -1; if (ind == prev) { w = 1 + sol(ind + 1, ind, nums, dp, max); wo = sol(ind + 1, ind + 1, nums, dp, max); } else { if (nums[ind] > nums[prev]) { w = 1 + sol(ind + 1, ind, nums, dp, max); } wo = sol(ind + 1, prev, nums, dp, max); } dp[ind][prev] = Math.max(w, wo); max[0] = Math.max(max[0], dp[ind][prev]); return dp[ind][prev]; } }

[@vishalbalaji1842]

Actually, we cannot do this in some cases(ex: gfg lis question), because they mention it has to be strictly increasing

[@MCEParitoshShukla]

Bahut Badhiya sir ji sab samajh aa rha h . Bahut sara pyar is series ke liye

[@user-ld3bx2cs4j]

We can perform a simple lcs on the given vector and its sorted vector(containing unique elements) and solve this😁 create a new vector push the values in the set and then push the values of set in the new vector (set automatically arranges in increasing order) and then run the lcs code(longest common subsequence)

[@vaibhavagarwal1479]

that seems like a valid approach Great

[@JayashreeThota]

Thanks Striver for the clear explanation of the approach. Can you please help me understand why is the time complexity n*n? We are traversing through the elements only once considering along with the memoization.

[@kashyapkumar6255]

understood and also thanks for runtime error till know i not sure about "runtime error" ,today i get one ans from you that is occur due to memory execced

[@madhuryar.p5070]

Love this guy's effort 🤩

[@cinime]

Understood! Thank you so so so much as always!!!

[@ADITYARAJ-yv2tr]

bhaiya you won't believe its been 20 days since i started graph and dp. each day i try to solve alteast 1 question of each topic. i have solved 20 question from each and i haven't reached this question yet but for some placement drive i was just looking for the intuition but as i had already solved the DP on subsequences i was able to build intuition on my within 5 min. in fortunately it is same as yours. thanks a lot for making this A2Z sheet..

[@prabhakaran5542]

Understood ❤ and thanks for explaining runtime error ❤

[@Mahi-kr9es]

we can do this sum in other way sort the given elements and apply lcs with given array and sorted array

[@your_name96]

good way, but it increases the time complexity for this though so maybe useful for tougher variations

[@Mahi-kr9es]

@@your_name96 ig it will not increase the tc

[@googlewasmyidea9895]

bruh, in subsequence we have to maintain order of indexes. if youll sort it then how could it be a subsequence

[@ritikshandilya7075]

Thankyou for great solution Striver

[@MohanaKrishnaVH]

Awesome Explanation. Understood!

[@DevashishJose]

understood thank you so much.

[@wisdomkhan]

You made it look so easy

[@anuragpandey8165]

its giving tle for map dp ( map mp )

[@tusharyadav5874]

bro map is not right data structure . You should use the unorderd_mpap as the map have insertion,deletion,searching of o(logn) , whereas the unorderd_map have time complexity of o(1) for the operations.

[@jaisamtani303]

The good thing is I was able to crack logic for LIS before this video. Did not know that binary search logic is the optimized approach for LIS! Thanks my intuition for DP problems has become much better than before!

[@user-ke7fs7ds6h]

striver strives us forward😍😍

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@anmoljohri9930]

Striver bhaiya you are just our GOD, did till space optimization without watching this video. Cant thank you enough for this brilliant series. Here's the code: class Solution { public: int lengthOfLIS(vector& nums) { int n = nums.size(); // vector dp(n+1,vector(n+1,0)); vector ahead(n+1,0),cur(n+1,0); for(int ind = n-1;ind>=0;ind--){ for(int prev = ind-1;prev>=-1;prev--){ // int nottake = dp[ind+1][prev+1]; int nottake = ahead[prev+1]; int take =0; if(prev==-1 || nums[ind]>nums[prev]){ // take = 1+dp[ind+1][ind+1]; take = 1+ahead[ind+1]; } // dp[ind][prev+1]=max(nottake,take); cur[prev+1]=max(nottake,take); } ahead=cur; } return ahead[0]; } };

[@pranavchandrode7127]

in take case "take = 1+dp[ind+1][ind+1];" why did you write [ind+1][ind+1] in both, acording to the recursive solution isn't it should be dp[ind+1][ind] ?

[@anmoljohri9930]

@@pranavchandrode7127 yes according to recursion it should be that only , but if you carefully observe you'll notice that indexing changes for tabulation and space optimization, striver has even tried to teach us why that change in indexing happens , i don't remember it as of now , did DP 5 months ago , have to revise again

[@pranavchandrode7127]

@@anmoljohri9930 Thank you! I think this is because of coordinate shifting , we have shift the coordinate of prev_ind by 1 everytime, so instead of writting dp[i][prev_ind] we have to write dp[i][prev_ind +1]

[@anmoljohri9930]

@@pranavchandrode7127 yes this was it as far as I remember

[@Sumeet_100]

Hey bro !! could you plz tell why you have taken ( take = 1+dp[ind+1][ind+1]; ) bcz it must be like (// take = 1+dp[ind+1][ind];) could you plz tell the reason??

[@paridhijain7062]

Again, Understood! Loving this series.

[@sameersahu4569]

Understood!!Thank you

[@icongrindsetsfj]

Thank You Legend for showing us all the possible approaches.

[@Virtualexist]

I could nt do with a slight variation... What if we are alllowed to swap two of the numbers in the subsequence and then find the longest increasing subseuence? Please suggest.

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@googleit2490]

Understood :) Was pretty confused why I am getting runtime error, when I was solving it before completing the chapter. Aug'1, 2023 10:38 pm

[@ganeshkamath89]

Thanks Striver. Understood.

[@gadgetsandhacks7161]

why we always take the first elemnt there might be a case where without it we get a longer inc subsequence ?

[@pranavchandrode7127]

in gfg at test case 111/116 i am getting an error "Abort signal from abort(3) (SIGABRT)" in both memoization and tabulation. can anyone help me with this here's the code int recursion(int i,int prev_ind,int arr[],int n,vector& dp) { if(i == n) { return 0; } if(dp[i][prev_ind+1] != -1) return dp[i][prev_ind+1]; int pick = 0; if(prev_ind == -1 || arr[i] > arr[prev_ind]) { pick = 1 + recursion(i+1,i,arr,n,dp); } int not_pick = 0 + recursion(i+1,prev_ind,arr,n,dp); return dp[i][prev_ind+1] = max(pick,not_pick); } Tabulation code :- vectordp(n+1,vector(n+1,0)); // since in base case we have to assign 0 therefore we can omit it // and can be taken care during the for loops for(int i = n-1;i>=0;i--) { for(int prev_ind = n-1;prev_ind>=-1;prev_ind--) { int pick = 0; if(prev_ind == -1 || a[i] > a[prev_ind]) { pick = 1 + dp[i+1][i+1]; } int not_pick = 0 + dp[i+1][prev_ind+1]; dp[i][prev_ind+1] = max(pick,not_pick); } } return dp[0][0]; }

[@impatientgaming9868]

Good one

[@arihantjammar8888]

Understood 😊

[@rohandevaki4349]

at 4:23 , can you share on which videos you have taught it ?

[@UECAshutoshKumar]

Understood!!!

[@krishnaa5559]

Understood!

[@ayushman_sr]

Apart from DP be aware of there exist more optimised solution. nLogN def lengthOfLIS(self, nums: List[int]) -> int: lis = [] for num in nums: pos = bisect.bisect_left(lis,num) if pos == len(lis): lis.append(num) else: lis[pos] = num return len(lis)

[@prit8360]

People who want top-down approach int fun(int ind,int last,vector &arr){ if(ind==0) return 0; int len=fun(ind-1,last,arr); if(last==-1 || arr[ind]

[@Invincible2203]

that would be ind < 0.

[@parambharti7095]

Great content. Thanks a lot striver.

[@thopbgm38]

what if values of array are from -10^4 to 10^4 then coordinate shift by 1 wont work how to do that

[@joya9785]

Guys can someone explain why the time complexity for the memoized soln is O(n^2)?

[@yashanand3068]

bhaiya why the base cant be if(ind == n - 1) return 1 but in the coin change problem you take base case at n - 1. I am confused when base will be n - 1 or when it will be n

[@GungunRamchandani]

UNDERSTOOD

[@IshmaamIftekhar]

Why (prev-ind) tho instead of prev only? Cause the previous element should be prev if we don't take right??

[@dhanesh.s]

Can we take prev as element (INT_MIN) instead of index And compare like If( nums[I] > prev) Take = 1 + f(I+1,nums[I]); No take = 0 + f(I+1,prev); Max(take,not); In recursion?

[@dhanesh.s]

Initially take as 0

[@jaisamtani303]

@Dhanesh, see below is the issue u will face according to me if u use prev_value instead of prev_idx @Striver was using f(int idx, int prev_idx) for recursion, when he converted it to memoization array he used dp[idx][prev_idx]. We know that both idx and prev_idx can be till n. So dp array will be of size n*n Your case: Your function becomes f(int idx, int prev_value) for Recursion, when u convert it to memoization array, dp[idx][prev_val]. Now idx can go till n, we cannot guarantee what will be limit for prev_value. If array consists of negative elements then array cannot take negative index, lets say array has 5 very huge elements, then your array will be of 5* huge value instead of 5*5. So using prev_idx is better as we know it will be max array size!

[@nik_hil_11]

space complexity is not O(N) it would be O(N2) right as you are checking current index and previous index. It would give memory limit exceeded error in leetcode. this solution would give O(n) space class Solution: def lengthOfLIS(self, nums: List[int]) -> int: # solutions memo = {} def dfs(idx): if idx in memo: return memo[idx] max_val = 1 for i in range(idx + 1, len(nums)): if nums[i] > nums[idx]: max_val = max(max_val, dfs(i) + 1) memo[idx] = max_val return max_val res = 0 for i in range(len(nums)): res = max(res, dfs(i)) return res

[@sejalrai30]

thank you

[@Aman-lm9jv]

what is wrong in this code someone explain please : int f(int n , vector& nums){ if(n == 0){ if(nums[n] < nums[n+1]) return 1; else return 0; } int notTake = f(n-1 , nums); int take = -1; if(n-1 >= 0){ if(nums[n] > nums[n-1]) 1 + f(n-1 , nums); } return max(take , notTake); }

[@ParthKanani555]

Hey striver In interview how we decide that the problem is memoized Or not? By drawing recursion tree...

[@ujjalsaha428]

As always "understood"❤️

[@dhruvilhirpara1795]

DP size would be dp[n+1][n+1]; (Just pointing out a small error, Otherwise your content is TOP TIER! BEST CONTENT AVAILABLE OUT THERE)

[@TakeMydick-ii4mb]

Why?

[@shashankvashishtha4454]

understood

[@ammanchhetri6716]

didn't even have to watch the video...was able to solve it :)

[@VenkatGopalakrishnan]

No need to create 2D matrix. just 1D def lis(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp

[@ayushupadhyaya7656]

Hey Striver A solution of TC(nlogn) and SC O(n) is available at leetcode explore section. Would be great if you can cover that approach as well.

[@adityasrivastava3540]

Can someone explain why this wont work? int lmax(vector &nums,int n,int index,int prev){ if(index==n) return 0; int take; if(prev==-1 || nums[index]>nums[prev]){ take=1+lmax(nums,n,index+1,index); } int nottake=0+lmax(nums,n,index+1,prev); return max(take,nottake); } What is the difference?

[@devanshibavaria699]

u need to initialize take with 0. if( the conditions prev==-1 || nums[index]>nums[prev] are not satisfied it will take a garbage value.

[@mdadil1810]

bhaiya please do longest arithmetic subsequence of given difference

[@amansamal8233]

understood ❤❤❤

[@pragyanandsingh6673]

Understood !!

[@nikitakeshri9233]

Understood:)

[@arsh2935]

Bhaiya what to do in case if nums[I] values range from 10^-4 to 10^4 . if I am declaring dp of n x 10^8 , It is showing memory limit exceeded on leetcode

[@takeUforward]

For that bs approach in next video

[@user-lt2ie8ys3n]

Understood

[@user-gq3xu4vj8d]

great content bhai respect for you

[@user-up6sl2gq8p]

understoood

[@varunaggarwal7126]

vector longestIncreasingSubsequence(std::vector& nums) { std::vector dp; // Longest increasing subsequence for (int i = 0; i < nums.size(); i++) { int x = nums[i]; if (dp.empty() || x > dp.back()) { dp.push_back(x); } else { // Perform a binary search to find the correct position to insert x in dp int left = 0; int right = dp.size() - 1; int index = -1; while (left

[@dhanashreegodase4445]

thanks

[@devangsingh2950]

Can someone tabulate the approach used in this video I am facing issues?

[@ayushs_2k4]

Can we tabulise it, I am not able to tabulise it

[@siddharthagarwal3927]

bhaiya is lecture ke notes site pe available nahi hai

[@blackhatsamurai9386]

One more approach that can be used is monotonic stack private static int findLongestIncreasingSequence(int[] arr) { Stack st = new Stack(); for(int i = 0; i < arr.length; i++) { while(!st.isEmpty() && st.peek() < arr[i]){ st.pop(); } st.push(arr[i]); } return st.size(); } Let me know your thoughts/corrections

[@dajucoder]

it is throwing compilation errors, please run your code before posting it somewhere, it wastes our time to understand your approach and figure out what the hell you wanted this code to do

[@mathanmaddy17]

In this code the tabulation and space optimization solution is not mentioned...

[@mritunjay3723]

why not take used before ?

[@kartikrameshchavan6662]

Understood 🙏

[@sakshimishra1491]

How can I optimize memory in this: Leetcode problem 334: public boolean increasingTriplet(int[] nums) { Boolean[][][] dp= new Boolean[nums.length+1][nums.length+1][4]; return sub(0,-1,nums,nums.length,dp,3); } public boolean sub(int ind, int prev, int[] nums, int n, Boolean[][][]dp, int count) { if(count==0) return true; if(ind==n) return false; if(dp[ind][prev+1][count]!=null) return dp[ind][prev+1][count]; boolean len1=sub(ind+1, prev,nums,n,dp, count);// nottake case boolean len2=false; if(prev==-1 || nums[ind] > nums[prev]) { // System.out.println(nums[ind]); // System.out.println(count); len2 = sub(ind+1,ind,nums,n,dp,count-1);// take case } return dp[ind][prev+1][count] = len1||len2; }

[@satyampande684]

understood!!

[@shubhigupta5689]

Understood🌻

[@_hulk748]

understood sir🙏🙏

[@Superheroic_Anime]

Understood 😁

[@ajitzote6103]

understood!

[@Hello-ro6hr]

UNDERSTOOD ...

[@DhruvToshniwal]

Is a 2D dp array necessary? Can't we do it in 1D? Start from the back and and for any i, dp[i] = LIS from inex 0...i ??

[@thallapakuteja2350]

nope beacuse we need the previous index also along with curent index beacuse result changes based on previous element also

[@rahul_rangi]

you can do that , using binary search concept int ceilIdx(int tail[], int l, int r, int key) { while (r > l) { int m = l + (r - l) / 2; if (tail[m] >= key) r = m; else l = m+1; } return r; } int longestIncreasingSubsequence(int nums[], int n) { int tail[n]; int len =1; tail[0] = nums[0]; for (int i = 1; i < n; i++) { if(nums[i] > tail[len - 1]) { tail[len] = nums[i]; len++; } else { int c = ceilIdx(tail, 0, len - 1, nums[i]); tail[c] =nums[i]; } } return len; }

[@VenkatGopalakrishnan]

def lis(array): def dfs(curr, prev): if curr == n: return 0 if (curr, prev) not in memoize: length = dfs(curr+1, prev) if prev == None or array[curr] > array[prev]: length = max(length, 1+dfs(curr+1, curr)) memoize[(curr, prev)] = length return memoize[(curr, prev)] n = len(array) memoize = {} return dfs(0, None)

[@pulkitranjan8189]

was able to do it by myself

[@original_gangsta_]

Understood💯💯💯💪💪💪

[@rakeshkumarreddypothireddy8159]

Striver bhai, why you haven't started picking elements from the end of the array?

[@tharunreddy2255]

bro did u got the tabulation solution if we start picking elements from the end

[@vaibhavgupta973]

how the time complexity of memoized solution is (n*n) ???

[@LBK3]

Understood ❤

[@parshchoradia9909]

Understood Sir!

[@ayushsrivastava458]

I used the following approach( but it is giving wrong answer for some test cases) for finding LIS : First I sorted the given array and then i found the Longest common subsequence between the original array and the sorted array. What is wrong with this approach, it is giving wrong answer for some test cases ?

[@chiragmehta2955]

Bcz it will change order in input Ex. 2 3 1 Lcs=2 If we sort input 1 2 3 Lcs = 3 ehich is wrong

[@10daysAgo]

​@@chiragmehta2955no your explanation is wrong . The LCS after sorting for your example will still be 2 not 3 .

[@the_haryannvi_coder]

Other way if you don't want to shift:- #include int f(int i, int prev, int n, int arr[], vector &dp){ // base case if(i==n) return 0; if(prev!=-1 && dp[i][prev] != -1) return dp[i][prev]; int pick = INT_MIN; if(prev==-1 || arr[i]>arr[prev]){ pick = 1 + f(i+1, i, n, arr, dp); } int notpick = f(i+1, prev, n, arr, dp); if(prev==-1) return max(pick, notpick); else return dp[i][prev] = max(pick, notpick); } int longestIncreasingSubsequence(int arr[], int n){ vector dp(n, vector(n, -1)); return f(0, -1, n, arr, dp); }

[@pixelsbyme]

Memoization Solution without taking n+1 .... ie only making dp[n][n]. // Leetcode : Accepted class Solution { public: int f(int ind, int prev_index, vector &dp, vector &arr, int &n) { if (ind == n) return 0; if (dp[ind][prev_index] != -1) return dp[ind][prev_index]; int len = f(ind + 1, prev_index, dp, arr, n); // not take if (prev_index == n-1 || arr[ind] > arr[prev_index]) len = max(len, 1 + f(ind + 1, ind, dp, arr, n)); // take condition return dp[ind][prev_index] = len; } int lengthOfLIS(vector& arr) { int n = arr.size(); vector dp(n, vector(n , -1)); return f(0, n-1, dp, arr, n); } };

[@rahulsaha332]

your previous is the last index and in the recursion you are increasing the indexes, the logic must be reversed and yeah it is still giving a runtime error :)

[@pixelsbyme]

@@rahulsaha332 It is not giving me error in leetcode. Copy paste the code in leetcode and please check again

[@parthverma7089]

@@rahulsaha332 actually it is giving TLE errror coz of memoization

[@abhishuraina4302]

Bhai apki videos next level hai

[@MaheshKumar-jt3qv]

why we are not using concept that we did earlier, that is starting from back? i am getting lot of confusions

[@piyushacharya7696]

look at this base case then you will understand! 1 2 2 if you start from 0th index then the ans is 2 and if you start from the last index the ans is 1.

[@riyakumari8377]

@@piyushacharya7696 not true thats why we are using pick and not pick we wont pick 2 at last index rather 2 of second last index and then 1 so ans will be 2. You start from start or last doesnt matter anyways.

[@ITArchanaGK]

understood✨

[@priyanshvatsal9791]

Understood 😇

[@youtubekumar8590]

Thanku bhaiya