Skip to content

2249. Count Lattice Points Inside a Circle 👎

  • 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 += any_of(begin(circles), end(circles), [&](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))