Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
How would you modify the solution if the input was an infinite streak of points? Time/Space Constraints Considerations: Try to seek different uses of O(N) space to solve this problem!
Run through a set of example cases:
HAPPY CASE
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
EDGE CASE
Input: [[1,1], [1,1], [1,1], [0,0]], k = 2
Output: [[0,0], [1,1]]Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: According to the distance of the point from the origin, use a priority queue to store the coordinates of the point in a priority queue of pairs. To assign the maximum priority to the least distant point from the origin, we use the Comparator class in Priority Queue. Next, we can print the first K elements of the priority queue.
1. Place the points into a PriorityQueue
2. Whenever the size reach K + 1, poll the farthest point out
3. Then for each point, we add it to the heap.
4. If the heap top is far from the origin compared to the incoming point then add the incoming point in the heap and remove the earlier top.⚠️ Common Mistakes
Implement the code to solve the algorithm.
import heapq
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = [] # out heap
output = [] # output array since we can't return heap directly + don't want to modify the points array
# loop through the points array
for cord in points:
# calculate the distance from 0 - current point
distance = ((cord[0] - 0) ** 2) + ((cord[1] - 0) ** 2)
# make a tuple, where tuple[0] is the distance negated, and tuple[1] is the current point we're on eg. (-8, [-2, 2])
# note that heapq will keep the heap property of tuples using the first index.
'''
we negate the distance because python's built in heap is by default a min heap.
we also want to be able to utilize heapq.heappushpop, and heapq.heappush, which doesn't exist for
the builtin max heap implementation.
'''
distance_tuple = (-distance, cord)
if len(heap) == k:
# check if we've reached our heap's max size, which is k.
# if so, we push the current tuple and pop the smallest item.
# since values are negated, the smallest item ends up being the largest item
heapq.heappushpop(heap, distance_tuple)
else:
# simply push on to the heap if we haven't exceeded size k
heapq.heappush(heap, distance_tuple)
# add points arrays from the tuples in the heaps to our output to get desired answer
for item in heap:
output.append(item[1])
return outputclass Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));
// loop in the rows of the 2Darray called points
for(int[] point : points) {
// add a row to the max heap
maxHeap.add(point);
// if the size of the max heap becomes more than k then remove a row from it
if(maxHeap.size() > k)
maxHeap.remove();
}
int[][] res = new int[k][2];
while(k-- > 0) {
// the last element in the heap is the kth closest element to the origin so put it in the kth row of res
res[k] = maxHeap.remove();
}
return res;
}
}Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
