Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

'K' Closest Points to the Origin (easy)

Problem Statement

Given an array of points in a 2D plane, find ‘K’ closest points to the origin.

Example 1:

Input: points = [[1,2],[1,3]], K = 1
Output: [[1,2]]
Explanation: The Euclidean distance between (1, 2) and the origin is sqrt(5).
The Euclidean distance between (1, 3) and the origin is sqrt(10).
Since sqrt(5) < sqrt(10), therefore (1, 2) is closer to the origin.

Example 2:

Input: point = [[1, 3], [3, 4], [2, -1]], K = 2
Output: [[1, 3], [2, -1]]

Constraints:

  • 1 <= k <= points.length <= 10<sup>4</sup>

.....

.....

.....

Like the course? Get enrolled and start learning!
H

hjalmar.basile

· 2 years ago

There is a test case failing with this error, but actually my output is correct as well. The validator is hardcoding a specific output, but there can be more than one, depending on ordering or entries with same distance from the origin. Please fix this.

WrongAnswer Your Input[[0,0],[1,1],[-1,-1],[2,2]] 2

Output[[-1,-1],[0,0]] Expected[[0,0],[1,1]]

K

k

· 3 years ago

  1. Generally def _ _ lt _ _(self, other) is used for "Less than". However, in definition it has used ">" sign (Which is used for Greater than)
  2. How will maxHeap will work? since we are pushing object of class Point. How will heap sort it?
Show 1 reply
D

design-gurus

· 5 months ago

Python has a bug. The question shows the lt being overwritten, but it either isn't or isn't overwritten how it's shown. Note here we want the lt logic to be wonky by using greater than, so the the heap sorting logic will work easily.

#  def __lt__(self, other):
#    return self.distance_from_origin() > other.distance_from_origin()
D

Derek Yu

· 4 years ago

How does just pushing ' points[i]' let the heap know how to maintain the furthest distance in the heap?

Show 3 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

Why not

 def findClosestPoints(self, points, k):
    result = []

    min_heap = []
    for point in points:
      heappush(min_heap, (point.distance_from_origin(), point))
      
    for i in range(k):
      tup = heappop(min_heap)
      result.append([tup[1].x, tup[1].y])
      
    return result
Show 1 reply
Dmytro Bibik

Dmytro Bibik

· a year ago

Less operator for Point class has mistake, it should be const instead of return const value

bool operator<(const Point& p) const { return p.distFromOrigin() > this->distFromOrigin(); }

instead of

const bool operator<(const Point& p) { return p.distFromOrigin() > this->distFromOrigin(); }