Detect squares

Array Hash Table Design Counting Data Stream

52.3% acceptance

Feb 25, 2026

1006

258

There is a 2D integer plane containing some points. Implement the DetectSquares class: DetectSquares() Initializes the object with an empty list of points. void add(int[] point) Adds a new point point = [x, y] to the list of points. int count(int[] point) Counts the number of ways to choose three points from the list such that the three points and point form an axis-aligned square with positive area. Example: Input: ["DetectSquares","add","add","add","count","count","add","count"] [[], [[3,10]], [[11,2]], [[3,2]], [[11,10]], [[14,8]], [[11,2]], [[11,10]]] Output: [null,null,null,null,1,0,null,2]

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

pub struct DetectSquares {
  counts: HashMap<(i32, i32), i32>,
  by_x: HashMap<i32, Vec<i32>>,
}

impl DetectSquares {
  pub fn new() -> Self {
    DetectSquares {
      counts: HashMap::new(),
      by_x: HashMap::new(),
    }
  }

  pub fn add(&mut self, point: Vec<i32>) {
    let (x, y) = (point[0], point[1]);
    *self.counts.entry((x, y)).or_insert(0) += 1;
    self.by_x.entry(x).or_default().push(y);
  }

  pub fn count(&self, point: Vec<i32>) -> i32 {
    let (qx, qy) = (point[0], point[1]);
    let mut res = 0;
    if let Some(ys) = self.by_x.get(&qx) {
      for &y3 in ys {
        if y3 == qy { continue; }
        let side = (y3 - qy).abs();
        // Try both x directions
        for &x2 in &[qx + side, qx - side] {
          let c1 = *self.counts.get(&(x2, qy)).unwrap_or(&0);
          let c2 = *self.counts.get(&(x2, y3)).unwrap_or(&0);
          res += c1 * c2;
        }
      }
    }
    res
  }
}