Minimum generations to target point

43.0% acceptance

May 13, 2026

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 generationeration 0 as the initial list of points. For each integer k >= 1, form generationeration k as follows: Consider every pair of two distinct points a = [x1, y1, z1] and b = [x2, y2, z2] taken from all points produced in generationerations 0 through k - 1. For each such pair, compute c = [floor((x1 + x2) / 2), floor((y1 + y2) / 2), floor((z1 + z2) / 2)] and collect every such c into a generationeration k. All points in the generationeration k are produced simultaneously from points in generationerations 0 through k - 1. After generationeration k is formed, the points in the generationeration k are considered available for forming later generationerations. Return the smallest integer k such that the target appears in one of the generationerations 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: floor denotes rounding down to the nearest integer. "Two distinct points" means the two chosen points must have different (x, y, z) coordinates. A point cannot be paired with itself, and pairing two points with identical coordinates is not possible.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_generations(points: Vec<Vec<i32>>, target: Vec<i32>) -> i32 {
    use std::collections::HashSet;
    let target_t = (target[0], target[1], target[2]);
    let mut seen: HashSet<(i32, i32, i32)> = points.iter()
      .map(|p| (p[0], p[1], p[2]))
      .collect();
    if seen.contains(&target_t) { return 0; }
    let mut current_layer: Vec<(i32, i32, i32)> = seen.iter().copied().collect();
    let mut generation = 0i32;
    loop {
      generation += 1;
      let mut next_layer: Vec<(i32, i32, i32)> = Vec::new();
      let all_so_far: Vec<(i32, i32, i32)> = seen.iter().copied().collect();
      for &p in &current_layer {
        for &q in &all_so_far {
          if p == q { continue; }
          let mid = (
            (p.0 + q.0) / 2,
            (p.1 + q.1) / 2,
            (p.2 + q.2) / 2,
          );
          if !seen.contains(&mid) {
            seen.insert(mid);
            next_layer.push(mid);
            if mid == target_t { return generation; }
          }
        }
      }
      if next_layer.is_empty() { return -1; }
      current_layer = next_layer;
    }
  }
}