You are given a 2D integer array points where points[i] = [xi, yi, zi] represents a point in 3D space, and an integer array target representing a target point.
Define generation 0 as the initial list of points. For each integer k >= 1, form generation k as follows:
a = [x1, y1, z1] and b = [x2, y2, z2] taken from all points produced in generations 0 through k - 1.c = [floor((x1 + x2) / 2), floor((y1 + y2) / 2), floor((z1 + z2) / 2)] and collect every such c into a generation k.k are produced simultaneously from points in generations 0 through k - 1.k is formed, the points in the generation k are considered available for forming later generations.Return the smallest integer k such that the target appears in one of the generations 0 through k. If the target is already in the initial points, return 0. If it is impossible to obtain the target, return -1.
Notes:
(x, y, z) coordinates. A point cannot be paired with itself, and pairing two points with identical coordinates is not possible.
Example 1:
Input: points = [[0,0,0],[6,6,6]], target = [3,3,3]
Output: 1
Explanation:
points = [[0, 0, 0], [6, 6, 6]].target = [3, 3, 3] does not exist in generation 0.[0, 0, 0] and [6, 6, 6], we generate [3, 3, 3].points = [[0, 0, 0], [6, 6, 6], [3, 3, 3]].target = [3, 3, 3] is found in generation 1, so the smallest k is 1.Example 2:
Input: points = [[0,0,0],[5,5,5]], target = [1,1,1]
Output: 2
Explanation:
points = [[0, 0, 0], [5, 5, 5]].target = [1, 1, 1] does not exist in generation 0.[0, 0, 0] and [5, 5, 5], we generate [2, 2, 2].points = [[0, 0, 0], [5, 5, 5], [2, 2, 2]].[0, 0, 0] and [5, 5, 5], we generate [2, 2, 2].[0, 0, 0] and [2, 2, 2], we generate [1, 1, 1].[5, 5, 5] and [2, 2, 2], we generate [3, 3, 3].points = [[0, 0, 0], [5, 5, 5], [2, 2, 2], [1, 1, 1], [3, 3, 3]].target = [1, 1, 1] is found in generation 2, so the smallest k is 2.Example 3:
Input: points = [[0,0,0],[2,2,2],[3,3,3]], target = [2,2,2]
Output: 0
Explanation:
points = [[0, 0, 0], [2, 2, 2], [3, 3, 3]].target = [2, 2, 2] already exists in generation 0, so the smallest k is 0.Example 4:
Input: points = [[1,2,3]], target = [5,5,5]
Output: -1
Explanation:
Constraints:
1 <= points.length <= 20points[i] = [xi, yi, zi]0 <= xi, yi, zi <= 6target.length == 30 <= target[i] <= 6Problem Overview: You start at point (1,1). In one generation you can transform (x, y) into either (x + y, y) or (x, x + y). Given a target point (tx, ty), determine the minimum number of generations required to reach it, or return -1 if it is impossible.
Approach 1: Breadth‑First Search (Exponential)
Start from (1,1) and simulate every possible generation using BFS. Each state generates two children: (x + y, y) and (x, x + y). Stop when the target appears. While this guarantees the minimum generations, the search space grows extremely fast because coordinates increase every step. Time complexity is O(2^g) where g is the number of generations, and space complexity is also O(2^g) due to the queue.
Approach 2: Reverse Subtraction Simulation (O(max(tx, ty)))
Instead of building forward from (1,1), work backward from the target. If the last move produced (tx, ty), then one of the coordinates must have been the sum of the other and its previous value. That means the previous state was either (tx - ty, ty) or (tx, ty - tx). Repeatedly subtract the smaller coordinate from the larger until you reach (1,1). This mirrors the idea behind the greedy reduction used in the Euclidean algorithm. Time complexity is O(max(tx, ty)) in the worst case with O(1) space.
Approach 3: Greedy with Modulo Optimization (O(log n))
The subtraction process can be accelerated using a mathematical observation. If tx > ty, the previous value of tx must be tx % ty after multiple reverse steps. Instead of subtracting ty repeatedly, jump directly using the modulo operation. Continue reducing the larger coordinate until one becomes 1. When one coordinate is 1, the remaining generations are simply the difference in the other coordinate. This turns the process into a variant of the Euclidean GCD algorithm, commonly seen in math and greedy interview problems. Time complexity becomes O(log(max(tx, ty))) with O(1) space.
Recommended for interviews: Start by describing the brute force BFS to show understanding of the state transitions. Then pivot to the reverse greedy strategy. Interviewers usually expect the modulo‑optimized version because it reduces the process to a Euclidean‑style reduction with O(log n) time and constant space.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search | O(2^g) | O(2^g) | Conceptual understanding of state transitions; impractical for large targets |
| Reverse Subtraction | O(max(tx, ty)) | O(1) | When demonstrating the reverse construction idea without optimization |
| Greedy with Modulo (Euclidean Reduction) | O(log n) | O(1) | Optimal solution for large coordinates; expected interview answer |
Practice Minimum Generations to Target Point with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor