Leetcode Weekly 379 | Maximize Number of Partitions | Coding With Bharat | DP + Bitmask
Recently there was a Leetcode Weekly Contest 379 where we had this problem: "Maximize Number of Partitions After Operations". We have discussed:
1. Brute Force and Time Complexity
2. Bitset and its use to optimise
3. Thoughts on Conversion to Bitmask DP.
4. Sparse DP and Proof that Complexity is within range.
Connect on Insta: / bharatkhanna1995
Connect on Linkedin: / bharat-khanna-717b4817b
00:00-06:29 Introduction to Problem
06:30-07:10 Trivial case k = 1
07:11-11:48 Brute Force idea 26*n*n
11:49-14:14 Code & failed Optimisation idea
14:15-21:47 Bitset concept
21:48-23:55 Introducing bitset into our brute force
23:56-26:48 Recursion with bitset
26:49-31:10 Code for Recursion & Bitset
31:11-32:21 Time Complexity of Recursion
32:22-33:33 Overlapping Subproblems & DP
33:34-35:00 Code for DP
35:01-44:36 How the hell is this O(N)? Sparse DP Concept
44:37-47:35 Important Takeaways
Пікірлер: 6
Sir please try to cover most of the leetcode hard question
@CodingwithBharat
4 ай бұрын
Yes we will
will (26^3 * n) complexity not give TLE?
@CodingwithBharat
6 ай бұрын
Actual states are going to be even less than that. The real upper bound that I actually found on Leetcode discuss is 26^2 but that is very complicated as proof. The difference between n^2 approach and this approach was - In n^2, it is always n^2 whereas here it is potentially very less than 26^3*n
🎉
@CodingwithBharat
6 ай бұрын
😀🙏