Number of Longest Increasing Subsequence | Using LIS | Full Dry Run | META | Leetcode-673

[@codestorywithMIK]

I will soon upload LIS and LIS all variations in my DP concepts playlist ❤

[@thekindspill]

Awesome. Thanks a lot bhai

[@ujjawalraj6096]

Yes it is much needed do ASAP

[@sauravbiswajit8091]

Yup .. waiting for that eagerly and plus dp using hashing and dp with bitmasking and partition dp variations also....in upcoming videos...😊😊

[@sauravbiswajit8091]

Koi Aisa kuch jald bazzi nahin chahiye ...Aram se jayenge lamba jayenge..best KZbin channel banayenge 😊

[@codestorywithMIK]

@sauravbiswajit8091 It means a lot Saurav 😇❤️❤️❤️

[@adityasoni5303]

the way u explain any concept is just amazing..........keep it up......and thanku very much

[@codestorywithMIK]

Thank you so much Aditya 😇❤️🙏

[@dayashankarlakhotia4943]

Understood. Please make full series on LIS AND LCS

[@codestorywithMIK]

Yessss. The next video on DP Concepts and Qns will be on LIS and all it’s variants will be covered

[@vivekkumaryadav9862]

thanks sir..bht badiya or simple way se explain kiye aap.

[@codestorywithMIK]

Thank you 😇🙏

[@rohithboppey3205]

Hey MIK! Been a subscriber for so long, and here is my first comment. I have done my dry run and understood the algorithm, but can you give a example where the count array is being updated multiple times, I will dry run it for better understanding. Thanks a lot MIK for uploading videos regarding Leetcode POTD daily! Huge love. 💖

[@codestorywithMIK]

Hi Rohit, thank you so much for all the love and respect you guys have given me. Please try a dry run with this one also - [1,3,5,4,7,2,3,4,2,3,4,5] Might be lengthy, but it helps.

[@rohithboppey3205]

@@codestorywithMIK sure sir. Will do it and keep a GitHub gist link for my fellow viewers. Thank you for replying sir.

[@ishwarkokkili7646]

Please make LIS - recursion + memo, Bottom up dp and all the LIS pattern questions in dp concept and questions

[@codestorywithMIK]

Yes yes already planned . I have all the list. One by one i will post in dp concepts playlist

[@wearevacationuncoverers]

++

[@kishan.17]

Super explanation bro ❤ always yours stories are great to understand ans learn bro

[@codestorywithMIK]

Thank you so much Kishan 😇❤️ Glad it was clear. Also recursion memo version will be uploaded in DP concepts playlists soon

[@anuppatankar4294]

Crystal Clear Explanation 👌🏻

[@codestorywithMIK]

Thanks a lot Anup 😇❤️

[@sauravbiswajit8091]

As usual great ji 😊😊

[@codestorywithMIK]

Thank you so much Saurav ❤😃

[@RAUSHANKUMAR-gw9ri]

Your explanations is really good.🎉

[@codestorywithMIK]

Thanks a lot Raushan ❤️

[@user-jp9jd6el1f]

bro so detailed and well explained All the best bro Now u get new Subscriber

[@codestorywithMIK]

Thank you and welcome to my channel ❤️

[@AstroboyHimanshu]

This video is Pure Gold ❤❤✨✨🙏🙏

[@codestorywithMIK]

Means a lot. Thank you so much ❤️❤️❤️

[@codeandtalk6]

I solved it own ❤❤❤ thank you bro

[@codestorywithMIK]

Wowww Awesome 😇👍🏻

[@user13443fg]

why (dp[j]+1>dp[i]) this condition in "else if" block ?? why cant simply write else?

[@AryanTomar_2025]

Sir please iska recursive + memo solution bhi explain kardo

[@codestorywithMIK]

Yes yes, coming in DP concepts playlist

[@jeelanibasha3984]

I have a doubt if we have an example with arr of 1,3,2 according to the code we would get max cnt as 1 but can't it be 2 as (1,3)(1,2)

[@tauquirahmed1879]

The level of concentration that I give when bhaiya say "Ab dhyan dena ab maza ayega" is unmatchable. 🥰

[@codestorywithMIK]

Ah, you just made my day. Thank you so much Tauquir ❤️❤️ I hope today’s video was worth learning

[@tauquirahmed1879]

@@codestorywithMIK haan bhaiya... 💞💯

[@wearevacationuncoverers]

Lol. exactly 😅

[@souravjoshi2293]

ha ha. sahi me bhai

[@thekindspill]

true

[@deepakagrawal7687]

I have seen this problem solving by other youtubers as well but one query is still present, why for 1,3,5,4 in count array value is 1? Definition of count array is total LIS ending at ith index. so if we take example of 1,3,5,4 then LIS is 3 ((1,3,5), (1,3,4)) but in count array the value you have shown is {1, 1, 1, 1} which means there is only 1 count of LIS with 3 but in reality there are 2 LIS. Am I missing something?

[@Rajdweep]

great explanation bro,i was trying to find the count in recursive way using prev and index in function,bt im unable to do so...is there a way to find the count while going top down in LIS?

[@codestorywithMIK]

Yes i will post that in DP concepts playlist Thanks a lot 😇🙏❤️

[@Rajdweep]

@@codestorywithMIK okk cool

[@AyushRaj-we2og]

Understood😇😇

[@AlishaKhan-ww3io]

You are a legend

[@UtkarshPatel-v9o]

maja aa gaya

[@codestorywithMIK]

Thank you so much for watching 😇❤️

[@abc-ym4zs]

bhaiya if possible can u tell me what are the patterns u are going to discuss in your dp series up to now how many patterns u discussed in future which pattern u will discuss bhaiya

[@codestorywithMIK]

1.Linear DP 2.Knapsack 3.Multi Dimensions DP 4.Interval DP 5.bit DP 6.String DP 7. Variants of LIS, LCS, Cadane's, 8. DP on Trees 9. MCM and it's variants More might come as time comes. Hope this help 😃

[@053_tanweer7]

Hey mik! Can you solve this with recursion + memo?

[@codestorywithMIK]

Hi there 🙂 yes yes, I will upload it in DP concepts and Qns playlist where I will first teach LIS, then all it's variants

[@053_tanweer7]

@@codestorywithMIK I have coded it but not able to memoize it?

[@053_tanweer7]

@@codestorywithMIK this is giving TLE... PLZ MEMOIZE IT class Solution { public: int n; mapm; vectorv; void solve(int idx, vector& dp, vector &nums){ if(idx nums[idx]){ // take v.push_back(nums[idx]); solve(idx-1,dp,nums); v.pop_back(); // not take solve(idx-1,dp,nums); } else solve(idx-1,dp,nums); } int findNumberOfLIS(vector& nums) { n= nums.size(); v.push_back(1e9); vector dp(n,-1); solve(n-1,dp,nums); for(auto it:m){ cout

[@kartikforwork]

hey i found the code of piority sort or lasy sort you taught in lis for this, but its a difficult to understand can you make a video explaining using this method. will wait for it. ty in adv here is the code- class Solution { public: int findNumberOfLIS(vector& nums) { vector piles; piles.push_back({{nums[0], 1}}); for (int i = 1; i < nums.size(); ++i) { int num = nums[i]; int idx = 0; for (; idx < piles.size(); ++idx) { if (piles[idx].back().first >= num) break; } int lis_count = 0; if (idx > 0) { for (int j = piles[idx - 1].size() - 1; j >= 0; --j) { if (piles[idx - 1][j].first >= num) break; lis_count += piles[idx - 1][j].second; } } else { lis_count = 1; } if (idx == piles.size()) { piles.push_back({{num, lis_count}}); } else { piles[idx].push_back({num, lis_count}); } } int result = 0; for (auto& pair : piles.back()) { result += pair.second; } return result; } };

[@s.s.shetty6548]

what will be the time complexity for this?

[@codestorywithMIK]

It’s O(n^2) because for every i, we traverse j from 0 to i-1 resulting in nested for loop

[@rajkrishanmahajan2373]

can little bit explain what is LIS AND LCS ? 😅

[@codestorywithMIK]

Sure 😇 LIS - Longest Increasing Subsequence LCS - Longest Common Subsequence Do not worry, all these and their variants will be covered in my DP concepts playlist

[@amitkumarchoudhary9008]

Bhaiya recursive mai kaise hoga without using dp

[@codestorywithMIK]

I will upload it in DP concepts and Qns playlist

[@doctorajshorts1590]

can you please make a video on 273. Integer to English Words on leetcode , please

[@codestorywithMIK]

Noted on this. Let me soon plan

[@floatingpoint7629]

not sure why my comments are not appearing

[@codestorywithMIK]

Yes sometimes youtube does it. I am also not sure why ☹️

[@yashgarg3027]

bhaiya core subjects ka kuch bata do kase karu 1 week ma ho jae ache se as placements season has started plz help bhaiya

[@codestorywithMIK]

Data Structures and Algorithms: Understanding data structures like arrays, linked lists, trees, graphs, and algorithms like sorting, searching, Time complexity. Database Management Systems (DBMS): Learn about database design, normalization, SQL queries, and database management concepts, ACID properties etc. Also, Learn about relational databases, normalization, and SQL queries. Operating Systems: Gain knowledge about processes, threads, memory management, file systems, and synchronization. Computer Networks: Understand the basics of networking, including protocols, IP addressing, routing, and network layers. Object-Oriented Programming (OOP): Understand OOP principles and concepts like inheritance, polymorphism, and encapsulation. This is a rough idea on what major things should be focused in short span of time.

[@yashgarg3027]

@@codestorywithMIK bhaiya jitne ye aapne topics btae hain corr subjects k more than sufficient hain na ??

[@Slow_learner33]

@@yashgarg3027 yes bro , exactly because very less companies ask system design you can skip it if u have less time

[@codestorywithMIK]

Yes

[@codestorywithMIK]

Freshers are not asked much on System design . Since you are a fresher, strengthen the important topics first only.

[@abhishekjha3499]

bro i am a student and would like to take your opinion on one thing as you can see aaj kal sab ne 500 plus question krrkhe he leetcode pe and then so it is possible ki un 500 questions pe unhone kai sheets bb solve krii hogi famous sheets jisko lekar log gurantee dete he ki use solve krne se job hojyegi and i also think that wo sheets ke question achee he and u need lot of practice to solve them and its not everybody cup of tea , to bhai aapko bb lagta he ye jo post krte he mostly linkedin pe its fake ??kuki mene bb kaii interviews dekhe he and mostly inhi me se pchte he and max to max system design ya aapke projects me se what do you think??

[@thedarkknight1865]

Memo DP || Java class Solution { private record Pair(int length, int count) {} private int n; private Pair[][] dp; public int findNumberOfLIS(int[] nums) { n = nums.length; dp = new Pair[n][n+1]; return solve(0, -1, nums).count(); } private Pair solve(int idx, int prev, int[] nums) { if(idx == n) return new Pair(0, 1); if(dp[idx][prev + 1] != null) return dp[idx][prev + 1]; Pair notPick = solve(idx + 1, prev, nums); int notPickLen = notPick.length(); int notPickCount = notPick.count(); int pickLen = 0; int pickCount = 0; if(prev == -1 || nums[idx] > nums[prev]) { Pair pick = solve(idx + 1, idx, nums); pickLen = pick.length() + 1; pickCount = pick.count(); } Pair res = null; if(pickLen == notPickLen) { res = new Pair(pickLen, pickCount + notPickCount); } else if(pickLen > notPickLen) { res = new Pair(pickLen, pickCount); } else { res = new Pair(notPickLen, notPickCount); } return dp[idx][prev + 1] = res; } }

[@codestorywithMIK]

And here it is ❤️🔥 Thanks a lot for sharing

[@wearevacationuncoverers]

Thanks for sharing this bro @codestorywithMIK are you planning to cover recursive version as well in your concepts playlist ?

[@AryanTomar_2025]

Bro can you explain that how count is updating