K Closest Points To Origin

Question

Two bar problem

find best area among ....

""" Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., sqrt((x1 - x2)^2 + (y1 - y2)^2)).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

================================================= Example 1:

Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

================================================= Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints:

1 <= k <= points.length <= 10^4 -10^4 < xi, yi < 10^4

"""

Solution

Full

heap/K Closest Points to Origin.py

import math
import heapq


def find_closest_points(arr, k):
    h = []

    for a in arr:
        v = math.sqrt(a[0] ** 2 + a[1] ** 2)

        #print(v)

        heapq.heappush(h, (v, a))

    ret = []

    for i in range(k):
        v, a = heapq.heappop(h)
        ret.append(a)

    return ret


result = find_closest_points([[1, 3], [-2, 2]], 1)
# print(find_closest_points([[3, 3], [5, -1], [-2, 4]], 2))

#print(result)

Step	v
1	3.1622776601683795
2	2.8284271247461903

result
[[-2, 2]]

Simple

heap/K Closest Points to Origin.py

import math
import heapq


def find_closest_points(arr, k):
    h = []

    for a in arr:
        v = math.sqrt(a[0] ** 2 + a[1] ** 2)

        #print(v)

        heapq.heappush(h, (v, a))

    ret = []

    for i in range(k):
        v, a = heapq.heappop(h)
        ret.append(a)

    return ret


result = find_closest_points([[1, 3], [-2, 2]], 1)
# print(find_closest_points([[3, 3], [5, -1], [-2, 4]], 2))

#print(result)

Step	v
1	3.1622776601683795
2	2.8284271247461903

result
[[-2, 2]]