973.k-closest-points-to-origin.md

973. K Closest Points to Origin

Clarification Questions

• Is the answer unique?
• What answer order should I return?

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Heap

fun kClosest(points: Array<IntArray>, k: Int): Array<IntArray> {
    val maxHeap = PriorityQueue<IntArray>() { c1, c2 ->
        val d1 = distance(c1[0], c1[1])
        val d2 = distance(c2[0], c2[1])
        d2 - d1
    }
    for (i in 0 until points.size) {
        maxHeap.add(points[i])
        if (maxHeap.size > k) maxHeap.poll()
    }
    
    val size = maxHeap.size
    val results = Array<IntArray>(size) { IntArray(2) }
    for (i in 0 until size) {
        results[i] = maxHeap.poll()!!
    }
    return results
}

// We don't calculate the square because we want to use int type, not double for convenience.
private fun distance(x: Int, y: Int) = x * x + y * y

• Time Complexity: O(n lg k).
• Space Complexity: O(k).