Skip to content

2249. Count Lattice Points Inside a Circle

Approach 1: Math

  • Time: $O(200^2n) = O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int countLatticePoints(vector<vector<int>>& circles) {
    int ans = 0;

    for (int x = 0; x < 201; ++x)
      for (int y = 0; y < 201; ++y)
        ans += ranges::any_of(circles, [x, y](const auto& c) {
          return (c[0] - x) * (c[0] - x) + (c[1] - y) * (c[1] - y) <=
                 c[2] * c[2];
        });

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int countLatticePoints(int[][] circles) {
    int ans = 0;

    for (int x = 0; x < 201; ++x)
      for (int y = 0; y < 201; ++y)
        for (int[] c : circles)
          if ((c[0] - x) * (c[0] - x) + (c[1] - y) * (c[1] - y) <= c[2] * c[2]) {
            ++ans;
            break;
          }

    return ans;
  }
}

1
2
3
4
5
class Solution:
  def countLatticePoints(self, circles: list[list[int]]) -> int:
    return sum(any((xc - x)**2 + (yc - y)**2 <= r**2 for xc, yc, r in circles)
               for x in range(201)
               for y in range(201))

Approach 2: Set

  • Time: $O(n\log n \cdot r^2)$ (C++), $O(nr^2) = O(n)$ (Java/Python)
  • Space: $O(nr^2) = O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int countLatticePoints(vector<vector<int>>& circles) {
    set<pair<int, int>> points;

    // dx := relative to x
    // dy := relative to y
    // So, dx^2 + dy^2 = r^2.
    for (const vector<int>& c : circles) {
      const int x = c[0];
      const int y = c[1];
      const int r = c[2];
      for (int dx = -r; dx <= r; ++dx) {
        const int yMax = sqrt(r * r - dx * dx);
        for (int dy = -yMax; dy <= yMax; ++dy)
          points.emplace(x + dx, y + dy);
      }
    }

    return points.size();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int countLatticePoints(int[][] circles) {
    Set<Pair<Integer, Integer>> points = new HashSet<>();

    // dx := relative to x
    // dy := relative to y
    // So, dx^2 + dy^2 = r^2.
    for (int[] c : circles) {
      final int x = c[0];
      final int y = c[1];
      final int r = c[2];
      for (int dx = -r; dx <= r; ++dx) {
        final int yMax = (int) Math.sqrt(r * r - dx * dx);
        for (int dy = -yMax; dy <= yMax; ++dy)
          points.add(new Pair<>(x + dx, y + dy));
      }
    }

    return points.size();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def countLatticePoints(self, circles: list[list[int]]) -> int:
    points = set()

    # dx := relative to x
    # dy := relative to y
    # So, dx^2 + dy^2 = r^2.
    for x, y, r in circles:
      for dx in range(-r, r + 1):
        yMax = int((r**2 - dx**2)**0.5)
        for dy in range(-yMax, yMax + 1):
          points.add((x + dx, y + dy))

    return len(points)