Skip to main content

K Closest Points to Origin

Given a list of points, return the k closest points to the origin (0, 0).

Note: The distance between two points (x₁, y₁) and (x₂, y₂) is calculated as √[(x₂-x₁)² + (y₂-y₁)²]. For distance to origin, this simplifies to √(x² + y²).

Example(s)​

Example 1:

Input: points = [[1,1],[-2,-2]], k = 1
Output: [[1,1]]
Explanation:
Distance from origin:
- [1,1]: √(1² + 1²) = √2 ≈ 1.41
- [-2,-2]: √((-2)² + (-2)²) = √8 ≈ 2.83
The closest point is [1,1].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation:
Distance from origin:
- [3,3]: √(3² + 3²) = √18 ≈ 4.24
- [5,-1]: √(5² + (-1)²) = √26 ≈ 5.10
- [-2,4]: √((-2)² + 4²) = √20 ≈ 4.47
The 2 closest are [3,3] and [-2,4].

Example 3:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
Distance from origin:
- [1,3]: √(1² + 3²) = √10 ≈ 3.16
- [-2,2]: √((-2)² + 2²) = √8 ≈ 2.83
The closest point is [-2,2].

Solution​

The solution uses sorting by distance:

  1. Calculate distances: For each point, calculate distance squared (avoid sqrt for efficiency)
  2. Sort by distance: Sort points by their distance to origin
  3. Return top k: Return the first k points from the sorted list

JavaScript Solution - Sorting

/**
* Find k closest points to origin
* @param {number[][]} points - Array of [x, y] coordinates
* @param {number} k - Number of closest points to return
* @return {number[][]} - K closest points
*/
function kClosest(points, k) {
// Calculate distance squared for each point (avoid sqrt for efficiency)
// Distance² = x² + y²
const pointsWithDistance = points.map((point, index) => ({
  point,
  distanceSquared: point[0] * point[0] + point[1] * point[1],
  index
}));

// Sort by distance squared
pointsWithDistance.sort((a, b) => a.distanceSquared - b.distanceSquared);

// Return first k points
return pointsWithDistance.slice(0, k).map(item => item.point);
}

// Test cases
console.log('Example 1:', kClosest([[1,1],[-2,-2]], 1)); 
// [[1,1]]

console.log('Example 2:', kClosest([[3,3],[5,-1],[-2,4]], 2)); 
// [[3,3],[-2,4]]

console.log('Example 3:', kClosest([[1,3],[-2,2]], 1)); 
// [[-2,2]]

console.log('Test 4:', kClosest([[1,3],[-2,2],[2,-2]], 2)); 
// [[-2,2],[1,3]]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Max Heap)​

For better performance when k is much smaller than n, use a max heap:

/**
 * Max heap approach (better when k << n)
 */
function kClosestHeap(points, k) {
  // Max heap of size k (keep k smallest)
  const heap = [];
  
  for (const point of points) {
    const distanceSquared = point[0] * point[0] + point[1] * point[1];
    
    if (heap.length < k) {
      heap.push({ point, distance: distanceSquared });
      heapifyUp(heap, heap.length - 1);
    } else {
      // If current point is closer than farthest in heap
      if (distanceSquared < heap[0].distance) {
        heap[0] = { point, distance: distanceSquared };
        heapifyDown(heap, 0);
      }
    }
  }
  
  return heap.map(item => item.point);
}

// Helper functions for max heap
function heapifyUp(heap, index) {
  while (index > 0) {
    const parent = Math.floor((index - 1) / 2);
    if (heap[parent].distance >= heap[index].distance) break;
    [heap[parent], heap[index]] = [heap[index], heap[parent]];
    index = parent;
  }
}

function heapifyDown(heap, index) {
  while (true) {
    let largest = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    
    if (left < heap.length && heap[left].distance > heap[largest].distance) {
      largest = left;
    }
    if (right < heap.length && heap[right].distance > heap[largest].distance) {
      largest = right;
    }
    if (largest === index) break;
    [heap[index], heap[largest]] = [heap[largest], heap[index]];
    index = largest;
  }
}

Alternative: Quickselect​

For optimal average-case performance, use quickselect:

/**
 * Quickselect approach (O(n) average time)
 */
function kClosestQuickselect(points, k) {
  function distanceSquared(point) {
    return point[0] * point[0] + point[1] * point[1];
  }
  
  function quickselect(left, right, k) {
    if (left === right) return;
    
    const pivotIndex = partition(left, right);
    
    if (pivotIndex === k) {
      return;
    } else if (pivotIndex < k) {
      quickselect(pivotIndex + 1, right, k);
    } else {
      quickselect(left, pivotIndex - 1, k);
    }
  }
  
  function partition(left, right) {
    const pivotDistance = distanceSquared(points[right]);
    let i = left;
    
    for (let j = left; j < right; j++) {
      if (distanceSquared(points[j]) <= pivotDistance) {
        [points[i], points[j]] = [points[j], points[i]];
        i++;
      }
    }
    [points[i], points[right]] = [points[right], points[i]];
    return i;
  }
  
  quickselect(0, points.length - 1, k);
  return points.slice(0, k);
}

Complexity​

  • Time Complexity:
    • Sorting: O(n log n) - Where n is the number of points
    • Max Heap: O(n log k) - Better when k << n
    • Quickselect: O(n) average, O(n²) worst case
  • Space Complexity:
    • Sorting: O(1) or O(n) depending on sorting algorithm
    • Max Heap: O(k) - For the heap
    • Quickselect: O(1) - In-place partitioning

Approach​

The solution uses sorting by distance:

  1. Calculate distance squared:

    • For each point [x, y], calculate x² + y²
    • Use squared distance to avoid expensive sqrt operation
    • Squared distance preserves ordering (if a² < b², then a < b)

  2. Sort points:

    • Sort points by their distance squared to origin
    • Closest points will be first

  3. Return top k:

    • Return the first k points from sorted list

Key Insights​

  • Distance squared: Use x² + y² instead of √(x² + y²) to avoid sqrt
  • Squared preserves order: If a² < b², then a < b (for positive values)
  • Sorting is simple: O(n log n) but easy to implement
  • Heap optimization: Better when k is much smaller than n
  • Quickselect: Optimal average case but more complex

Step-by-Step Example​

Let's trace through Example 1: points = [[1,1],[-2,-2]], k = 1

Step 1: Calculate distance squared
  Point [1,1]:
    distance² = 1² + 1² = 1 + 1 = 2
  
  Point [-2,-2]:
    distance² = (-2)² + (-2)² = 4 + 4 = 8

Step 2: Sort by distance squared
  [1,1] has distance² = 2
  [-2,-2] has distance² = 8
  Sorted: [[1,1], [-2,-2]]

Step 3: Return first k = 1
  Result: [[1,1]]

Visual Representation​

Example 1: points = [[1,1],[-2,-2]], k = 1

Points on coordinate plane:
        |
        |  [1,1] (distance = √2)
        |
--------+--------
        |
        |        [-2,-2] (distance = √8)
        |

Distance squared:
  [1,1]: 2
  [-2,-2]: 8

Sorted: [1,1] (closest)
Result: [[1,1]]

Edge Cases​

  • k equals array length: Return all points
  • k = 1: Return the single closest point
  • Points at same distance: Any of them can be returned
  • Negative coordinates: Works correctly (squared is always positive)
  • Origin point: [0,0] has distance 0 (closest)

Important Notes​

  • Distance squared: Use x² + y² instead of √(x² + y²) for efficiency
  • Ordering preserved: Squared distance preserves relative order
  • No sqrt needed: Avoids floating-point operations
  • Stable sort: If distances are equal, order may vary
  • In-place vs new array: Can modify input or return new array

Optimization: Distance Squared​

Why use distance squared?

  • √(x² + y²) is expensive (square root operation)
  • x² + y² preserves ordering (if a² < b², then a < b for a, b > 0)
  • No need for actual distance, only relative ordering matters

Comparison of Approaches​

ApproachTimeSpaceBest For
SortingO(n log n)O(1)General purpose, simple
Max HeapO(n log k)O(k)When k << n
QuickselectO(n) avgO(1)When k is close to n/2
  • Kth Largest Element: Find kth largest element
  • Top K Frequent Elements: Different selection problem
  • Merge K Sorted Lists: Different problem
  • Closest Pair of Points: Different geometric problem

Takeaways​

  • Distance squared avoids expensive sqrt operation
  • Sorting is simple and works well
  • Heap optimization is better when k is small
  • Quickselect provides optimal average case
  • O(n log n) is acceptable for most cases