Amazon

Leetcode 146 LRU Cache

Leetcode 403 Frog Jump

K closest points

Find the K closest points to the origin in a 2D plane, given an array containing N points.

 Method1, use a priority queue. Because it takes constant time to retrieve the smallest one always.

/*
public class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
*/
 
public List<Point> findKClosest(Point[] p, int k) {
    PriorityQueue<Point> pq = new PriorityQueue<>(10, new Comparator<Point>() {
        @Override
        public int compare(Point a, Point b) {
            return (b.x * b.x + b.y * b.y) - (a.x * a.x + a.y * a.y);
        }
    });
     
    for (int i = 0; i < p.length; i++) {
        if (i < k)
            pq.offer(p[i]);
        else {
            Point temp = pq.peek();
            if ((p[i].x * p[i].x + p[i].y * p[i].y) - (temp.x * temp.x + temp.y * temp.y) < 0) {
                pq.poll();
                pq.offer(p[i]);
            }
        }
    }
     
    List<Point> x = new ArrayList<>();
    while (!pq.isEmpty())
        x.add(pq.poll());
     
    return x;
}

Max points on a line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

public int maxPoints(Point[] points) {
    if(points == null || points.length == 0) return 0;
 
    HashMap<Double, Integer> result = new HashMap<Double, Integer>();
    int max=0;
 
    for(int i=0; i<points.length; i++){
        int duplicate = 1;//
        int vertical = 0;
        for(int j=i+1; j < points.length; j++){
            //handle duplicates and vertical
            if(points[i].x == points[j].x){
                if(points[i].y == points[j].y){
                    duplicate++;
                }else{
                    vertical++;
                }
            }else{
                double slope = points[j].y == points[i].y ? 0.0
            : (1.0 * (points[j].y - points[i].y))
      / (points[j].x - points[i].x);
 
                if(result.get(slope) != null){
                    result.put(slope, result.get(slope) + 1);
                }else{
                    result.put(slope, 1);
                }
            }
        }
 
        for(Integer count: result.values()){
            if(count+duplicate > max){
                max = count+duplicate;
            }
        }
 
        max = Math.max(vertical + duplicate, max);
        result.clear();
    }
 
 
    return max;
}