2
\$\begingroup\$

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

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]]

(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

  • 1 <= K <= points.length <= 10000
  • -10000 < points[i][0] < 10000
  • -10000 < points[i][1] < 10000

Also note that there can be a situation where distance of 2 nodes are equal and hence can print any of the node.


Here is my approach.

  1. Took tree map (So that I get all sorted distance)
  2. Start filling tree map for all points
  3. Finally took first k element.
public class KClosestPointsToOrigin {

    public int[][] kClosest(int[][] points, int K) {

        int rows = points.length;


        SortedMap<Double, List<CoordinatePoint>> distanceToPoint = new TreeMap<>();

        for(int i =0; i<rows; i++) {
            double distance = getDistance(points[i]);
            if(Objects.nonNull(distanceToPoint.get(distance))) {
                List<CoordinatePoint> coordinatePointList = distanceToPoint.get(distance);
                coordinatePointList.add(new CoordinatePoint(points[i][0], points[i][1]));
            } else {
                List<CoordinatePoint> coordinatePoints = new ArrayList<>();
                coordinatePoints.add(new CoordinatePoint(points[i][0], points[i][1]));
                distanceToPoint.put(distance, coordinatePoints);// x and y coordinates.
            }
        }

        int[][] arrayToReturn = new int[K][2];
        int counter = 0;
        for (Double key : distanceToPoint.keySet()) {
            List<CoordinatePoint> coordinatePoints = distanceToPoint.get(key);
            Iterator iterator1 = coordinatePoints.iterator();
            while (iterator1.hasNext() && counter < K) {
                CoordinatePoint coordinatePoint = (CoordinatePoint) iterator1.next();
                arrayToReturn[counter][0] = coordinatePoint.x;
                arrayToReturn[counter][1] = coordinatePoint.y;
                counter++;
            }
        }

        return arrayToReturn;
    }

    private double getDistance(int[] point) {
        int x = point[0];
        int y = point[1];

        int x2 = Math.abs(x) * Math.abs(x);
        int y2 = Math.abs(y) * Math.abs(y);

        return Math.sqrt(x2+y2);
    }
}

class CoordinatePoint {
    int x;
    int y;

    public CoordinatePoint(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

However, this solution is not efficient as runtime and memory usage is high. Can you please help me to optimize the solution.

\$\endgroup\$
  • 1
    \$\begingroup\$ What do you mean by "runtime is high": is it longer than say \$\mathcal O(n\log n)\$? And did you measure the memory usage? You are guaranteed to get at most 10000 points, and I think memory usage is \$\mathcal O(n\log n)\$ as well. As long as there is nothing quadratic, I wouldn't be worried. \$\endgroup\$ – Roland Illig Apr 28 at 7:25
  • \$\begingroup\$ Since you know \$k\$ in advance, you only ever need to store the \$k\$ points that are closest to the origin. \$\endgroup\$ – Roland Illig Apr 28 at 7:27
  • \$\begingroup\$ @RolandIllig the leetcode submission shows Runtime: 75 ms Memory Usage: 68.3 MB, which is 15.44% of other solution. I want to improve on Runtime and memory usage. \$\endgroup\$ – Mosbius8 Apr 29 at 6:56
1
\$\begingroup\$

It would make more sense to store the distance with the point so that you don't have to calculate it each time.

class CoordinatePoint implements Comparable<CoordinatePoint> {

    int[] coordinates;
    int squaredDistance;

    private CoordinatePoint(int[] coordinates, int squaredDistance) {
        this.coordinates = coordinates;
        this.squaredDistance = squaredDistance;
    }

    public CoordinatePoint create(int[] coordinates) {
        int squaredDistance = coordinates[0] * coordinates[0] + coordinates[1] * coordinates[1];
        return new CoordinatePoint(coordinates, squaredDistance);
    }

    public int[] getCoordinates() {
        return coordinates;
    }

    @Override
    public int compareTo(CoordinatePoint coordinatePoint) {
         return -Integer.compareTo(this.squaredDistance, point.squaredDistance);
    }

}

I stored the squared distance because it compares the same as the distance but is easier to calculate.

The square of an integer (real numbers in general) is always positive, so taking the absolute value is unnecessary.

I implemented Comparable so that it could be used with a PriorityQueue without declaring a Comparator.

    Queue<CoordinatePoint> nearestPoints = new PriorityQueue<>(K);

    for (int[] point : points) {
        nearestPoints.add(CoordinatePoint.create(point));

        while (nearestPoints.size() > K) {
            nearestPoints.remove();
        }
    }

    int index = 0;
    int[][] results = new int[nearestPoints.size()][2];
    for (CoordinatePoint point : nearestPoints) {
        results[index] = point.getCoordinates();
        index++;
    }

    return results;

Defined this way, the PriorityQueue returns the largest distance. So what this does is it adds each point to the heap (which is how a PriorityQueue is stored). Then if there are too many points, it removes all but K of them. Then it just converts the heap to an array.

Using the PriorityQueue simplifies the logic. And this solution has a runtime complexity of \$\mathcal{O}(n\log k)\$ where \$n\$ is the number of points in the input and \$k\$ is the number to return. This is because for each element in the input, you insert it into a heap of at most \$k\$ elements. And heaps have logarithmic insertion complexity. Your original solution was \$\mathcal{O}(n\log n)\$ because it inserted all the elements into the set before removing only some of them.

But actually, I think that this problem is trying to get you to implement the heap yourself. The reason that I think that is that it would be quite possible to return an array organized as a heap. You'd lose the storage of the squared distance that way, so you'd have to calculate it each time. But you'd save storage space and the work of copying the results from intermediate storage.

The part about not caring about order strongly suggests using a heap, as that is one of the properties of a heap. It makes finding the smallest or largest element easy but does not store the elements in order after that.

I haven't tested this code, so be careful of compile errors, etc.

\$\endgroup\$
  • \$\begingroup\$ Wow.. never thought about using Priority Queue.Thanks @mdfst13. Yes can check as well on using custom heap as an array. May be it can save space. \$\endgroup\$ – Mosbius8 Apr 29 at 7:01
  • \$\begingroup\$ Using priority queue saved the running time from 75ms to 34ms. Almost half!!! However, the memory usage is still 68mb. I tried returning from priority queue as an array, using toArray method, but the compilation error happened. \$\endgroup\$ – Mosbius8 Apr 29 at 7:28
1
\$\begingroup\$

This task sounds as if it came directly from an advertisement for the Java 8 streams API:

  • Sort the points by their distance
  • Take the minimum k points

This boils down to the following code:

static int[][] kClosest(int[][] points, int k) {
    return Arrays.stream(points)
        .sorted(Comparator.comparing((int[] point) -> point[0] * point[0] + point[1] * point[1]))
        .limit(k)
        .toArray(int[][]::new);
}

That code is written from the top of my head. Since the Java streams API is general-purpose and intended to be highly optimized, it should notice that it only ever needs to remember the \$k\$ smallest elements. You should check this by counting how often the distance function is called. To do that you should extract it to a local method, which is something that your IDE can do for you.

Compared to your code:

  • I left out the Math.sqrt since the point coordinates are restricted to 10000, which means that the square of the distance can become at most 2e8, which luckily is a bit smaller than Integer.MAX_VALUE.
  • Calling Math.abs is unnecessary as well.
  • Making a map of lists may help in pathological cases when the given points all have the same distance. In other cases it can be left out.
\$\endgroup\$
  • \$\begingroup\$ Thanks @Roland I will check this out. In java 8, it is just 2 lines. \$\endgroup\$ – Mosbius8 Apr 29 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.