The trick here is to name the state correctly, then let the implementation follow. For 973. K Closest Points to Origin, the solution in this repository is mainly a greedy solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: greedy.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are sort_indexes, idx, dist, partition, sort.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N \log N)O(NlogN), where NN is the length of points.
- Space: O(N)O(N).
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02We have a list of points on the plane. Find the K closest points to the origin (0, 0).
03
04(Here, the distance between two points on a plane is the Euclidean distance.)
05
06You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
07**/
08
09//Runtime: 252 ms, faster than 89.47% of C++ online submissions for K Closest Points to Origin.
10//Memory Usage: 47.6 MB, less than 56.00% of C++ online submissions for K Closest Points to Origin.
11
12/**
13Complexity Analysis
14
15Time Complexity: O(N \log N)O(NlogN), where NN is the length of points.
16
17Space Complexity: O(N)O(N).
18**/
19class Solution {
20public:
21 template <typename T>
22 vector<size_t> sort_indexes(const vector<T> &v) {
23
24 // initialize original index locations
25 vector<size_t> idx(v.size());
26 iota(idx.begin(), idx.end(), 0);
27
28 // sort indexes based on comparing values in v
29 sort(idx.begin(), idx.end(),
30 [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});
31
32 return idx;
33 }
34
35 vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
36 vector<float> dist;
37 vector<vector<int>> ans;
38
39 for(vector<vector<int>>::iterator it=points.begin(); it<points.end(); it++) {
40 vector<int> point = *it;
41 dist.push_back(sqrt(pow(point[0], 2) + pow(point[1],2)));
42 }
43
44 vector<long unsigned int> sorted_indices = sort_indexes(dist);
45 for(int i = 0; i < K; i++){
46 int idx = sorted_indices[i];
47 ans.push_back(points[idx]);
48 }
49
50 return ans;
51 }
52};
53
54//Runtime: 236 ms, faster than 94.04% of C++ online submissions for K Closest Points to Origin.
55//Memory Usage: 44.7 MB, less than 63.56% of C++ online submissions for K Closest Points to Origin.
56/**
57Approach 2: Divide and Conquer
58Intuition
59We want an algorithm faster than N \log NNlogN.
60Clearly, the only way to do this is to use the fact that the K elements returned can be in any order
61-- otherwise we would be sorting which is at least N \log NNlogN.
62
63Say we choose some random element x = A[i] and split the array into two buckets:
64one bucket of all the elements less than x,
65and another bucket of all the elements greater than or equal to x.
66This is known as "quickselecting by a pivot x".
67
68The idea is that if we quickselect by some pivot,
69on average in linear time we'll reduce the problem to a problem of half the size.
70
71Algorithm
72
73Let's do the work(i, j, K) of partially sorting the subarray
74(points[i], points[i+1], ..., points[j])
75so that the smallest K elements of this subarray
76occur in the first K positions (i, i+1, ..., i+K-1).
77
78First, we quickselect by a random pivot element from the subarray.
79To do this in place, we have two pointers i and j,
80and move these pointers to the elements that are in the wrong bucket
81-- then, we swap these elements.
82
83After, we have two buckets [oi, i] and [i+1, oj],
84where (oi, oj) are the original (i, j) values when calling work(i, j, K).
85Say the first bucket has 10 items and the second bucket has 15 items.
86If we were trying to partially sort say, K = 5 items,
87then we only need to partially sort the first bucket: work(oi, i, 5).
88Otherwise, if we were trying to partially sort say, K = 17 items,
89then the first 10 items are already partially sorted,
90and we only need to partially sort the next 7 items: work(i+1, oj, 7).
91**/
92
93/**
94Complexity Analysis
95
96Time Complexity: O(N)O(N) in average case complexity, where NN is the length of points.
97
98Space Complexity: O(N)O(N).
99**/
100
101/**
102class Solution {
103public:
104 int dist(vector<vector<int>>& points, int i){
105 return pow(points[i][0], 2) + pow(points[i][1], 2);
106 }
107
108 int partition(vector<vector<int>>& points, int i, int j){
109 //Partition by pivot A[i], returning an index mid
110 //such that A[i] <= A[mid] <= A[j] for i < mid < j.
111 int oi = i;
112 int pivot = dist(points, i);
113 i += 1;
114
115 while(true){
116 while(i < j && dist(points, i) < pivot) i+=1;
117 while(i <= j && dist(points, j) >= pivot) j-=1;
118 if(i>=j) break;
119 vector<int> tmp = points[i];
120 points[i] = points[j];
121 points[j] = tmp;
122 }
123
124 vector<int> tmp = points[oi];
125 points[oi] = points[j];
126 points[j] = tmp;
127 return j;
128 }
129
130
131 void sort(vector<vector<int>> &points, int i, int j, int K){
132 // Partially sorts A[i:j+1] so the first K elements are
133 // the smallest K elements.
134 if(i>=j) return;
135
136 // Put random element as A[i] - this is the pivot
137 srand(1);
138 int k = rand()%(j-i) + i;
139 vector<int> tmp = points[i];
140 points[i] = points[k];
141 points[k] = tmp;
142
143 int mid = partition(points, i, j);
144 //mid - i + 1 : the size of former partition
145 if(K < mid - i + 1){
146 sort(points, i, mid - 1, K);
147 }else if(K > mid - i + 1){
148 sort(points, mid + 1, j, K - (mid - i +1));
149 }
150 }
151
152 vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
153 sort(points, 0, points.size() - 1, K);
154 vector<vector<int>> ans(points.begin(), points.begin() + K);
155 return ans;
156 }
157
158};
159**/Cost
Complexity
Time
O(N \log N)O(NlogN), where NN is the length of points.
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(N)O(N).
Auxiliary state plus the answer structure where the problem requires one.