# Java O(n^2) greedy solution

• We always choose the current shortest height (so we need to sort input first), and then try to put it into the right position. We simply scan from the left and count how many persons are really >= its own height. Then we put the person into the empty slot.

``````public class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length <= 1) {
return people;
}
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
}
});
int n = people.length;
int[][] ret = new int[n][];
for (int i = 0; i < n; i++) {
for (int j = 0, ahead = 0; j < n; j++) {
ahead += (ret[j] == null || ret[j][0] >= people[i][0]) ? 1 : 0;
} else if (ret[j] == null) {
ret[j] = people[i];
break;
}
}
}
return ret;
}
}
``````

• Thanks for the code! Here is my C++. I did one pass for people with the same height.

``````class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
sort(people.begin(), people.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.first < b.first || (a.first == b.first && a.second < b.second);});
int n = people.size();
vector<pair<int, int>> ans(n, {-1, 0});
for (int i = 0; i < n;) {
int k = people[i].first, j = 0, ahead = 0;
while (i < n && people[i].first == k) {
}
while (ans[j].first != -1) j++;
ans[j++] = people[i++];
}
}
return ans;
// Another solution to choose highest people first
/*sort(people.begin(), people.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.second < b.second || (a.second == b.second && a.first < b.first);});
int n = people.size();
vector<pair<int, int>> ans;
for (int i = 0; i < n; i++) {
ans.insert(ans.begin()+people[i].second, people[i]);
}
return ans;*/
}
};
``````

• To relieve the pain for future readers:
this solution sort in the manner of `height` ascending first, and `rank` ascending if height tie (`rank` as defined as number of people taller than or equal to my height who is also standing before me).

After sorting, we iterate through `people`, for each `people[i]`, we try to directly put it into the correct position. `j` is used to iterate from left to right in the output list, while `ahead` is used to record the actual number of slots that could be counted into the calculation of `people[i]`'s rank. If at position `j` we already have somebody placed, and also this somebody is shorter than `people[i]` (which is yet to be placed in this iteration of the outer loop), then we don't count this slot into `ahead` since `people[i]`'s rank's calculation does not take this slot's person into account anyway(he's shorter).

When `ahead` reaches `people[i]`'s rank, put him there.

Come on people, at least tell the readers what your variable name means.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.