LeetCode 3923 - Minimum Generations to Target Point
This problem defines a process that repeatedly creates new 3D points from existing points. We begin with the given list points, which forms generation 0.
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Simulation
Solution
LeetCode 3923 - Minimum Generations to Target Point
Problem Understanding
This problem defines a process that repeatedly creates new 3D points from existing points.
We begin with the given list points, which forms generation 0. For every later generation, we consider all distinct points that have been created so far, including points from every previous generation. For each pair of distinct points, we create a new point whose coordinates are the component-wise floor averages:
$$\left( \left\lfloor \frac{x_1+x_2}{2}\right\rfloor, \left\lfloor \frac{y_1+y_2}{2}\right\rfloor, \left\lfloor \frac{z_1+z_2}{2}\right\rfloor \right)$$
All newly generated points form the next generation simultaneously.
The goal is to determine the smallest generation number at which the target point first becomes available. If the target already exists among the initial points, the answer is 0. If the target can never be produced, we return -1.
A crucial detail is that only distinct coordinates may be paired. If two points have identical coordinates, they cannot be used together. Likewise, a point cannot be paired with itself.
The constraints are extremely small:
- At most 20 initial points.
- Every coordinate is between 0 and 6 inclusive.
- The target coordinates are also between 0 and 6.
These constraints are the key observation. Since every coordinate lies in [0,6], there are only:
$$7^3 = 343$$
possible distinct points in the entire universe.
No matter how many generations are produced, the process can never create more than 343 unique points. This finite state space makes exhaustive exploration feasible.
Several edge cases are important:
- The target may already exist initially.
- There may be only one starting point, making generation impossible.
- New generations may repeatedly recreate points that already exist.
- The target may be unreachable even after all possible points have been generated.
- A point can often be generated through multiple paths, and we need the minimum generation number.
Approaches
Brute Force
A direct simulation would explicitly build generation 1, then generation 2, then generation 3, and so on.
For each generation, we would consider every pair of points available so far and generate all possible midpoint points. We would continue until either the target appears or no new points can be created.
This approach is correct because it exactly follows the process described in the statement. However, it repeatedly recomputes the same midpoint relationships and does not exploit the fact that the entire state space contains only 343 possible points.
While the constraints are small enough that even this method could pass, it is not the most elegant way to think about the problem.
Key Insight
Instead of thinking in terms of generations of points, think in terms of the earliest generation at which each point becomes available.
Suppose point A first appears at generation gA and point B first appears at generation gB.
Once both points exist, they can be paired in the next generation. Therefore the midpoint point C can first appear at:
$$\max(gA, gB) + 1$$
This creates a shortest-path style problem.
Each possible point is a state. Whenever two states are known, they can produce another state with a cost determined by the above formula.
Because there are only 343 possible points, we can repeatedly relax these generation values until no improvement is possible.
This is essentially a multi-source shortest-path computation over a very small state space.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(V³) | O(V) | Simulates generations directly, repeatedly recomputes pairs |
| Optimal | O(V³) | O(V) | Computes earliest generation for every reachable point using relaxation |
| Here V = 343 possible points |
Although both approaches have similar asymptotic bounds due to the tiny state space, the optimal approach directly computes minimum generations and avoids explicit generation-by-generation simulation.
Algorithm Walkthrough
Let V = 343, the number of possible 3D points.
1. Represent every point uniquely
Store each point as a tuple (x, y, z) so it can be used inside hash-based data structures.
Create a map:
dist[point] = earliest generation point becomes available
Initialize all starting points with generation 0.
2. Handle the trivial case
If the target already exists among the initial points, return 0.
3. Repeatedly relax reachable points
At any moment, every point whose generation is known can participate in future constructions.
For every pair of distinct reachable points:
- Let their generations be
g1andg2. - Compute their midpoint
mid. - The midpoint can first appear at:
new_generation = max(g1, g2) + 1
If this is better than the currently known generation of mid, update it.
4. Continue until no improvements occur
Whenever a point receives a smaller generation value, that information may help produce better values for other points.
Therefore continue performing relaxation passes until an entire pass makes no changes.
5. Return the answer
If the target point has a generation value, return it.
Otherwise return -1.
Why it works
The key invariant is that dist[p] always stores the smallest generation discovered so far for point p.
Whenever two points become available at generations g1 and g2, the earliest moment they can be paired is after both already exist, namely generation max(g1, g2) + 1. Every valid construction of a point must follow this rule.
The relaxation process considers every possible pair repeatedly until no smaller generation values can be found. At convergence, every point stores the minimum generation achievable by any valid sequence of constructions. Therefore the target's value is exactly the answer.
Python Solution
from typing import List, Tuple
from math import inf
class Solution:
def minGenerations(self, points: List[List[int]], target: List[int]) -> int:
target_t = tuple(target)
dist = {}
for p in points:
dist[tuple(p)] = 0
if target_t in dist:
return 0
changed = True
while changed:
changed = False
current_points = list(dist.items())
n = len(current_points)
for i in range(n):
p1, g1 = current_points[i]
for j in range(i + 1, n):
p2, g2 = current_points[j]
if p1 == p2:
continue
mid = (
(p1[0] + p2[0]) // 2,
(p1[1] + p2[1]) // 2,
(p1[2] + p2[2]) // 2,
)
candidate = max(g1, g2) + 1
if candidate < dist.get(mid, inf):
dist[mid] = candidate
changed = True
return dist.get(target_t, -1)
Implementation Explanation
The dictionary dist stores the earliest generation for every discovered point.
All initial points are inserted with generation 0, since they already exist before any construction occurs.
The main loop performs relaxation. During each pass, every pair of reachable points is examined. The midpoint is computed coordinate by coordinate using integer floor division.
If the midpoint can be reached earlier than previously known, its generation value is updated.
The process continues until a complete pass produces no changes. Since there are only 343 possible points and generation values only decrease when updated, convergence is guaranteed.
Finally, the target's generation value is returned if present.
Go Solution
package main
func minGenerations(points [][]int, target []int) int {
type Point struct {
x, y, z int
}
dist := make(map[Point]int)
for _, p := range points {
dist[Point{p[0], p[1], p[2]}] = 0
}
targetPoint := Point{target[0], target[1], target[2]}
if _, ok := dist[targetPoint]; ok {
return 0
}
changed := true
for changed {
changed = false
type Entry struct {
p Point
g int
}
current := make([]Entry, 0, len(dist))
for p, g := range dist {
current = append(current, Entry{p, g})
}
n := len(current)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
p1 := current[i].p
p2 := current[j].p
if p1 == p2 {
continue
}
mid := Point{
(p1.x + p2.x) / 2,
(p1.y + p2.y) / 2,
(p1.z + p2.z) / 2,
}
candidate := current[i].g
if current[j].g > candidate {
candidate = current[j].g
}
candidate++
old, exists := dist[mid]
if !exists || candidate < old {
dist[mid] = candidate
changed = true
}
}
}
}
if ans, ok := dist[targetPoint]; ok {
return ans
}
return -1
}
Go-Specific Notes
The Go version uses a struct Point as the map key because structs containing only comparable fields are valid map keys.
Unlike Python's tuples, Go requires a dedicated type to represent coordinates efficiently.
Integer division in Go already performs floor division for non-negative values, which matches the problem constraints because all coordinates are between 0 and 6.
Worked Examples
Example 1
Input:
points = [[0,0,0],[6,6,6]]
target = [3,3,3]
Initial state:
| Point | Generation |
|---|---|
| (0,0,0) | 0 |
| (6,6,6) | 0 |
Relaxation:
| Pair | Midpoint | Generation |
|---|---|---|
| (0,0,0),(6,6,6) | (3,3,3) | 1 |
Updated table:
| Point | Generation |
|---|---|
| (0,0,0) | 0 |
| (6,6,6) | 0 |
| (3,3,3) | 1 |
Target appears at generation 1.
Answer:
1
Example 2
Input:
points = [[0,0,0],[5,5,5]]
target = [1,1,1]
Initial state:
| Point | Generation |
|---|---|
| (0,0,0) | 0 |
| (5,5,5) | 0 |
First relaxation:
| Pair | Midpoint | Generation |
|---|---|---|
| (0,0,0),(5,5,5) | (2,2,2) | 1 |
State:
| Point | Generation |
|---|---|
| (0,0,0) | 0 |
| (5,5,5) | 0 |
| (2,2,2) | 1 |
Second relaxation:
| Pair | Midpoint | Generation |
|---|---|---|
| (0,0,0),(2,2,2) | (1,1,1) | 2 |
| (5,5,5),(2,2,2) | (3,3,3) | 2 |
Target first appears at generation 2.
Answer:
2
Example 3
Input:
points = [[0,0,0],[2,2,2],[3,3,3]]
target = [2,2,2]
The target already exists among the initial points.
Answer:
0
Example 4
Input:
points = [[1,2,3]]
target = [5,5,5]
Only one point exists.
No valid pair can ever be formed.
The state never changes.
Answer:
-1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(V³) | Up to V relaxation passes, each examining O(V²) point pairs |
| Space | O(V) | Stores generation value for each reachable point |
Here V = 343, the total number of possible 3D points.
Because V is a fixed constant derived from the coordinate range [0,6], the practical runtime is very small. The algorithm comfortably fits within the problem constraints.
Test Cases
sol = Solution()
assert sol.minGenerations([[0, 0, 0], [6, 6, 6]], [3, 3, 3]) == 1 # example 1
assert sol.minGenerations([[0, 0, 0], [5, 5, 5]], [1, 1, 1]) == 2 # example 2
assert sol.minGenerations([[0, 0, 0], [2, 2, 2], [3, 3, 3]], [2, 2, 2]) == 0 # example 3
assert sol.minGenerations([[1, 2, 3]], [5, 5, 5]) == -1 # example 4
assert sol.minGenerations([[0, 0, 0], [2, 2, 2]], [1, 1, 1]) == 1 # direct midpoint
assert sol.minGenerations([[0, 0, 0], [1, 1, 1]], [0, 0, 0]) == 0 # target initially present
assert sol.minGenerations([[0, 0, 0]], [0, 0, 1]) == -1 # single point cannot generate
assert sol.minGenerations(
[[0, 0, 0], [6, 6, 6]],
[1, 1, 1]
) == 3 # repeated halving chain
assert sol.minGenerations(
[[0, 0, 0], [6, 6, 6]],
[2, 2, 2]
) == 2 # intermediate point
assert sol.minGenerations(
[[0, 0, 0], [6, 6, 6]],
[6, 6, 6]
) == 0 # endpoint already exists
Test Summary
| Test | Why |
|---|---|
[[0,0,0],[6,6,6]] -> [3,3,3] |
Direct generation in one step |
[[0,0,0],[5,5,5]] -> [1,1,1] |
Requires multiple generations |
| Target already present | Verifies immediate return of 0 |
| Single initial point | No generation possible |
| Direct midpoint case | Simplest constructive scenario |
| Existing target among endpoints | Confirms generation 0 handling |
| Unreachable with one point | Validates impossibility detection |
| Deep halving chain | Tests repeated constructions |
| Intermediate reachable point | Verifies minimum generation tracking |
| Existing endpoint target | Confirms original points remain available |
Edge Cases
Target Already Exists Initially
A common mistake is to begin generating new points before checking whether the target is already present. If the target is one of the original points, the answer must be 0 regardless of what future generations could produce.
The implementation handles this immediately after initializing the distance map.
Only One Reachable Point
When there is only one point in the system, no valid pair of distinct points exists. Therefore no new point can ever be generated.
The relaxation loop simply performs no updates, and the algorithm correctly returns -1 unless the target was already present.
Multiple Ways to Generate the Same Point
A point may be reachable through several different construction sequences. Some paths may require more generations than others.
For example, a midpoint might be generated directly in generation 2 or indirectly in generation 4. A naive simulation that only tracks existence could lose this information.
The dist map stores the minimum generation discovered for every point, and relaxation only updates when a smaller generation is found. This guarantees that the final answer is the earliest possible generation.
Repeatedly Generated Points
Many pairs may recreate points that already exist. Without careful handling, an implementation might repeatedly process duplicates and incorrectly increase generation counts.
The algorithm stores a single entry per coordinate in dist. Once the optimal generation for a point is known, worse generation values are ignored, preventing duplicate creations from affecting correctness.