This can be done in one pass by counting how many of the 0th elements are in each array, as well as doubles. A valid swapping will have the count of a 0th element from both arrays equal to length + doubles. Then just return the minimum for valid swappings minus the unnecessary swaps for doubles.
Ashish Subudhi anytime! If you like my explanations sign up for the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining the annual tier
Kevin Naughton Jr. yeah. Had no idea it was a leetcode question. Love the content by the way! I have been using your playlist for these to study for interviews. Absolutely nailed my one this morning. The other question I got in the same challenge was something about watering two plants with two watering cans and returning the minimum number of trips you would need to take between the plant and the hose to water both.
Can someone explain me why are we just stopping after exploring the four possibilities, why cant we try matching A and B with B[1] or A and B with A[1] as target (so on for B[2] as target and A[2] as target), why stop with just exploring for A[0] and B[0] ?
I had some difficulty understanding this as well hence I am here. I am going to give this a try. If there a solution possible, then the target value has to match A[0] or B[0], this is because both A[0] and B[0] are included in the final solution. Also we are trying to find a case where all the elements match to target not max number of matches. This is exactly why target becomes A[0] or B[0]. You could try this as well: It doesn't have to A[0]/B[0], it could be any element A[i]/B[i] where i is [0,n) If interested, here is a gist with experiment at each index: gist.github.com/bdevapatla/87f89ff60a54c2f7415012e1d45d9045
I think you can skip the last two calls to numSwaps. if you have 10 tiles and you swapped 7 times, it also implies that you could have swapped it just 10 - 7 = 3 times.
Because we need to swap all dominoes to have the same number on the top, or the bottom, since we start from the first domino we know that only those 2 numbers are valid, so lets say: You start with a domino that has 5 : 2 if the rest of the dominoes don't have a 5 or a 2 there's no way you could line all of them in a single row, either you line them in the 5 or you line them in the 2.
Since we know the values can be between 1-6, what if we run through both the arrays first and create an array of count 6 having the count of each number 1-6 within A, B (2 auxiliary arrays ). Now there can be at max 2 elements across all of A,B for which there can be n elements on a single side post flipa. So before doing any of the above logic we need to run through the array once to check if such a combination is possible or not - if not we return -1 or otherwise we can figure out the qualifying number easily ( it should be present at every index atleast one among both Domino arrays A,B ) Then we can find the minimum swaps as ( number of elements - (max occurence of element between A,B)).
Just an approach, since we know only possible values are from 1-6, can’t we run a loop for either of the array to see if value can be Ai by swapping with Bi or not.
I kinda get why we are checking for one index but maybe if we choose a different index other than 0, minimum swaps would be less than what we get by choosing zeroth index?.
Ahmer Khan Yes the most common value is directly proportional to the minimum number of swaps i think, So by computing the min swaps will get us the most common value in the domino’s.
Because we need to swap all dominoes to have the same number on the top, or the bottom, since we start from the first domino we know that only those 2 numbers are valid, so lets say: You start with a domino that has 5 : 2 if the rest of the dominoes don't have a 5 or a 2 there's no way you could line all of them in a single row, either you line them in the 5 or you line them in the 2.
This may be overthinking it, but wouldn't a relatively easy optimization be to pass the minSwaps value into the function as currentMinSwaps every time you try a new swap iteration, returning Integer.MAX_VALUE as soon as your numSwaps is equal to currentMinSwaps? This way if you solve for A[0] in 2 swaps you don't have to continue iterating over a potential 100000 dominos for another value
oh yeah this makes sense one of those 2 dominoes must be the number for equal row, otherwise, there is no equal row I looped over all domino numbers to check valid equal row number but this is more general solution for arbitrary domino #
the number we r swapping must be present in all the ith element atleast once so we could just loop through the list with A[0] element and B[0] element alone cause the element should be present in these 2 .
Sir ,it would be great if u upload contest problems because u explain very well .I like the way u explain the things in easy way and there is no good content for the explanations of contest questions of leetcode on TH-cam .Sir, please upload contest questions explanation if possible . Thanks in advance
Because in order for this to be possible every Domino needs share a number. So they could either share the top or the bottom of the first Domino since even if every other Domino shared a value if they don't all have one of the values on the first Domino it is impossible.
Haha, I'm so ashamed of my solution after seeing yours, my solution adds the first 2 numbers to a set and if the set size is 2 and one of the two numbers is not in the set I remove it from the set and map how many times I saw each number on the top and the bottom. After that I just find the min by doing : let moves = Number.MAX_VALUE; for(let num of dominoesSet){ moves = Math.min(moves, numDominoes - topMap.get(num), numDominoes - bottomMap.get(num)); } since I check in the beggining if the dominoes length is less than 2 and in the loop that I go through if I don't find either number in the set I just return -1 when you do this you get the min number of swaps xD
Check Line 16, If there is no solution possible, numSwap will return Integer.MAX_VALUE whenever it is call. so, min(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE) -> Returns Integer.MAX_VALUE
Can someone please explain why we are only looking at A[0] and B[0]? What if for example there was no way to get everything the same matching A[0] but for another index of A it would be possible to match? That's the part of the question and answer I don't get. Thanks.
ie if A[1] contained a 1, and B[1] contained a 5, and then every other index of B contained a 1, then your solution should be num of swaps = 1 and you're only swapping A[1] for B[1]. With this algorithm you are going through every index to try to match it to A[0] or B[0], why is that the optimal solution? Sorry if I am missing something obvious here.
4 ปีที่แล้ว
Keep it up! Looking forward for more videos from you, don't stop! Would you like to be TH-cam friends? :)
*WE LOVE DOMINOS*
instagram: instagram.com/kevinnaughtonjr/
twitter: twitter.com/kevinnaughtonjr
patreon: www.patreon.com/KevinNaughtonJr
This can be done in one pass by counting how many of the 0th elements are in each array, as well as doubles. A valid swapping will have the count of a 0th element from both arrays equal to length + doubles. Then just return the minimum for valid swappings minus the unnecessary swaps for doubles.
You make things look simple by looking at problems from a different angle. Thanks much 👍
Ashish Subudhi anytime! If you like my explanations sign up for the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining the annual tier
I got this exact question when I did my coding challenge for Google back in like November.
NO WAY
Kevin Naughton Jr. yeah. Had no idea it was a leetcode question. Love the content by the way! I have been using your playlist for these to study for interviews. Absolutely nailed my one this morning. The other question I got in the same challenge was something about watering two plants with two watering cans and returning the minimum number of trips you would need to take between the plant and the hose to water both.
@@Gersssy Nice and anytime thanks for supporting the channel! hmm sounds like an interesting problem thanks for sharing :)
@Gers I think plant watering is also a leetcode problem. Can’t recall exact problem. Solved last year.. Did you use treemap?
Can someone explain me why are we just stopping after exploring the four possibilities, why cant we try matching A and B with B[1] or A and B with A[1] as target (so on for B[2] as target and A[2] as target), why stop with just exploring for A[0] and B[0] ?
I had some difficulty understanding this as well hence I am here. I am going to give this a try.
If there a solution possible, then the target value has to match A[0] or B[0], this is because both A[0] and B[0] are included in the final solution. Also we are trying to find a case where all the elements match to target not max number of matches. This is exactly why target becomes A[0] or B[0].
You could try this as well: It doesn't have to A[0]/B[0], it could be any element A[i]/B[i] where i is [0,n)
If interested, here is a gist with experiment at each index: gist.github.com/bdevapatla/87f89ff60a54c2f7415012e1d45d9045
@@baurks Thank you so much for the explanation.
@@baurks Thanx for this amazing explanation ❤
I think you can skip the last two calls to numSwaps. if you have 10 tiles and you swapped 7 times, it also implies that you could have swapped it just 10 - 7 = 3 times.
I also thought so.
You are right.
Hey kevin. Noob here. Can u please explain y we need to checkk only the first value and not any otherrvalue?
Because we need to swap all dominoes to have the same number on the top, or the bottom, since we start from the first domino we know that only those 2 numbers are valid, so lets say:
You start with a domino that has 5 : 2
if the rest of the dominoes don't have a 5 or a 2 there's no way you could line all of them in a single row, either you line them in the 5 or you line them in the 2.
for two of your combinations we need to add 1 to the number of swaps because making A[0] appear in B[0] means you swapped
Since we know the values can be between 1-6, what if we run through both the arrays first and create an array of count 6 having the count of each number 1-6 within A, B (2 auxiliary arrays ).
Now there can be at max 2 elements across all of A,B for which there can be n elements on a single side post flipa. So before doing any of the above logic we need to run through the array once to check if such a combination is possible or not - if not we return -1 or otherwise we can figure out the qualifying number easily ( it should be present at every index atleast one among both Domino arrays A,B )
Then we can find the minimum swaps as ( number of elements - (max occurence of element between A,B)).
Amazing explanation. Thanks Kevin!
problem seemed so daunting at first, then u mentioned 4 possibilities and just like that, it become easy.
Nicely explained the solution + Weirdest mustache ever.!!
Just an approach, since we know only possible values are from 1-6, can’t we run a loop for either of the array to see if value can be Ai by swapping with Bi or not.
Nice approach but why are you giving preference to 0th index. I read question thrice no where it mentioned about zeroth index!
I kinda get why we are checking for one index but maybe if we choose a different index other than 0, minimum swaps would be less than what we get by choosing zeroth index?.
I was wondering about the same thing. Couldn't we have taken the index with the most common value
Same question. Kevin, please do explain
Ahmer Khan Yes the most common value is directly proportional to the minimum number of swaps i think, So by computing the min swaps will get us the most common value in the domino’s.
Because we need to swap all dominoes to have the same number on the top, or the bottom, since we start from the first domino we know that only those 2 numbers are valid, so lets say:
You start with a domino that has 5 : 2
if the rest of the dominoes don't have a 5 or a 2 there's no way you could line all of them in a single row, either you line them in the 5 or you line them in the 2.
Awesome! The videos are getting better and better. ^^
Algorithm Implementer thanks!
This may be overthinking it, but wouldn't a relatively easy optimization be to pass the minSwaps value into the function as currentMinSwaps every time you try a new swap iteration, returning Integer.MAX_VALUE as soon as your numSwaps is equal to currentMinSwaps? This way if you solve for A[0] in 2 swaps you don't have to continue iterating over a potential 100000 dominos for another value
This is a nice approach Kevin..
when you look at your runtime (1260 ms) and see kevins... Despair.
oh yeah this makes sense one of those 2 dominoes must be the number for equal row, otherwise, there is no equal row
I looped over all domino numbers to check valid equal row number but this is more general solution for arbitrary domino #
the number we r swapping must be present in all the ith element atleast once so we could just loop through the list with A[0] element and B[0] element alone cause the element should be present in these 2 .
Sir ,it would be great if u upload contest problems because u explain very well .I like the way u explain the things in easy way and there is no good content for the explanations of contest questions of leetcode on TH-cam .Sir, please upload contest questions explanation if possible .
Thanks in advance
keep going Kevin. you rock :)
Thanks Keshav :)
kevin where were u for past months you really r the best
please upload more leetcode medium questions
thanks so much and just got busy :)
Nice solution. Thanks!
I wish you can execute the code and shoe results as well.
How many leetcode questions have you completed so far? Just curious
What is the problem number??
Is there any reason you don't just return -1 directly in line 16? You wouldn't need the ternary operator in line 9.
If -1 will be returned Math.min will fail
I don't get why every value of A has to match B[0] or every value of B has to match A[0]?
Because in order for this to be possible every Domino needs share a number. So they could either share the top or the bottom of the first Domino since even if every other Domino shared a value if they don't all have one of the values on the first Domino it is impossible.
Haha, I'm so ashamed of my solution after seeing yours, my solution adds the first 2 numbers to a set and if the set size is 2 and one of the two numbers is not in the set I remove it from the set and map how many times I saw each number on the top and the bottom.
After that I just find the min by doing :
let moves = Number.MAX_VALUE;
for(let num of dominoesSet){
moves = Math.min(moves, numDominoes - topMap.get(num), numDominoes - bottomMap.get(num));
}
since I check in the beggining if the dominoes length is less than 2 and in the loop that I go through if I don't find either number in the set I just return -1 when you do this you get the min number of swaps xD
Smooth explanation.
thanks!
is this being asked for engineering residency?
not sure tbh
🔥
Kevin can you make dsa cheet sheet for fang interviews,please n do you have discord or telegram?
I got this question asked by Google...it was actually my first interview question ever in my career lol
NO WAY
did you get an offer?
how does minSwaps == Integer.MAX_VALUE ever evaluate to true? minSwaps is never assigned Integer.MAX_VALUE to be its value.
Check Line 16, If there is no solution possible, numSwap will return Integer.MAX_VALUE whenever it is call. so, min(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE) -> Returns Integer.MAX_VALUE
Now since this video is the google search first result, Google will never ask this question...lol atleast in 2020.
Please do video on grid illuminating problem leetcode
I'll add it to my list
@@KevinNaughtonJr Thank you.
Keep it up! Looking forward for more videos from you, don't stop! Would you like to be TH-cam friends? :)
Bro be regular in uploading videos
Anirudha Talmale I’ve uploaded every day for like the past 10 days???
Can someone please explain why we are only looking at A[0] and B[0]? What if for example there was no way to get everything the same matching A[0] but for another index of A it would be possible to match? That's the part of the question and answer I don't get. Thanks.
ie if A[1] contained a 1, and B[1] contained a 5, and then every other index of B contained a 1, then your solution should be num of swaps = 1 and you're only swapping A[1] for B[1]. With this algorithm you are going through every index to try to match it to A[0] or B[0], why is that the optimal solution? Sorry if I am missing something obvious here.
Keep it up! Looking forward for more videos from you, don't stop! Would you like to be TH-cam friends? :)