[Java] O(N(people)) + O(limit) solution
Seems most people use sorting with N logN complexity. For this problem, we can use bucket sort with linear complexity. Instead of using two-pointers on an array
Seems most people use sorting with N logN complexity. For this problem, we can use bucket sort with linear complexity. Instead of using two-pointers on an array of the weight of the people, we can use two pointers on a count array. Code:\n\n```\nclass Solution {\n    public int numRescueBoats(int[] people, int limit) {\n        int[] count = new int[limit];\n        for(int i: people) {\n            count[i-1]++;\n        }\n        int re = count[limit-1];\n        int start = 0, end = limit-2;\n        while(start < end) {\n            if(start + end <= limit - 2) { //if boat can hold two people\n                int min = Math.min(count[start], count[end]);\n                re += min;\n                count[start] -= min;\n                count[end] -= min;\n                if(count[start] == 0) start++;\n                if(count[end] == 0) end--;\n            }\n            else { //if boat can only hold one person\n                re += count[end--];\n            }\n        }\n        if(start == end) {\n            if(2 * start + 2 <= limit) {\n                re += (count[start] + 1) / 2;\n            }\n            else {\n                re += count[start];\n            }\n        }\n        return re;\n    }\n}\n```
[]