Скачать или смотреть Daily LeetCode (Day 3) - LC973 K Closest Points to Origin

AI Summary:
The speaker tackles LeetCode 973 – K Closest Points to Origin, first sketching a max-heap + hashmap design to associate distances with points. They wrestle with min-heap vs max-heap, negative distances, and awkward retrieval from the map, then realize the approach is clunky and get tangled on time-complexity. After checking a standard reference (“Niko”/NeetCode-style), they learn Python’s heapq can store tuples/lists and compares by the first element, so you can push (distance, x, y) and skip the hashmap—and you don’t need a square root. They conclude with the canonical size-k heap solution using squared distance for O(n log k) time and O(k) space, noting it’s cleaner than their first attempt.

Additional Notes:
I was able to solve it initially without any hints or videos. However, I found that my solution was not optimal with a time efficiency of O(nlogn). Looking at the solution, I learnt that a heap is more powerful than I thought. I thought it could only store a number as its value which was why I created the hashMap to correspond the distance to the coordinates. HOWEVER, a heap can store, the distance as well as the corresponding coordinates together, and the heap will use the value in the first index for comparison.

This completely invalidates the need for a hashMap and I can immediately start pushing to the maxHeap right as I calculate the distance. I also need to remember that I don't always need to initialize a heap with heapify, I can just start using heappush one by one if the problem requires it. To make it a bit cleaner, you can also break down the coordinates into for x, y in points instead of for point in points. Ah, and I also shouldn't forget how to square root a value or how to use the exponent operator in python.

Tags:
#heap #leetcode_medium #python