3116. Kth Smallest Amount With Single Denomination Combination | Weekly Leetcode 393

Segment Tree Series - bit.ly/segment-trees
*************************************************
Contest Link - leetcode.com/contest/weekly-c...
Problem Link - leetcode.com/contest/weekly-c...
Solution - leetcode.com/problems/kth-sma...
*************************************************
Timestamps -
00:00 - Agenda
00:25 - Problem Description
01:47 - Brute Force Solution
04:00 - [Reduced Problem] [Approach 1] - Combining all the elements
05:05 - [Reduced Problem] [Approach 2] - Figure only first K elements
07:03 - [Reduced Problem] [Approach 3] - Binary Search for Kth smallest
13:50 - Dry run of the Algorithm
19:28 - Removing duplicates from the count of smaller elements
26:28 - Recap of Algorithm
28:44 - Time Complexity of complete Algorithm
30:33 - Code Walkthrough
*************************************************
Interview Experiences Playlists -
Microsoft - • Microsoft Interview Qu...
Amazon - • Amazon Interview Quest...
D.E.Shaw - • D.E.Shaw Interview Que...
Linkedin - • Linkedin Interview Que...
Facebook - • Facebook (Meta) Interv...
*********************************************************************
Please show support and subscribe if you find the content useful.

[@Dawodu_Johnson]

I have about 8 emails. You should recognise my name 😅...the one with the guitar. Just wanted to let u know I have subscribed with all of them

[@codingmohan]

Thank you!
But you don't need to do this. My motive with this channel is just to make few people better at coding :)

[@UnknownLearner-od3qn]

Great explanation!! Relating to existing Previous Problems is awesome❤❤❤

[@vaibhavagarwal2421]

figured out it involoved bitmasking and bs during contest, but had no clue about inclusion-exclusion part. Great video tho👍

[@HARSHMISHRA-lb5nr]

Thanks for your playlists

[@vaibhavkumar8341]

What if answer given by binary search (say x) is not a valid amount? I think we also need to validate the x finally. If x can be formed by some coin then okay else find minimum valid amount >=x from all coins and take minimum among them. Please correct me if I'm wrong.

[@shivamjoshi4176]

Got goosebumps after seeing value of k
But he explained it so precisely

[@raghavendrac4710]

Thank you sir!

[@hritikanand9734]

mind blowing 🤯🤯

[@souravshaw8904]

Great explanation 💯

[@mayankjohari1951]

Nice explanation

[@executioner769]

Waiting for your Video

[@sanjai_rs7]

31:30 can you share in which video have u explained that Bit masking concept.

[@jawadkaiyal5008]

i would be very thankful if you write the solution code in python

[@jiaxuwu2114]

Thank you sir. But I want ask a question (maybe stupid). Why can we sure that the return value l is in the given arrays.

[@bhavanidattchalumuru]

In approach 3, question is about finding the kth smallest or kth largest ? Because in a case where we have more than k elements on both side, if we check the first side and ignore the right side(which is where the kth largest element will be in case when the array is sorted increasing manner ) then it will be an issue.

[@codingmohan]

It's kth smallest and hence we need to check specifically for the left side.

[@aniny]

Can anyone explain the cnt%2 part and why are we adding subtracting accordingly??

[@codingmohan]

It is because the expression containing odd number of sets are added in the union formula whereas the one with even number of sets are subtracted.
For example - AUB = A + B - AnB. Notice A and B are positive (expression with just 1 set i.e. odd number of sets).

[@iWontFakeIt]

classic inclusion exclusion principle to be followed!

[@JIGARSINGTHAKOR-yy6qp]

Difficult 😢