Leetcode 3923 | Minimum Generations to Target Point | Leetcode biweekly contest 182

Ajouté : 2026-05-10

[00:00:00]Hello. In this video, let's discuss third question of today's contest. You are given a 2D integer array points where points of I is xi, yi, zi represents a point in a 3D space and an integer target representing a target point. Define the generation zero as the initial list of points. For each integer K more than equal to one, form the generation K points as follows.

[00:00:22]Consider every pair of two distinct points x1, y1, z1 and x2, y2, z2 taken from all the points produced in the generation zero through K minus one.

[00:00:32]For each such pair, compute a new point which is floor of x1 + x2 / 2 and so on.

[00:00:38]And collect every such C into a new generation K.

[00:00:42]All the points in the generation K are produced simultaneously from the points in zero to K minus one.

[00:00:48]After generation K is formed, the points in the generation K are considered available for the later generations.

[00:00:54]Return the smallest integer K such that the given target appears in one of the generation zero through If the target is in the initial points, then it is zero.

[00:01:04]If it is impossible, then return minus one.

[00:01:06]And the floor denotes the down to the nearest integer.

[00:01:11]So, floor of one plus one plus four by two it is equal to two because five by two floor is equal to two.

[00:01:19]Two distinct points means that two chosen points must have different x, y, z coordinates.

[00:01:24]And the constraints are the points are up to only 20. The values are six. The target length is only three. It means it is a valid and then target of I is less than or equal to six.

[00:01:33]So, the question is over complicated, but it is very simple, right?

[00:01:36]So, the question is very simply saying that initially we have let's say initially we have some uh five points.

[00:01:43]Let's say we have five x, y, z in the generation zero.

[00:01:49]Now, given these five points, what we have to find?

[00:01:53]This is the zeroth generation. So, how can we find the values in the first generation.

[00:01:58]We have to take every two distinct coordinates from the before set. For example, let's say this is the zeroth generation. So, in the first row, we have to consider these two. And then, we have to produce some kind of sun with respect to these two. So, this will contain the floor of these two by two, floor of y by two, and floor of z by two. And then, we should consider these two points. And then, we should consider these two, and these two, and these two, these two, these two, these two, these two, these two.

[00:02:26]So, if you have n points in the before generation, then how many Let's assume that these are n distinct, right? Let's assume if these are n distinct. So, how can we find the number of points in the generation plus one of the before one?

[00:02:39]We have to take every two, and then we have to find a new coordinate, new tuple, indirectly. Tuple means simply 3D point 3D point.

[00:02:48]x, z, y. So, this is called tuple. So, two is called a pair. Three is called tuple. So, for every tuple, we have to find a new tuple for every pair in the before generation tuple.

[00:03:00]And then, what is the time complexity for doing this? It will be n squared, right? Because if you have n points, then we can select n into n minus one by two number of distinct pairs to get a new point.

[00:03:13]So, the time complexity for this will be n squared. And then, and then, is there a way like is there a use of storing same coordinate twice?

[00:03:23]Let's say we have 111. And let's say we have Sorry, let's take 000 and 222.

[00:03:29]Now, let's assume these are in the zeroth generation. So, in the first generation, what are the points that are available? They are 000, 222.

[00:03:37]All the before points also will exist.

[00:03:39]But, new points will be generated where the new points are from before pairs.

[00:03:44]So, the only pair that we can form in the generation one because of these two are 111.

[00:03:50]Because these two are the only pairs, right? So, in the generation one, these three are the only coordinates we have.

[00:03:56]So, and now let's come to second generation.

[00:03:59]So, in the second generation, these three points will be existing. And then coming to the new points, what are new points will be there? Let's first start with these two.

[00:04:07]So, given these two, the new point formed is 111. So, we already have 111.

[00:04:11]So, is there a way to maintain this also 111 in the new vector?

[00:04:15]No, because there is no use at all. For example, if we have 111, and let's say we are storing 111.

[00:04:20]And then let's assume the other pair.

[00:04:22]So, what is the use of storing this?

[00:04:24]Because if the new coordinate, if we are trying to find, then we can find between these two. No need to find between these two, because these both will give Let's say this is giving tuple one.

[00:04:34]So, these both also will give tuple one.

[00:04:36]So, indirectly, no need to store the same tuple again.

[00:04:40]And if we are trying to store the same, then by these two, only the same will be formed again.

[00:04:46]That's why if no need to maintain two sim two same things, because two same things will not give a new one, or two same things will not give a new one with the other one.

[00:04:57]So, if this is if these both are giving tuple one, these both also will give give same. So, very simply, we have to store only the unique tuples XYZ in the generation. So, now what can we do?

[00:05:07]The constraints are very small, right?

[00:05:09]So, the points are only up to six. Let's assume seven. So, the target It means the points are only less than or equal to seven. So, what is the net volume?

[00:05:18]Let's say what are uh So, what are the total points that we can have? It is 7 into 7 into 7.

[00:05:23]So, these are the only points that we have. These many distinct points that we have. And that is simply 343.

[00:05:29]So, now what we should do? Let's go with the same brute force, because the time complexity for forming the new generation is n squared.

[00:05:37]Let's assume if we are finding the Right? Because if we have n points, and for next, it will be n into n plus 1 by 2. n into n plus one by two.

[00:05:48]And then we will get all these points and then we will get a new generation using all these n all these distinct pairs and so on.

[00:05:58]Now one question thing the one thing that we have to address is till how many generations we have to keep on traversing until we get that point.

[00:06:05]We can't do infinite times, right?

[00:06:07]Because even though it's time complexity is this, if we are doing ultimate like infinite times, it will not be possible. So how to find what is the maximum number of generations where we can try to get this as answer.

[00:06:19]So one thing, the point should be like given a target, there are two possibilities. The first thing is the answer can be there.

[00:06:27]It can be there in some kth generation or it cannot be there at all. So if there is in kth generation, then we can try to loop till some 10 power six or highest value and then we can break if we find this value. But what if we don't have any guarantee that this point will not be there, then we'll keep on traversing.

[00:06:46]Right? But what if the number found is in only ninth 10 power ninth generation?

[00:06:52]So we can't loop through ultimately. So how to find if there is answer or not?

[00:06:56]So that is the that is one thing left.

[00:06:58]Because if we know if the target element exists or not and then we want to know what is the maximum generation. These two are the points to be addressed. So how to do this?

[00:07:07]So instead of complicating, let's say we got we discussed that, right? We only have 343 points.

[00:07:14]If we even if we do 10 power nine generations, the points the total number of distinct points are only up to 343.

[00:07:21]So can we keep an upper bound or can we keep a maximum number of generations?

[00:07:26]Can we find that? Yes.

[00:07:28]So let's say we are at the generation one zero and let's say we are generation k and then we are trying to form k plus one generation.

[00:07:36]So if the values in in k is equal to values in k plus 1. For example, if there are three points in this and after doing all the computation, even then we got only three distinct points in this. So, what does that mean then?

[00:07:50]It means there is no use of continuing this because the points are only distinct.

[00:07:55]So, these distinct points will come in valid iterations, maybe some finite iterations or something.

[00:08:02]It will be very less.

[00:08:03]So, there is no need of keeping the loop ultimately.

[00:08:07]If the points in the generation K is equal to the number of points in generation K + 1, it means all the points are generated and the no new points can be generated. And that's why we can break the loop here itself.

[00:08:18]Because if these are the only three points, then even if you go to next generation, only these three can be found.

[00:08:23]That's why if the current set if the current elements in K and then if we are trying to find the K + 1 if all the values are same, it means we are unable to add any new element.

[00:08:35]Let's take the same example. Let's take 0 0 0, 2 2 2, and 1 1 1.

[00:08:41]Now, is there any way of adding the new point into this?

[00:08:45]Let's initially the values are 0 0 0, 2 2 2. And now we came to next generation, so we got a new point 1 1 1. Now, now what are the points in the next generation? These three will come again, 0 0 0, 1 1 1, 2 2 2. Now, are there any new points that can be found? Let's check. Let's take these two. So, if we take these two, then we have to take floor. So, 0 0 0 will be formed again, so no new point. And coming to these two, even then 1 1 1 will come, but it is already there, so no use. And then let's come to this. So, even if we are taking these two, then 1 1 1 will come.

[00:09:16]That's why we got that these three are the only points that are there and these three points cannot be increased. So, why to waste? So, simply break the loop.

[00:09:24]And if the point is existing, let it For example, in the Kth generation, we have X points and in the next generation, if we are able to get more than X points, more than X tuples, then we can keep on continuing because we are sure that the points are only up to 343.

[00:09:40]Right, the points are only up to 343.

[00:09:42]So, we can loop till at most 343 generations. Even though this is not possible, but this can be like a at most at most upper bound.

[00:09:50]So, we can we can loop through 343 generations and then we can keep on continuing the finding the elements in the next generation from the previous. And then if these both are same, then break the loop.

[00:10:02]And we can check if the target is in generation or not.

[00:10:07]So, let's discuss for the last time. So, initially we have generation zero. Now, we'll check if the tuple is in this list. If yes, we can return here itself.

[00:10:15]Else, we will start the loop. And then in the loop, we will loop through every two distinct values and then we'll get all the new points. Now, in the new points, we'll check if the present if the target is there or not. If it is there, we'll return. Else, we'll continue to the next generation. And so on till 350 generations.

[00:10:31]So, if we did not find element, then we'll return minus one. Else, we would have returned our answer in the middle itself.

[00:10:36]So, how to maintain how to write the code? We can simply maintain a set because we only want the distinct tuples. So, maintain set of tuple. So, for a tuple, we can have vector of three elements or we can maintain two pairs.

[00:10:51]Pair of pair of in comment comment. And then we have a tuple also, which is very useful here. So, we can simply maintain array of int {comma} three. So, this is like a three vector size element.

[00:11:04]So, this is what the All right, so we are storing in the set.

[00:11:07]So, initially maintain the set and then loop through all the initial values and then push into current. So, this is the zeroth generation. Now, if the current contains this target, Sorry, if Yeah, if count contains the target values, then simply return zero because it is in the zeroth generation itself. Else, you can add any element here because this will be broken sometime in the middle itself. So, loop till any number of generation and then maintain the next set of points in the next generation. How to find it? It is very easy. So, loop through all the before points.

[00:11:38]Loop through every distinct J and I and then find the net point new point. So, add the new point into next. And with the new points, we can maintain the previous points as well. So, these are the previous points. So, in the new vector, add the before generation all the points and then for all the before points, loop through each and every value and then add new pair formed for every double.

[00:12:01]New double formed for every two distinct doubles.

[00:12:03]And then add to the vector. And then if we simplify this, then return the generation.

[00:12:07]And if this is equal to before value, it means no points can be increased. So, simply break the loop. Else, current is equal to next.

[00:12:15]And if you're unable to find, then return minus one.

[00:12:18]If you have any doubts, comment below.

[00:12:19]See you in the next video.