Leetcode Weekly Contest 503 | Video Solutions - A to D | by Vibhaas| TLE Eliminators

Added: 2026-05-25

[00:00:00]Hello everyone and welcome to Tminators PC for lead code weekly contest 503.

[00:00:07]Today we'll discuss all the problems from A to D in today's contest.

[00:00:12]Let's begin with problem A. Since problem A and B are simple, we'll do them quickly and we'll do problems C and D in more detail.

[00:00:21]Okay, problem A. We are given a sorted integer array and an integer K and we need to return an array such that each distinct element appears at most k times.

[00:00:36]Now obviously there are many ways to solve this question and you can take advantage of the fact that the integer array is sorted right but there's a very simple method um which works for any sorted or unsorted array. Uh obviously you can optimize this to O of N. The best answer for this will be O of N but there's a simple N login method which works and since the time is just um N is equal to 100 it really doesn't matter. Um there are other versions like can you solve this in place etc etc. You can try that later on but for the contest it doesn't really matter. So what's the simple and fast solution you can do in a contest?

[00:01:20]Well, all you can do, all you need to do is just make an answer vector, right?

[00:01:24]You need to make an answer vector.

[00:01:28]And what we can do is we can keep a count of how many times an element has appeared. So for each element in this given vector, let's say nums, right? Each element, we have a map to do the keep the counts, right? So we have a map to keep a count for each element or frequency. So we can just uh do like if the count of if the count of x is k or it has become greater than k or basically if it's exactly k already like it's already been added x times to the answer then we can just continue otherwise we can increase the count and just add it to the answer vector right and this ensures that at most um at most k values of x right each unique value at most k times gets added to answer and that's it the time complexity of this because we're using maps is n login but if you use unordered map it will become big of n which is the same as the expected time complexity for the question obviously if you want to do with big of one space in place you can think of that but in the contest accepted is what matters so let's move on to the next Okay, let's do problem B.

[00:02:56]Uh, okay.

[00:02:59]Problem B, this is also a very simple question. Um, maybe even simpler than problem A. All it's saying is the strength of a password is calculated. One point for any letter between A and Z. Two points for capital A and Z. Uh three points for digits from 0 to 9. Five points for any one of these symbols. Right? So like if you have this then five points. If you have both of these then five points. Right? So that's how it is. And also if a let's say small a appears twice you will not add + 1 + 1 two times you just calculated based on the distinct occurrences right so you need two things one you need somewhere to calculate the distinct occurrences and the second is to actually just sum up the points right so the way I have done this and obviously there are many different ways again it's just an implementation question is put all the characters of the string of the password string into a Okay, so we can make a set of characters and we can initialize this with the begin and end pointer for a password string. So we can just do pass begin right and pass end. This is where initializing using a range you can you can initialize all the STL containers with some given range. This puts all the elements in a set and what is a set? A set is unique. So it only has the unique values.

[00:04:30]Now we can just do for each character right for each character in the set we can just add up the score right so if it's lower case a to zed add + one right um if it's upper A to Z add + 2 right and so on. If it's um digit 0 to 9 add three and if it's a symbol add five right that's basically the logic and then you can turn the answer now obviously the time complexity again to make the set is going to be n login right to find whether it's distinct or not at some point you'll have to sort or you'll have to use some sorted container unique container which will all give you an log in time complexity. So this is a very valid solution and I believe this is optimal.

[00:05:29]Of course um if you use a hash table it'll be of right if you use a hash table it will be of so that's a slightly better solution but anyways let's have a look. So we have answer zero we have these we put it in the set. Um, if it's not any of these, it has to be a symbol. So, we increase by five and then we return the answer. Right? That's it.

[00:05:53]Simple and short code.

[00:05:57]Okay. Let's go on to problem C where the real fun starts in this contest. I would say this contest was a very balanced contest overall. Right? This is what I expect from lead code contest. First two questions are roughly easy. Third question is slightly more challenging and the fourth question uses some interesting topic of some sort. So overall I would say it's a balanced lead code contest.

[00:06:23]Okay, let's have a look at this question. It says we need to sort an array and we have only two operations.

[00:06:29]One is reverse the entire array and the other is rotate left by one. Okay. And this array is a permutation from the range 0 to n minus one. Right.

[00:06:40]As we know what a permutation is, it's just an array which has all the numbers from 0 to n minus one in some order.

[00:06:48]Right?

[00:06:50]Right? In some order okay so now I want to know what what are the arrays which I could possibly reach using the rotation operation. Okay. So obviously we know the time constraints it's O of N right?

[00:07:04]N is given as 10^ 5. So you need to find some O of N or N login solution.

[00:07:10]Okay. So let's examine this question. Um let's take the example array n= 4. Okay.

[00:07:17]Because the size is handleable. N is equal to 4. So that means the permutation is 0 1 2 3.

[00:07:26]Right? So how could have 0 1 2 3 come?

[00:07:29]Like if you do exactly one rotation where can you go? Right? So if you do one rotation it will become 1 2 3 0.

[00:07:36]Right? It will become 1 2 3 0.

[00:07:40]If you do another rotation, it's going to become 2 3 0 1, right? And if you do another rotation, it'll become uh 3 0 1 2, right? And if you do another rotation, it will come back to the top again. So, it comes back here, right?

[00:08:03]Okay. So, now let's do a reversal. All right? Let's do a reversal here.

[00:08:09]of this and we get 3 2 1 0 right we get 3 2 1 0 okay now what happens if we do this reversal and then we rotate okay if we do this reversal and we rotate um so if we rotate this we get 2 1 03 right we get 2 1 03 so Um, interestingly you will see that 2103 is exactly the reversal of this right.

[00:08:44]So if we rotate this we get this element which is exactly the reversal of this.

[00:08:51]Okay. Now what happens if we reverse this uh sorry if we if we rotate this okay and if we rotate this you will see that again you get um 1 32 right which is the exact reversal of this right so you can see there this graph with like some nodes and their rotation their um mirror image kind of nodes right and here the edges go this Okay, here the edges will go upwards, right? You can show this pretty easily or you can observe this pretty easily, right? So, we get 2 3 uh sorry, we get 0 3 2 1, right? And this is basically the graph and you can get a feeling of how to do this is just simply write all the permutations which you can visit, right? Because obviously they've given us a minus one case as well, right? So these are all the possible permutations you can visit.

[00:09:52]Basically all the possible permutations is a set which is the original array and all of its shifts as well as the reverse array and all of its possible shifts. Right?

[00:10:06]And then every array can reach its reversed form. And then if you're going this way you'll have to go like this. If you're going this way you have to go the other way around. All right.

[00:10:18]Okay. And now what is our target?

[00:10:20]Imagine this like a graph of permutation. What is our target? Our target is this node. Right? This node is our target. That is our target. We want to reach this node somehow.

[00:10:32]We can see that there are two cases, right? Either we start with an array, right? Either we start with an array which is like um which is like the correct way around, right? So we have it's a rotation of 0 1 2 3 basically then obviously we can go the direct route right we can just follow this edge and reach here right and what is the formula for this uh as you can see this took us one two steps right this took us 1 2 3 steps right this took us zero steps right so it's 0 3 2 one step right or in other words in other words it's just the position of the zero right so the number of steps to go normally and reach here is just I right let's say I is equal to position of zero in the permutation right position of zero in permutation then the number of steps taken to go like this is I right so for case where given array is a rotation of sorted array.

[00:11:56]Right? The solution, one solution is I.

[00:11:59]Okay? And what is the other solution?

[00:12:03]The other solution is imagine you started somewhere here. Okay? Then what you can do is you can do a mirror. Okay?

[00:12:10]You do a mirror step. Then you go up like this, right? You do a rotation like this and then you do another mirror step. All right? So you take a path which is something like this. Right? Okay.

[00:12:26]So that's the other way. So one step to do the mirror then you take a path upwards. So we don't know how many steps that is plus one step to do another mirror. Right? Or another reverse.

[00:12:40]Let's see how many steps it takes to travel upwards. Right? And for this also you can see a simple pattern. Right?

[00:12:47]Here this is zero steps. This is one step.

[00:12:51]This is two step. Three step.

[00:12:54]Right? So you can come up with many formulas. But the easiest one is simply I + 1 mod N. Right? I + 1 mod N. Why?

[00:13:03]Because see here it takes us one step and 0 is at position 0. So 0 + 1 is 1.

[00:13:09]Here 0 + uh here 1 + 1 is 2 here it's three right and here once it reach the fourth position it will become zero again right so the number of steps to start at a node here and go up is I + 1 mod n where i is the position of the zero right remember i is the position of the zero that's what we discussed right i is the position of the zero so the answer for the case where the array is a rotation of the sorted array simply I + 1 mod n + 1 right so either we do this way or we do this way one of these two ways will give us the minimum and that's the answer right and now for the second case for case where given array is mirror of this sorted array or is rotated right is mirror uh is rotation of the mirror array Okay. Rotation of mirror of the sorted mirror of reverse whatever.

[00:14:19]Right? Now what do we do in this case?

[00:14:22]Let's have a quick look. Okay. So here we're starting out somewhere. Let's say here, right? We're starting out somewhere here. One method is we do a rotate and then we do it normally. Right? One method is we do a rotate and we do it normally. So we do a mirror and then we do it normally, right? Like we do a mirror then we follow the rotations, right? The other idea is we do it this way and then here we do the mirror step.

[00:14:50]Right? We do it this way and then here we do the mirror step. Okay? So these are the two cases over here. Let's just write them out. When we do a mirror then the position of the zero becomes 10 - i - 1. Right? This should be obvious because this zero is at three here.

[00:15:06]Sorry, the zero is at two here and it will become at one here. Right? And the reason is simple because we are flipping it about n minus one, right? So n - 1 - i is the rotated zero, right? So the answer will be minimum of 1. This is for the flipping plus n - 1 - i. Right?

[00:15:29]Okay. And what is the other case? The other case is first we go up and then we flip.

[00:15:36]So how much time does that take? It takes I + 1 mod N. Right? I + 1 mod N + one. Right? So these are the two cases in the answer and these are their respective answers. And in the case that the array is not a rotation of the sorted array and not a rotation of the mirror sorted array, then obviously we need to print minus one, right? Return minus one. Otherwise, right? And how do you check which case it is? Well, you can just find the position of the zero which is required, right? You can find the position of the zero, see if it's increasing from zero onwards or see if it's going this way from zero onwards. Right? So that is just a for loop. If you're trying to solve lead code C, then you should be able to write a for loop to check whether a given array has a given structure or not. Right? So that much you should be able to do.

[00:16:35]Okay, obviously this whole process is big of n because all we're doing is just checking if it matches either the rotated sorted array or rotated mirror array and then we're just using a formula after finding the position of zero. Right? Okay.

[00:16:53]Let's have a look at the code.

[00:16:57]Um yeah so I is the position of the zero which is the minimum element. That's how I found it. Now we're checking if it's the first case or second case. So reverse case is set to false. Now we check for the first case. Right? We're checking if starting at zero all the numbers are matching.

[00:17:17]If at some point they don't match I'm going to set the reverse case as true.

[00:17:20]Right? So if they're not matching there must be the reverse case. I set it to true and I break out. Right? So I'm I'm checking it over here. If I have guaranteed that's the reverse case I need to check if um whether the array matches the reverse case right and if it doesn't match at any point then that means none of the cases are matching I return minus one right I return minus one. If we have confirmed that the reverse case is holding, I can use this formula.

[00:17:51]All right, it's the exact same formula if you have a look.

[00:17:55]Otherwise, I use the standard formula for the sorted rotated sorted case, right?

[00:18:02]Okay. And that's about it for this question. Time complexity will be O of N, right? If you implement this correctly, it's of Okay, let's move on to problem D.

[00:18:26]Okay, problem D is less about um getting a nice idea like problem C. Problem D is more about knowing a standard um idea or like a concept. So if you don't know this concept, it might be a bit hard for you.

[00:18:40]But yeah, so it's a query type question and it will use some query type concept.

[00:18:45]Okay, you're given two arrays nums 1 and nums 2.

[00:18:50]Now have a look. Nums one has a length of only five. Okay, nums one has a length of only five. Nums 2 has a length of 5 * 10^ 4.

[00:19:01]Nums 2 has a length of 5 * 10^ 4.

[00:19:22]Okay. So immediately we can see that these sizes are a bit um odd like nums one is very small right. Let's see what effect that has on the question.

[00:19:34]Um okay so the question asks we have a bunch of queries. The first is a change type of query where we have to change the array uh nums and the second one is the answer type of query where we have to give an answer right and the second one we have to give the answer of how many pairs are there right how many pairs are there such that nums one j plus nums 2 k is equal to exactly total where total is given in the query right given in query right and these are the forms of queries and again there's 5 into 10^ 4 queries I believe right there's 5 into 10^ 4 queries okay and what is the change or what is the update we are given we're basically given In this vector nums 2, we can take a range or a subarray and we can add a value to it. Okay, we can take a range or a subarray and incremented by value.

[00:20:50]Right?

[00:20:53]So every element over here becomes plus value plus value plus value. Right?

[00:21:00]There is no such thing as subtract here.

[00:21:02]So that's convenient. The values are always positive. Total is always positive and yeah the numbers go up to 10^ 5 the value being added goes up to 10^ 5 etc etc the 10^ 4 queries right okay so when we're given n and q as 10^ 4 right number of queries and size of the second array is being taken as n because first array is obviously not important right first array we understand the reason why it's only five because we can just try all five cases This is here and here we have 10^ 4 different cases which we have to reduce somehow right we also know that n and q are going to be at most 5 * 10^ 4 right and 5 * 10^ 4 is interesting number because it allows more than just n login it allows big of n of n login big of n root n all these solutions to pass right uh n root n sorry in fact it's pretty lenient and it might even allow n root n login solution to pass maybe right this might be on the boundary but it might pass okay and most probably the expected solution will be somewhere here just guessing from the constraint okay just guessing from this the solution should probably be somewhere here right otherwise they would have given 10^ 5 if the question was supposed to be solved with of n or n login.

[00:22:41]Okay.

[00:22:43]So next let's think about how to solve this. Right. First off we need to count how many values are equal to the total.

[00:22:53]Right. So then since the nums one has only five cases we can do for each value in nams one we need to find a case uh we need to find a case. So we need to basically find count how many elements are equal to uh count how many elements are equal to total right the given total in this query minus x right because then basically we have just taken and this and moved it to this side. Right? So nums 2 of K is equal to total minus nums one of J. Right? That's the idea. This is the formula. And then this is X.

[00:23:54]Right? This is X because we're trying all the nums one of J.

[00:23:58]So we need to just count this. We need to add it to the answer to the query and give it as an answer. Right? So answer is zero. Answer plus equal to this. And then we can see all the answers must be given back as a vector. So we can push back to that vector. Right? Okay. This is going to be the structure of how we answer our queries. That much is obvious. But how do we find this bound, right? And the question reduces to How do we find count of elements of a given element? Right? So how do we find this query?

[00:25:03]When we can do range sum update, right? We can do when we have range sum update, right? Range some update because that's what the first query is. Update a given range. Add this value to all the elements.

[00:25:24]Right?

[00:25:26]So now when you're thinking of rain sub update obviously you're going to think of something like lazy sector that you're going to think of something like lazy sector right but then lazy se has no way of finding the count of a given element right there's no way to find count of given element efficiently right we need it very efficiently here we cannot find that in a lazy set okay let's think of map Because map is good for finding counts, right? Each element's count can be put in the map. But then how do we do range update on map, right? We cannot do a range update on a map.

[00:26:07]So that part is also going to be kind of hard, right? Okay. So the idea which we'll settle on is an interesting one and the topic is called square root decomposition. Okay. Square root decomposition.

[00:26:24]Okay, we will basically expand on the map idea using square root de composition and what we'll say is okay what we'll say is um divide the big nums to vector right into chunks right into chunks of size square root of n right we will have different chunks of square root of n or you could take some constant k which is roughly near the size of square root of n right the last one may be smaller than square root of n because it's the remainder but that's fine now for each of these chunks I have a map okay I have a map map one map for chunk two map for chunk three right so on how many maps will I have total well we know that I will have n /<unk> n maps which is equal to roo<unk> 10 maps right n / square is root n maps total right which is not too much that's like 200 200 is the root of 4 * 10^ 4 so uh roughly 200 220 maps that's fine I can allocate that much in memory right okay so I have root maps in my memory now what I can do is whenever I have a range update from L to Uh right. So from this to this we need to sum value right we need to sum value then what happens is over here I can manually sum the value into the map. Okay here I can manually sum the value into the map like I can be I can remove this element from the map and add that element plus value to the map.

[00:28:20]Right? I can do that now for these maps. Instead of changing the elements themselves, I will have a variable because this value is getting added to this whole range, right? It's going to affect this whole range. So what I'm going to do is I'm just going to mark that this range has had this value added. So I'll call that lazy and I will increment the lazy of the maps in between. Okay, I will increment the lacy of the maps in between.

[00:28:53]Now this last these elements again these elements I will manually go inside the map. I'll be like map of num of i minus minus then nums of i is plus equal to value and then map of nums of i ++ right? So I'm manually editing the map over here.

[00:29:14]Now if you have a look this is a pretty brilliant data or algorithmic concept because here the size is at most root 10 right the size of this chunk is at most root 10 so at most root 10 elements are affected right are affected here again at most root 10 elements are affected affected. All right. And now here as well when we do this jump we're not editing the individual elements. We're just editing the lazy value of the whole map. So that's go of one for each of them.

[00:29:58]So again in between also at most we go of root and variable lazy variable are incremented right. So the overall time complexity for updating this way right the overall time complexity for updating this way is big of root n and since we are using standard map data structure there's an extra log factor so but log of the size of the map right size of the map is at most log of root 10 so this is the total time of update okay this is the total time of update Cool. Now we need to do um query, right? Now we need to do query.

[00:30:47]We already have this structure.

[00:30:50]So remember our formula. We have to count how many elements are there. But here we don't have a global map. So we need to go through all root and maps, right? So for solving query with this method solve query.

[00:31:04]So yeah the is divided into this square root number of partitions. Right? Now for each partition the root and partition right for each partition I will check the map of that partition for total minus x and obviously the lazy of this this this partition will be added right so I must subtract that also so map of total minus x minus lazy for each map right for each map for each iat map, right? And that will be added on to my answer, right? And how much time will this take?

[00:31:46]It has to go through all the maps. There are square root of n maps. Each query in the map will be log of roo<unk> n again.

[00:31:54]So the time complexity of this is also root n log root n, right? And all of this will happen for total q queries. So the overall complexity of the solution right this is the overall complexity of the solution which as you can see is very close to 10 <unk>10 log n actually it's slightly It's n roo<unk> n log roo<unk> 10 right and as you can see it's somewhere between these two time complexities we discussed right it's somewhere over here so yeah it probably passes and indeed it does pass this square root decomposition on maps kind of solution all right that's the idea how does this look like in code let's have a look Right. Okay. So, first I'm taking this vector nums two and copying it to vector nums which is of type long law.

[00:33:11]Why am I doing that? Because when we repeatedly add the value could become bigger than long law which is an error I did get. It overflowed in the first submissions which I did. So that's why I changed it to long law.

[00:33:24]That's why it's long long over here.

[00:33:27]Now here are maps right total how many maps are needed n / k ceiling right n divided by k ceiling maps are needed that's exactly what I've written here k I've taken as root of uh 10^ 4 right 5 * 10^ 4 which is 220 roughly even if this is 200 250 the time complexity should pass but if you're closer to root 10 it's better right okay so these many maps and also the same number of elements in lazy right so n + k minus one by k is how you write seal of n by k that many elements in lazy first we're filling all the elements up in the map over here as you can see now we make our answer vector and we go through each query query type one is update right so what we are doing is at the boundary right at the boundary until it is equal to uh until l mod k is equal to zero right that means you're at the boundary we updating the element manually. Right?

[00:34:28]So, we're going to this map in the correct location L by K, decrementing it, then changing nums of L, adding it back to the map, right? And then doing L++.

[00:34:40]So, similarly for R until the right boundary is equal to mod K minus one, right? So, mod K it's equal to K minus one. That means is at the boundary of the uh array, right? So then we do we have to ensure obviously L is greater than equal to R right and then we can decrement R and do this process right. So then this has made sure that the boundaries are taken care of right like this boundary and this boundary right this boundary until this position is equal to 0 mod k and this this boundary until this position is equal to k - 1 mod k right k - 1 mod k as you can see here once these two are taken care of the boundaries are taken care of which both are root and time then we can from there we can start doing lazy jumps right still from l by k to rx Okay, we can just add it to the lazy values.

[00:35:37]Okay, so this is the type one query and the type two query is here. Um, we just need to go through for each element for each map, right? In map and each element x, right? Each element x in nums one, right? Each element x in nums one total of x total minus total of the query minus x minus lazy. That is our formula.

[00:36:01]If that exists in the map, then we add that to the answer. Why am I writing it like this? Because I don't want to create unwanted nodes in my map, right?

[00:36:08]I don't want to create unwanted nodes in my map and make the size very big.

[00:36:12]That's why I'm first checking if it exists in then I'm accessing it.

[00:36:17]And yeah, that's it. Once you have this answer, we push it back to the answer and we return it. Right?

[00:36:25]Okay, that's bring us to the end of this session. Uh overall I would say a nice balanced set easy somewhat like these first two questions were easy third question was little bit of thinking little bit of ideation I think there are multiple approaches in the third question which will get you to the same answer fourth question I'm pretty sure it's a square root decomp question I'm not sure if there's some better way to solve it offline or something like that but yeah uh it's a standard square root decomp kind of operation If you've ever done square root decom before, you probably might have gotten it. If you haven't, it might take some practice. Yeah, do absolve the last question. Usually lead code last questions are pretty educational. So if you solve the first three, I've solve the last one. If you solve the first two, absolve the third one. Right? The third one is also has some interesting thinking behind it.

[00:37:18]Okay, then thanks for watching. Uh see you later. Bye-bye.