K Closest Points to Origin

To solve this medium LC problem, you must first define a function to calculate the Euclidian distance of two points. In this case, we have to find the distance between a point and the origin (0, 0).

The Euclidian distance formula is defined as

d(p1, p2) = √(|p2.x-p1.x|2 + |p2.y-p1.y|2)

Since we are measuring from the origin (0,0), we can simplify the equation to:

d(p1, p2) = √(p2.x2 + p2.y2)

Now, for every point in the array, we calculate the distance and use a TreeMap to store the distances as the key and the points as the value.

The last line loops through all the entries of our map and flattens it to a single list. We can then use the operator take() to limit the result into K number of items and finally convert the result into Array of IntArray.

import java.util.*;
class Solution {
    fun kClosest(points: Array<IntArray>, K: Int): Array<IntArray> {
        val distance : (IntArray) -> Double = {
            Math.sqrt(Math.pow(it[0].toDouble(), 2.0) + Math.pow(it[1].toDouble(), 2.0))
        }
        
        var distanceMap = TreeMap<Double, ArrayList<IntArray>>()
    
        points.forEach { 
            val d = distance(it)
            if(!distanceMap.containsKey(d)){
                distanceMap.put(d, ArrayList<IntArray>())
            }
            
            distanceMap[d]?.add(it)
        }
        
        return distanceMap.flatMap { it.value }.take(K).toTypedArray()
    }
}
Runtime: 604 ms, faster than 54.65% of Kotlin online submissions for K Closest Points to Origin.
Memory Usage: 61.5 MB, less than 100.00% of Kotlin online submissions for K Closest Points to Origin.
comments powered by Disqus