K Closest Points to Origin

📋

K Closest Points to Origin

Edge cases:

</>

IDE

def kClosest(points: list[list[int]], k: int) -> list[list[int]]:public int[][] kClosest(int[][] points, int k)vector<vector<int>> kClosest(vector<vector<int>>& points, int k)function kClosest(points, k)

def kClosest(points, k):
    # Write your solution here
    pass

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // Write your solution here
        return new int[0][0];
    }
}

#include <vector>
using namespace std;

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    // Write your solution here
    return {};
}

function kClosest(points, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,3]]Sorting points by x or y coordinate instead of distance.✅ Sort points using key=lambda p: p[0]*p[0] + p[1]*p[1].

Wrong: [[1,3],[-2,2]]Returning all points regardless of k value.✅ Return only points[:k] after sorting by distance.

Wrong: [[1,1],[2,2],[3,3],[4,4],[5,5]]Ignoring k and returning all points.✅ Return exactly k points after sorting or selecting.

Wrong: Function crashes or infinite loopNo handling for empty input or k=0.✅ Add guard clause: if not points or k == 0: return [].

Wrong: TLE on large inputUsing O(n^2) brute force or repeated sorting.✅ Use max heap of size k or quickselect algorithm for O(n log k) or average O(n) time.

✓

Test Cases

Consider edge cases like empty input and k equal to points length.

Watch out for points with identical distances and greedy traps.

Optimize your solution to handle large inputs efficiently.

t1_01basic

Input{"points":[[1,3],[-2,2]],"k":1}

Expected[[-2,2]]

⏱ Performance - must finish in 2000ms

The point (-2, 2) is closer to the origin than (1, 3).

💡 Sort points by their squared distance to the origin.

💡 Use the comparator: distance = x^2 + y^2.

💡 Return the first k points after sorting by distance.

Why it failed: Returned points are incorrect or not the closest. Check if sorting uses squared distance and returns exactly k points.

✓ Correctly returns the closest point using sorting by squared distance.

t1_02basic

Input{"points":[[3,3],[5,-1],[-2,4]],"k":2}

Expected[[3,3],[-2,4]]

⏱ Performance - must finish in 2000ms

Points (3,3) and (-2,4) are closer to origin than (5,-1).

💡 Calculate squared distances: 18, 26, 20 respectively.

💡 Sort points by these distances and pick first k=2.

💡 Return points with distances 18 and 20.

Why it failed: Incorrect points returned or wrong number of points. Ensure sorting by squared distance and returning exactly k points.

✓ Correctly returns the two closest points by sorting.

t2_01edge

Input{"points":[],"k":0}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input returns empty output.

💡 Check behavior when points array is empty.

💡 k can be zero, so return empty list immediately.

💡 Add a guard clause for empty input or k=0.

Why it failed: Function crashes or returns non-empty output on empty input. Add check for empty points or k=0 to return [].

✓ Handles empty input and k=0 correctly by returning [].

t2_02edge

Input{"points":[[0,0]],"k":1}

Expected[[0,0]]

⏱ Performance - must finish in 2000ms

Single point input returns that point when k=1.

💡 With one point and k=1, return that point.

💡 Distance calculation trivial but must still work.

💡 Ensure no off-by-one errors when k equals points length.

Why it failed: Fails to return the single point or returns empty. Fix indexing and ensure k=points.length returns all points.

✓ Correctly returns the single point when k=1.

t2_03edge

Input{"points":[[1,1],[2,2],[3,3]],"k":3}

Expected[[1,1],[2,2],[3,3]]

⏱ Performance - must finish in 2000ms

k equals number of points, so return all points.

💡 When k equals points length, return all points.

💡 No sorting needed but sorting is acceptable.

💡 Check boundary condition k == points.length.

Why it failed: Returns fewer than all points when k equals points length. Fix condition to return all points if k == len(points).

✓ Returns all points correctly when k equals points length.

t2_04edge

Input{"points":[[-1,-1],[-1,1],[1,-1],[1,1]],"k":2}

Expected[[-1,-1],[-1,1]]

⏱ Performance - must finish in 2000ms

Points with negative coordinates handled correctly.

💡 Distance calculation uses squares, so negatives become positive.

💡 Ensure no sign errors in distance computation.

💡 Return any k points with smallest distances.

Why it failed: Incorrect distance calculation due to sign errors. Fix distance formula to use squares of coordinates.

✓ Correctly handles negative coordinates in distance calculation.

t3_01corner

Input{"points":[[1,1],[1,-1],[-1,1],[-1,-1]],"k":2}

Expected[[1,1],[1,-1]]

⏱ Performance - must finish in 2000ms

All points have same distance sqrt(2), any 2 points are valid closest.

💡 Check if your code handles multiple points with identical distances.

💡 Sorting by distance alone may not guarantee order; any k points with smallest distance are valid.

💡 Return any k points with the minimum distance, do not rely on stable sort.

Why it failed: Fails by returning points with larger distances or wrong count. Fix sorting to handle ties correctly and return exactly k points.

✓ Correctly returns any k points among those with smallest equal distances.

t3_02corner

Input{"points":[[1,2],[2,1],[3,3],[0,0]],"k":1}

Expected[[0,0]]

⏱ Performance - must finish in 2000ms

Closest point is (0,0) with distance 0.

💡 Check if your code correctly calculates zero distance.

💡 Avoid off-by-one errors when k=1.

💡 Return the single closest point correctly.

Why it failed: Returns wrong point or multiple points when k=1. Fix logic to pick minimum distance point and return exactly one point.

✓ Correctly returns the single closest point when k=1.

t3_03corner

Input{"points":[[1,1],[2,2],[3,3],[4,4],[5,5]],"k":3}

Expected[[1,1],[2,2],[3,3]]

⏱ Performance - must finish in 2000ms

Greedy approach picking points with smallest x or y fails; must use distance.

💡 Do not pick points greedily by x or y coordinate alone.

💡 Use squared Euclidean distance to compare points.

💡 Sort or select points by distance, not coordinate values.

Why it failed: Returns points not closest by distance due to greedy coordinate-based selection. Fix to use distance comparator for sorting or selection.

✓ Correctly returns closest points by distance, avoiding greedy coordinate traps.

t4_01performance

Input{"points":[[0,0],[1,-1],[2,-2],[3,-3],[4,-4],[5,-5],[6,-6],[7,-7],[8,-8],[9,-9],[10,-10],[11,-11],[12,-12],[13,-13],[14,-14],[15,-15],[16,-16],[17,-17],[18,-18],[19,-19],[20,-20],[21,-21],[22,-22],[23,-23],[24,-24],[25,-25],[26,-26],[27,-27],[28,-28],[29,-29],[30,-30],[31,-31],[32,-32],[33,-33],[34,-34],[35,-35],[36,-36],[37,-37],[38,-38],[39,-39],[40,-40],[41,-41],[42,-42],[43,-43],[44,-44],[45,-45],[46,-46],[47,-47],[48,-48],[49,-49],[50,-50],[51,-51],[52,-52],[53,-53],[54,-54],[55,-55],[56,-56],[57,-57],[58,-58],[59,-59],[60,-60],[61,-61],[62,-62],[63,-63],[64,-64],[65,-65],[66,-66],[67,-67],[68,-68],[69,-69],[70,-70],[71,-71],[72,-72],[73,-73],[74,-74],[75,-75],[76,-76],[77,-77],[78,-78],[79,-79],[80,-80],[81,-81],[82,-82],[83,-83],[84,-84],[85,-85],[86,-86],[87,-87],[88,-88],[89,-89],[90,-90],[91,-91],[92,-92],[93,-93],[94,-94],[95,-95],[96,-96],[97,-97],[98,-98],[99,-99]],"k":50}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 points, O(n log n) or O(n log k) expected to complete within 2s.

💡 Use a max heap of size k or quickselect to achieve O(n log k) or average O(n).

💡 Avoid sorting entire array if possible for better performance.

💡 Implement efficient distance comparator and data structures.

Why it failed: TLE due to O(n^2) or brute force approach. Optimize to O(n log k) heap or O(n) quickselect.

✓ Efficient algorithm passes performance test within time limit.

Practice

1. Given the following Python code implementing Quickselect, what is the output of findKthLargest([4,1,3,2], 3)?

easy

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Understand k and indexing

   k=3 means the 3rd largest element, so index k-1=2 in zero-based indexing.

2. Step 2: Trace partition and quickselect

   Partition rearranges so elements > pivot are left; after recursive calls, the element at index 2 is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   3rd largest in [4,1,3,2] is 2 [OK]

Hint: Remember zero-based index k-1 for kth largest [OK]

Common Mistakes:

• Off-by-one error in k indexing
• Confusing kth largest with kth smallest
• Misunderstanding partition direction

2. You need to continuously track the kth largest element in a stream of integers where new elements arrive one by one. Which approach guarantees efficient updates and retrievals after each new element arrives?

easy

A. Sort the entire stream after each new element and pick the kth largest element.

B. Maintain a min-heap of size k containing the current k largest elements seen so far.

C. Use a max-heap containing all elements and extract the kth largest by popping k times.

D. Use dynamic programming to store intermediate kth largest values for all prefixes.

Solution

1. Step 1: Understand the problem constraints

   We need to efficiently update and retrieve the kth largest element after each insertion in a stream.

2. Step 2: Evaluate approaches

   Sorting the entire stream each time (B) is inefficient (O(n log n) per add). Using a max-heap of all elements (C) requires popping k times per query, which is costly. Dynamic programming (D) is not applicable here as the problem is not about overlapping subproblems but about maintaining order dynamically. Maintaining a min-heap of size k (A) keeps the kth largest element at the root, allowing O(log k) updates and O(1) retrieval.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap of size k efficiently tracks kth largest element [OK]

Hint: Min-heap size k keeps kth largest at root efficiently [OK]

Common Mistakes:

• Sorting entire stream each time is too slow
• Using max-heap of all elements wastes space and time
• Dynamic programming is irrelevant here

3. The following code attempts to find the kth smallest element in a sorted matrix using binary search on the value range. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line with 'if matrix[row][col] < mid:' inside countLessEqual

B. Line with 'low, high = matrix[0][0], matrix[-1][-1]'

C. Line with 'if countLessEqual(mid) < k:' inside while loop

D. Line with 'return low' at the end

Solution

1. Step 1: Examine countLessEqual condition

   The condition uses '<' instead of '<=' which causes elements equal to mid to be excluded from count.

2. Step 2: Understand impact on binary search

   Excluding elements equal to mid causes countLessEqual to undercount, leading binary search to converge incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing '<' to '<=' fixes counting and correctness [OK]

Hint: Counting ≤ mid must include equality [OK]

Common Mistakes:

• Using '<' instead of '<=' in count function
• Off-by-one in binary search updates

4. What is the time complexity of the optimal bucket sort approach for sorting characters by frequency in a string of length n?

medium

A. O(n + m) where m is the maximum frequency of any character

B. O(n * k) where k is the number of unique characters

C. O(n) because counting frequencies and bucket sorting are linear in string length

D. O(n log n) due to sorting the frequency map

Solution

1. Step 1: Count frequencies in O(n)

   Counting frequencies requires one pass over the string.

2. Step 2: Bucket sort in O(n + m)

   Characters are placed into buckets indexed by frequency; iterating buckets takes O(m), total characters sum to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting + bucket iteration both linear in n and max frequency m [OK]

Hint: Bucket sort complexity is O(n + m), where m is max frequency [OK]

Common Mistakes:

• Assuming sorting frequencies requires O(n log n)
• Confusing unique chars count with n

5. Suppose the problem changes: the matrix is no longer sorted by columns, only rows are sorted, and you still need to find the kth smallest element. Which approach is the most suitable to solve this variant efficiently?

hard

A. Use binary search on the value range with the same counting method as before.

B. Use a greedy approach picking the smallest element from each row repeatedly.

C. Flatten the matrix and sort all elements to find the kth smallest.

D. Use a min heap to merge the k sorted rows, extracting the kth smallest element.

Solution

1. Step 1: Understand changed constraints

   Only rows are sorted, columns are not sorted, so binary search counting on columns is invalid.

2. Step 2: Identify suitable approach

   Min heap merging k sorted lists (rows) efficiently finds kth smallest in O(k log n) time.

3. Step 3: Reject other approaches

   Binary search counting fails without column sorting; flattening is O(n² log n²); greedy is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Min heap merge exploits row sorting without column sorting [OK]

Hint: Without column sorting, binary search counting fails [OK]

Common Mistakes:

• Trying binary search counting without column sorting
• Assuming greedy works