MediumNo. 1828
Queries on Number of Points Inside a Circle — LeetCode 1828 Python Solution
- Pattern
- Math and Number Theory
- Topics
- Geometry, Array, Math
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an array points where points[i] = [xi, yi] is the coordinates of the ith point on a 2D plane. Multiple points can have the same coordinates.
Example
- Input
- points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
- Output
- [3,2,2]
- Explanation
- The points and circles are shown above.
Python solution
class Solution:
def countPoints(
self, points: List[List[int]], queries: List[List[int]]
) -> List[int]:
ans = []
for x, y, r in queries:
cnt = 0
for i, j in points:
dx, dy = i - x, j - y
cnt += dx * dx + dy * dy <= r * r
ans.append(cnt)
return ansComplexity
- Time
- O(m × n)where m and n are the lengths of the arrays `queries` and `points` respectively
- Space · auxiliary
- O(1)
Pattern: Math and Number Theory
Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1828. Queries on Number of Points Inside a Circle is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math and Geometry.
The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0335 | Self Crossing | Hard |
| 0587 | Erect the Fence | Hard |
| 0812 | Largest Triangle Area | Easy |
| 0883 | Projection Area of 3D Shapes | Easy |
| 0892 | Surface Area of 3D Shapes | Easy |
| 1037 | Valid Boomerang | Easy |
Frequently asked questions
- How hard is LeetCode 1828. Queries on Number of Points Inside a Circle?
LeetCode 1828. Queries on Number of Points Inside a Circle is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1828. Queries on Number of Points Inside a Circle?
The Python solution on this page runs in O(m × n), where m and n are the lengths of the arrays `queries` and `points` respectively.
- What is the space complexity of LeetCode 1828. Queries on Number of Points Inside a Circle?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1828. Queries on Number of Points Inside a Circle cover?
LeetCode 1828. Queries on Number of Points Inside a Circle is tagged Geometry, Array and Math on LeetCode.