MediumNo. 2857
Count Pairs of Points With Distance k — LeetCode 2857 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Array, Hash Table
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [xi, yi] are the coordinates of the ith point in a 2D plane. We define the distance between two points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2) where XOR is the bitwise XOR operation.
Example
- Input
- coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
- Output
- 2
- Explanation
- We can choose the following pairs:
Python solution
class Solution:
def countPairs(self, coordinates: List[List[int]], k: int) -> int:
cnt = Counter()
ans = 0
for x2, y2 in coordinates:
for a in range(k + 1):
b = k - a
x1, y1 = a ^ x2, b ^ y2
ans += cnt[(x1, y1)]
cnt[(x2, y2)] += 1
return ansComplexity
- Time
- O(n × k)
- Space · auxiliary
- O(n)
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2857. Count Pairs of Points With Distance k is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0268 | Missing Number | Easy |
| 0421 | Maximum XOR of Two Numbers in an Array | Medium |
| 0491 | Non-decreasing Subsequences | Medium |
| 0645 | Set Mismatch | Easy |
| 0691 | Stickers to Spell Word | Hard |
| 0982 | Triples with Bitwise AND Equal To Zero | Hard |
Frequently asked questions
- How hard is LeetCode 2857. Count Pairs of Points With Distance k?
LeetCode 2857. Count Pairs of Points With Distance k is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2857. Count Pairs of Points With Distance k?
The Python solution on this page runs in O(n × k).
- What is the space complexity of LeetCode 2857. Count Pairs of Points With Distance k?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2857. Count Pairs of Points With Distance k cover?
LeetCode 2857. Count Pairs of Points With Distance k is tagged Bit Manipulation, Array and Hash Table on LeetCode.