1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/**
 * Sorting Approach
 * Time Complexity: O(n log n) - Dominated by the sorting operation
 * Space Complexity: O(n) - For storing the distances and sorted points
 * 
 * @param {number[][]} points - Array of points [x, y]
 * @param {number} k - Number of closest points to return
 * @return {number[][]} - k closest points to the origin
 */
function kClosestSorting(points, k) {
  // Sort points by distance to origin
  return points.sort((a, b) => {
    return (a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]);
  }).slice(0, k);
}
 
/**
 * Max Heap Approach
 * Time Complexity: O(n log k) - Where n is the number of points
 * Space Complexity: O(k) - For storing the heap of size k
 * 
 * Note: JavaScript doesn't have a built-in heap, so we'll implement a simple max heap
 * 
 * @param {number[][]} points - Array of points [x, y]
 * @param {number} k - Number of closest points to return
 * @return {number[][]} - k closest points to the origin
 */
function kClosestMaxHeap(points, k) {
  // Create a max heap of size k
  const heap = [];
  
  // Helper function to maintain heap property
  const heapify = (i) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;
    
    if (left < heap.length && heap[left][0] > heap[largest][0]) {
      largest = left;
    }
    
    if (right < heap.length && heap[right][0] > heap[largest][0]) {
      largest = right;
    }
    
    if (largest !== i) {
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      heapify(largest);
    }
  };
  
  // Add point to heap
  const addToHeap = (distance, point) => {
    heap.push([distance, point]);
    let i = heap.length - 1;
    let parent = Math.floor((i - 1) / 2);
    
    while (i > 0 && heap[i][0] > heap[parent][0]) {
      [heap[i], heap[parent]] = [heap[parent], heap[i]];
      i = parent;
      parent = Math.floor((i - 1) / 2);
    }
  };
  
  // Remove top element from heap
  const pollFromHeap = () => {
    const top = heap[0];
    heap[0] = heap[heap.length - 1];
    heap.pop();
    heapify(0);
    return top;
  };
  
  // Process all points
  for (const point of points) {
    const distance = point[0] * point[0] + point[1] * point[1];
    addToHeap(distance, point);
    
    if (heap.length > k) {
      pollFromHeap();
    }
  }
  
  // Extract points from heap
  const result = [];
  while (heap.length > 0) {
    result.push(pollFromHeap()[1]);
  }
  
  return result;
}
 
/**
 * QuickSelect Approach
 * Time Complexity: O(n) average, O(n²) worst case
 * Space Complexity: O(n) - For storing the distances and points
 * 
 * @param {number[][]} points - Array of points [x, y]
 * @param {number} k - Number of closest points to return
 * @return {number[][]} - k closest points to the origin
 */
function kClosestQuickSelect(points, k) {
  // Calculate squared distances
  const distances = points.map(point => {
    const distance = point[0] * point[0] + point[1] * point[1];
    return [distance, point];
  });
  
  // QuickSelect algorithm
  const quickSelect = (left, right) => {
    if (left >= right) return;
    
    // Choose pivot (rightmost element)
    const pivot = distances[right][0];
    let i = left;
    
    // Partition around pivot
    for (let j = left; j < right; j++) {
      if (distances[j][0] <= pivot) {
        [distances[i], distances[j]] = [distances[j], distances[i]];
        i++;
      }
    }
    
    // Place pivot in its final position
    [distances[i], distances[right]] = [distances[right], distances[i]];
    
    // If pivot is at position k-1, we've found our answer
    if (i === k - 1) {
      return;
    } else if (i < k - 1) {
      // If pivot is before position k-1, search in the right half
      quickSelect(i + 1, right);
    } else {
      // If pivot is after position k-1, search in the left half
      quickSelect(left, i - 1);
    }
  };
  
  // Apply QuickSelect
  quickSelect(0, distances.length - 1);
  
  // Return k closest points
  return distances.slice(0, k).map(item => item[1]);
}
 
// Test cases
const points1 = [[1, 3], [-2, 2]];
const k1 = 1;
console.log(kClosestSorting(points1, k1)); // [[-2, 2]]
 
const points2 = [[3, 3], [5, -1], [-2, 4]];
const k2 = 2;
console.log(kClosestSorting(points2, k2)); // [[3, 3], [-2, 4]] or [[-2, 4], [3, 3]]