K-th Nearest Obstacle Queries

K-th Nearest Obstacle Queries - Problem

There is an infinite 2D plane. You are given a positive integer k. You are also given a 2D array queries, which contains the following queries:

queries[i] = [x, y]: Build an obstacle at coordinate (x, y) in the plane. It is guaranteed that there is no obstacle at this coordinate when this query is made.

After each query, you need to find the distance of the k-th nearest obstacle from the origin.

Return an integer array results where results[i] denotes the k-th nearest obstacle after query i, or results[i] == -1 if there are less than k obstacles.

Note that initially there are no obstacles anywhere.

The distance of an obstacle at coordinate (x, y) from the origin is given by |x| + |y|.

Input & Output

Example 1 — Basic Queries

$ Input: queries = [[1,2],[3,4],[2,3]], k = 3

› Output: [-1,-1,7]

💡 Note: After 1st query: only 1 obstacle (distance 3), need 3 → -1. After 2nd query: only 2 obstacles (distances 3,7), need 3 → -1. After 3rd query: 3 obstacles (distances 3,5,7), 3rd nearest → 7.

Example 2 — Small K

$ Input: queries = [[5,5],[4,4],[3,3]], k = 1

› Output: [10,8,6]

💡 Note: k=1 means we want nearest obstacle each time. After [5,5]: nearest is 10. After [4,4]: nearest is 8. After [3,3]: nearest is 6.

Example 3 — Equal Distances

$ Input: queries = [[1,0],[0,3],[2,2]], k = 2

› Output: [-1,3,3]

💡 Note: After [1,0]: distance 1, only 1 obstacle → -1. After [0,3]: distances [1,3], 2nd nearest is 3. After [2,2]: distances [1,3,4], 2nd nearest is 3.

Constraints

1 ≤ queries.length ≤ 2 × 10⁴
1 ≤ k ≤ queries.length
queries[i].length == 2
-10⁴ ≤ queries[i][0], queries[i][1] ≤ 10⁴

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18

The key insight is using a max heap to efficiently maintain the k nearest obstacles. The optimal approach uses a max heap of size k - when adding a new distance, if heap size exceeds k, remove the maximum. The heap root always contains the k-th nearest distance. Time: O(n log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Max Heap - Maintain K Nearest	O(n log k)	O(k)	Use max heap to keep only k smallest distances efficiently
Brute Force - Sort After Each Query	O(n² log n)	O(n)	Store all distances and sort to find k-th nearest after each query

Max Heap - Maintain K Nearest — Algorithm Steps

Calculate Manhattan distance for new obstacle
Add distance to max heap
If heap size > k, remove maximum element
Return heap root (k-th nearest) if heap has k elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Distance

Insert Manhattan distance into max heap

Maintain Size

If heap size > k, remove maximum

Get K-th

Heap root is k-th nearest distance

Code -

solution.c — C

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

typedef struct {
    int* data;
    int size;
    int capacity;
} MaxHeap;

MaxHeap* createHeap(int capacity) {
    MaxHeap* heap = (MaxHeap*)malloc(sizeof(MaxHeap));
    heap->data = (int*)malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(MaxHeap* heap, int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap->data[parent] >= heap->data[idx]) break;
        swap(&heap->data[parent], &heap->data[idx]);
        idx = parent;
    }
}

void heapifyDown(MaxHeap* heap, int idx) {
    while (1) {
        int largest = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < heap->size && heap->data[left] > heap->data[largest]) {
            largest = left;
        }
        if (right < heap->size && heap->data[right] > heap->data[largest]) {
            largest = right;
        }
        
        if (largest == idx) break;
        swap(&heap->data[idx], &heap->data[largest]);
        idx = largest;
    }
}

void push(MaxHeap* heap, int val) {
    heap->data[heap->size] = val;
    heapifyUp(heap, heap->size);
    heap->size++;
}

int pop(MaxHeap* heap) {
    int root = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return root;
}

int* solution(int** queries, int queriesSize, int* queriesColSize, int k, int* returnSize) {
    MaxHeap* heap = createHeap(k + 1);
    int* results = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int x = queries[i][0], y = queries[i][1];
        // Calculate Manhattan distance from origin
        int distance = abs(x) + abs(y);
        
        // Add to max heap
        push(heap, distance);
        
        // Keep only k smallest distances
        if (heap->size > k) {
            pop(heap);
        }
        
        // Return k-th nearest if we have k elements
        if (heap->size == k) {
            results[i] = heap->data[0];
        } else {
            results[i] = -1;
        }
    }
    
    free(heap->data);
    free(heap);
    return results;
}

int main() {
    // Simple parsing for demonstration
    int k = 3;
    int queriesSize = 3;
    int** queries = (int**)malloc(queriesSize * sizeof(int*));
    int* queriesColSize = (int*)malloc(queriesSize * sizeof(int));
    
    // Example input: [[1,2],[3,4],[2,3]]
    for (int i = 0; i < queriesSize; i++) {
        queries[i] = (int*)malloc(2 * sizeof(int));
        queriesColSize[i] = 2;
    }
    queries[0][0] = 1; queries[0][1] = 2;
    queries[1][0] = 3; queries[1][1] = 4;
    queries[2][0] = 2; queries[2][1] = 3;
    
    int returnSize;
    int* result = solution(queries, queriesSize, queriesColSize, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log k)

n queries, each requiring O(log k) heap operations

⚡ Linearithmic

Space Complexity

O(k)

Max heap stores at most k distances

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 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 - Maintain K Nearest — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler