LeetCode Notes: Heap

#23 Merge k Sorted Lists

We can use a priority queue to solve this problem. I used a default min heap and added all nodes from each linked list into the priority queue. Then, I built a new linked list by polling elements from the top of the queue to guarantee the sorted order.

• Time Complexity: O(n log n)
• Space Complexity: O(n)

public ListNode mergeKLists(ListNode[] lists) {
    Queue<Integer> queue = new PriorityQueue<>();
    for (ListNode list : lists) {
        while (list != null) {
            queue.add(list.val);
            list = list.next;
        }
    }

    if (queue.peek() == null) {
        return null;
    }

    ListNode head = new ListNode(queue.poll());
    ListNode current = head;
    while (queue.peek() != null) {
        current.next = new ListNode(queue.poll());
        current = current.next;
    }

    return head;
}

#973 K Closest Points to Origin

At first, I tried using a min heap and returned the first k points from the heap. However, I used this approach together with some other inefficient solutions, which resulted in a memory limited exceed error. After searching for some solutions, I found that using a max heap is more efficient.

Get chiang-sh’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

So I implemented a max heap using priority queue with a custom comparator based on the point’s distance from the origin. The heap maintains at most k elements. Whenever the heap size exceeds k, the max value should be removed. After processing all points, we have the k closest points to origin.

• Time Complexity: O(n log k)
• Space Complexity: O(k)

public int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> queue = new PriorityQueue<>(
            (p1, p2) -> Integer.compare(p2[0] * p2[0] + p2[1] * p2[1], p1[0] * p1[0] + p1[1] * p1[1]));

    for (int[] point : points) {
        queue.add(point);
        if (queue.size() > k) {
            queue.poll();
        }
    }

    int[][] result = new int[k][2];
    for (int i = 0; i < result.length; i++) {
        result[i] = queue.poll();
    }
    return result;
}