easy thought process to improve from O(nlogn) to O(n)
the O(nlogn) solution wasn\'t difficult to came up with after sorting the array. We simply maintain 2 pointers start and end. If people[start] + people[end] <= 
the O(nlogn) solution wasn\'t difficult to came up with after sorting the array. We simply maintain 2 pointers `start` and `end`. If `people[start] + people[end] <= limit` meaning both start and end can put in the same boat, hence we increament `start` and decrement `end`. If `people[start] + people[end] > limit` meaning only `end` can be on the boad, hence we decrement `end` and keep `start`. \n```\npublic int numRescueBoats(int[] people, int limit) {\n        Arrays.sort(people);\n        int solution = 0;\n        int start = 0;\n        int end = people.length -1;\n        \n        while(start <= end) {\n            solution++;\n            if(start == end) break; // last person on boat\n            if(people[start] + people[end] <= limit) start++; // we can carry two people\n            end--;\n        }\n        return solution;\n    }\n```\nTime: O(nlogn)\nSpace: O(1)\n\nWe can see the main cost for this logic is the `Arrays.sort()`. After seeing the hint "It is guaranteed each person can be carried by a boat", we know that the number in the array will not be larger than `limit`; Hence, it is suitable for bucket sort. Once we sort the array, the remain logic is the same. The only difference is that we need make sure `start` and `end` are pointing to a valid person, since the bucket might be 0;\n\n```\npublic int numRescueBoats(int[] people, int limit) {\n        int[] buckets = new int[limit+1];\n        for(int p: people) buckets[p]++;\n        int start = 0;\n        int end = buckets.length - 1;\n        int solution = 0;\n        while(start <= end) {\n\t\t\t//make sure the start always point to a valid number\n            while(start <= end && buckets[start] <= 0) start++;\n\t\t\t//make sure end always point to valid number\n            while(start <= end && buckets[end] <= 0) end--;\n\t\t\t//no one else left on the ship, hence break.\n            if(buckets[start] <= 0 && buckets[end] <= 0) break;\n            solution++;\n            if(start + end <= limit) buckets[start]--; // both start and end can carry on the boat\n            buckets[end]--;\n        }\n        return solution;\n    }\n```\nOf course engineering is all about trade offs.\nTime: O(n)\nSpace: O(limit)
[]