Maximum points activated with one addition

Array Hash Table Union-Find

43.6% acceptance

Mar 31, 2026

You are given a 2D integer array points, where points[i] = [xi, yi] represents the coordinates of the ith point. All coordinates in points are distinct. If a point is activated, then all points that have the same x-coordinate or y-coordinate become activated as well. Activation continues until no additional points can be activated. You may add one additional point at any integer coordinate (x, y) not already present in points. Activation begins by activating this newly added point. Return an integer denoting the maximum number of points that can be activated, including the newly added point.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn max_activated(points: Vec<Vec<i32>>) -> i32 {
    let n = points.len();
    if n == 0 {
      return 1;
    }
    // Union-Find: group points sharing x or y coordinates
    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0u32; n];
    let mut size = vec![1i32; n];

    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x {
        parent[x] = find(parent, parent[x]);
      }
      parent[x]
    }

    fn union(parent: &mut Vec<usize>, rank: &mut Vec<u32>, size: &mut Vec<i32>, a: usize, b: usize) {
      let ra = find(parent, a);
      let rb = find(parent, b);
      if ra == rb {
        return;
      }
      if rank[ra] < rank[rb] {
        parent[ra] = rb;
        size[rb] += size[ra];
      } else if rank[ra] > rank[rb] {
        parent[rb] = ra;
        size[ra] += size[rb];
      } else {
        parent[rb] = ra;
        size[ra] += size[rb];
        rank[ra] += 1;
      }
    }

    // Group by x-coordinate and y-coordinate
    let mut x_map: HashMap<i32, usize> = HashMap::new();
    let mut y_map: HashMap<i32, usize> = HashMap::new();

    for i in 0..n {
      let x = points[i][0];
      let y = points[i][1];
      if let Some(&j) = x_map.get(&x) {
        union(&mut parent, &mut rank, &mut size, i, j);
      } else {
        x_map.insert(x, i);
      }
      if let Some(&j) = y_map.get(&y) {
        union(&mut parent, &mut rank, &mut size, i, j);
      } else {
        y_map.insert(y, i);
      }
    }

    // Get component sizes
    let mut comp_sizes: Vec<i32> = Vec::new();
    for i in 0..n {
      if find(&mut parent, i) == i {
        comp_sizes.push(size[i]);
      }
    }
    comp_sizes.sort_unstable_by(|a, b| b.cmp(a));

    if comp_sizes.len() >= 2 {
      comp_sizes[0] + comp_sizes[1] + 1
    } else {
      comp_sizes[0] + 1
    }
  }
}