CareerCup

We can keep a max heap of size k where we check each incoming element vs the top and if it's smaller we replace it. After we've gone through the list of N points we pop our heap into a list and reverse that list. Running time O(N*log(K)) extra space O(K).

List<Point> findClosestToOrigin(List<Point> points, int numToFind) {
    PriorityQueue<Point> closestPoints = new PriorityQueue<>(Collections.reverseOrder());
    for (Point point : points) {
      if (closestPoints.size() < numToFind) {
        closestPoints.add(point);
      } else if (point.compareTo(closestPoints.peek()) < 0) {
        closestPoints.poll();
        closestPoints.add(point);
      }
    }
    List<Point> closeList = new ArrayList<>();
    while (!closestPoints.isEmpty()) {
      closeList.add(closestPoints.poll());
    }
    Collections.reverse(closeList);
    return closeList;
  }

  class Point implements Comparable {
    double x, y;

    double distanceFromOrigin() {
      return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
    }

    @Override
    public int compareTo(Object other) {
      if (!(other instanceof Point)) {
        throw new IllegalArgumentException("Points can only be compared with other points.");
      }
      double diff = (distanceFromOrigin() - ((Point) other).distanceFromOrigin());
      if (diff == 0) {
        return 0;
      } else {
        return diff > 0 ? 1 : -1;
      }
    }
  }

Running time should be O(nlogk) as O(nlogk) + O(n) ~ O(nlogk) of the above code

Yep, I had edited it but CC takes a couple of hours to post edits haha. Thanks though!

1) it is finding the k-thary element and return it and all that are smaller
2) A modified quick-sort partition method will do it in O(n)
3) I did it in place of the original array/vector for simplicity

#include <iostream>
#include <vector>

using namespace std;

struct Point
{
	int x; int y;
	Point(int ax, int ay) : x(ax), y(ay) {}
	int get_DistSq() { return x*x + y*y; }	
};
ostream& operator << (ostream& os, Point& p) { return os << "{" << p.x << "," << p.y << "("  << p.get_DistSq() << ")" << "}"; }

// quick-sorts partition function, returns k
// partitions array [s..e] into [s..k][k+1..e] where every element in [s..k] < than every element in [k+1..e]
int Partition(int s, int e, vector<Point>& pts)
{
	int p = (s + e) / 2; // pick pivot element, improvement: randomize or at least check overflow
	swap(pts[p], pts[e]); // swap pivot with end element

	int i = s-1; // all in [s..i] <= p < all in [i+1..j] 
	int pv = pts[e].get_DistSq();
	for (int j = s; j < e; ++j)
	{
		if (pts[j].get_DistSq() <= pv)
		{ 
			i++;
			swap(pts[i], pts[j]);
		} 
	}

	swap(pts[i+1], pts[e]);
	return i+1;
}

// changes the vector to contain the k-smallest elements at position 0..k
// smallest in this contect is the distance of the points to {0,0}
void Find(vector<Point>& pts, int k)
{
	int s = 0; 
	int e = pts.size()-1;
	int m = 0;
	do
	{
		m = Partition(s, e, pts);
		if (m < k) s = m + 1; // on the left of m are not enough elements
		if (m > k) e = m - 1; // on the left of m are too many elements
	} while (m != k);
}

int main()
{		
	int k = 2;
	auto pts = vector<Point>{ Point(1,2), Point(2,2), Point(5,3), Point(4,2), Point(3,2), Point(2,0), Point(1,1), Point(2,1), Point(9,9) };

	cout << "all points:" << endl;
	for (int i = 0; i < pts.size(); i++) cout << pts[i] << " ";

	Find(pts, k);

	cout << endl << endl << k << " smallest point(s):" << endl;
	for (int i = 0; i < k; i++) cout << pts[i] << " ";

	getchar();
}

#run time O(nlogn), space O(1)
def closest_point(origin, points, k):

    def compare(p1, p2):
        return ((p1[0] - origin[0])**2 + (p1[1] - origin[1])**2) - ((p2[0] - origin[0])**2 + (p2[1] - origin[1])**2)

    def compare1(p1, p2):
        return (p1[0]**2 + p1[1]**2) - (p2[0]**2 + p2[1]**2)

    points = sorted(points, cmp=compare1)
    return points[:k]


points = [(0, 0), (1, 1), (1, 0), (2, 1), (2, 2), (1, 2), (0, 1)]
print closest_point((0, 0), points, 3)

Two methods are shown here to find:
1. To do the quick sort comparator, based on the distance to origin.
2. To use the heap of size K.

#run time O(nlogn), space O(1)
import heapq

def closest_point(origin, points, k):

    def compare(p1, p2):
        return ((p1[0] - origin[0])**2 + (p1[1] - origin[1])**2) - ((p2[0] - origin[0])**2 + (p2[1] - origin[1])**2)

    def compare1(p1, p2):
        return (p1[0]**2 + p1[1]**2) - (p2[0]**2 + p2[1]**2)

    points = sorted(points, cmp=compare1)
    return points[:k]


points = [(0, 0), (1, 1), (1, 0), (2, 1), (2, 2), (1, 2), (0, 1)]
print closest_point((0, 0), points, 3)

#time: nlogk; space O(k)
def closest_point_heap(origin, points, k):
    hp = []

    for i in xrange(len(points)):
        x, y = points[i]
        dis = -(x**2 + y**2)

        if len(hp) < k:
            heapq.heappush(hp, (dis, x, y))
        else:
            mxdis, xx, yy = heapq.heappop(hp)
            if mxdis < dis:
                heapq.heappush(hp, (dis, x, y))
            else:
                heapq.heappush(hp, (mxdis, xx, yy))

    for p in hp:
        print p[1], p[2]


closest_point_heap((0, 0), points, 4)