K Closest Points to Origin - Practice Coding Problems

K Closest Points to Origin - Problem

Array Math Divide and Conquer Geometry Sorting Heap (Priority Queue) Quickselect Medium

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)² + (y1 - y2)²).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Input & Output

Example 1 — Basic Case

$ Input: points = [[1,1],[3,3],[1,3]], k = 2

› Output: [[1,1],[1,3]]

💡 Note: Distance from origin: [1,1] has distance √2, [3,3] has distance √18, [1,3] has distance √10. The 2 closest are [1,1] and [1,3].

Example 2 — Larger Input

$ Input: points = [[3,3],[5,-1],[-2,4]], k = 2

› Output: [[-2,4],[3,3]]

💡 Note: Distances: [3,3] → √18, [5,-1] → √26, [-2,4] → √20. The 2 closest are [-2,4] and [3,3].

Example 3 — Single Point

$ Input: points = [[0,1]], k = 1

› Output: [[0,1]]

💡 Note: Only one point exists, so it must be the closest.

Constraints

1 ≤ k ≤ points.length ≤ 10⁴
-10⁴ ≤ xi, yi ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Points

Points plotted on coordinate plane with origin

Calculate Distances

Compute Euclidean distance from each point to origin

Select K Closest

Return the k points with smallest distances

Key Takeaway

🎯 Key Insight: Use squared distances to avoid expensive square root calculations, and choose the right algorithm based on input size and k value.

Asked in

a Amazon 68 f Facebook 45 G Google 32 M Microsoft 28

The key insight is that we don't need to sort all points - just find the k closest ones. Optimal approach uses quickselect for O(n) average time, while sorting takes O(n log n) and max heap takes O(n log k). Time: O(n), Space: O(log n)

Common Approaches

Approach	Time	Space	Notes
✓ Max Heap Approach	O(n log k)	O(k)	Use max heap to maintain k closest points during single pass
Quickselect (Optimal)	O(n)	O(log n)	Use quickselect to partition around kth closest point in O(n) average time
Sort All Points	O(n log n)	O(1)	Calculate all distances, sort by distance, return first k points

Max Heap Approach — Algorithm Steps

Initialize max heap with first k points
For remaining points, compare with heap top
Replace heap top if current point is closer
Return all points in heap

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Points

Add points to heap up to size k

Compare & Replace

Replace farthest point if current is closer

Extract Result

All points in heap are k closest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* point;
    int dist;
} HeapNode;

int compare(const void* a, const void* b) {
    HeapNode* nodeA = (HeapNode*)a;
    HeapNode* nodeB = (HeapNode*)b;
    return nodeB->dist - nodeA->dist; // Max heap
}

int** solution(int** points, int pointsSize, int* pointsColSize, int k, int* returnSize, int** returnColumnSizes) {
    HeapNode* heap = (HeapNode*)malloc(k * sizeof(HeapNode));
    int heapSize = 0;
    
    for (int i = 0; i < pointsSize; i++) {
        int dist = points[i][0]*points[i][0] + points[i][1]*points[i][1];
        
        if (heapSize < k) {
            heap[heapSize].point = points[i];
            heap[heapSize].dist = dist;
            heapSize++;
            qsort(heap, heapSize, sizeof(HeapNode), compare);
        } else if (dist < heap[0].dist) {
            heap[0].point = points[i];
            heap[0].dist = dist;
            qsort(heap, k, sizeof(HeapNode), compare);
        }
    }
    
    *returnSize = k;
    *returnColumnSizes = (int*)malloc(k * sizeof(int));
    int** result = (int**)malloc(k * sizeof(int*));
    
    for (int i = 0; i < k; i++) {
        (*returnColumnSizes)[i] = 2;
        result[i] = (int*)malloc(2 * sizeof(int));
        result[i][0] = heap[i].point[0];
        result[i][1] = heap[i].point[1];
    }
    
    free(heap);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int** points = (int**)malloc(100 * sizeof(int*));
    int pointsSize = 0;
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(points, pointsSize, NULL, k, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log k)

Process n points, each heap operation takes O(log k)

⚡ Linearithmic

Space Complexity

O(k)

Heap stores at most k points

✓ Linear Space

125.0K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Max Heap Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler