97% Faster || Greedy Approach || Short & Concise
Intuition\nSukuna sorts the array, then uses two pointers to pair people efficiently, incrementing boat count for each pair that fits within the weight limit.\n
# Intuition\nSukuna sorts the array, then uses two pointers to pair people efficiently, incrementing boat count for each pair that fits within the weight limit.\n\n# Approach\nLet\'s break it down step by step:\n\n1. **Sorting the Array**: First, Sukuna sorts the array of people\'s weights in ascending order. This step ensures that the heaviest people are at the end of the array.\n\n2. **Initializing Pointers and Boat Count**: Sukuna sets up two pointers: `left` at the beginning of the array and `right` at the end of the array. They also initialize a variable `boats` to keep track of the number of boats needed.\n\n3. **Looping Through the Array**: Sukuna enters a loop that continues as long as the `left` pointer is less than or equal to the `right` pointer. This loop ensures that they consider all pairs of people in the array.\n\n4. **Checking Weight Limit**: Inside the loop, they check if the weight of the person at the `left` pointer plus the weight of the person at the `right` pointer is less than or equal to the limit. This step determines if both people can fit into the same boat without exceeding the weight limit.\n\n5. **Moving Pointers**: If the combined weight is within the limit, Sukuna increments the `left` pointer and decrements the `right` pointer. This action indicates that these two people can share a boat. If not, they only decrement the `right` pointer, indicating that only the heavier person will go in the boat.\n\n6. **Counting Boats**: Regardless of whether they move the pointers or not, Sukuna increments the `boats` variable after each iteration of the loop. This step ensures that they count the number of boats needed to rescue all the people.\n\n7. **Returning the Result**: Finally, they return the `boats` variable, which contains the total number of boats needed to rescue all the people while respecting the weight limit per boat.\n\nIn summary, Sukuna\'s approach optimizes the use of each boat\'s capacity by pairing people together efficiently, thereby minimizing the total number of boats needed to rescue everyone.\n\n# Complexity\n- Time complexity: O(n * logn)\n\n- Space complexity: O(1)\n\n# Code\n\n```java []\nclass Solution {\n    public int numRescueBoats(int[] people, int limit) {\n        Arrays.sort(people);\n        int left = 0, right = people.length - 1, boats = 0;\n\n        while(left <= right) {\n            if(people[left] + people[right] <= limit) {\n                left++;\n                right--;\n            } else {\n                right--;\n            }\n\n            boats++;\n        }\n\n        return boats;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int numRescueBoats(vector<int>& people, int limit) {\n        sort(begin(people), end(people));\n        int left = 0, right = people.size() - 1, boats = 0;\n\n        while (left <= right) {\n            if (people[left] + people[right] <= limit) {\n                left++;\n                right--;\n            } else {\n                right--;\n            }\n            boats++;\n        }\n        \n        return boats;\n    }\n};\n```\n```python []\nclass Solution:\n    def numRescueBoats(self, people: List[int], limit: int) -> int:\n        people.sort()\n        left, right, boats = 0, len(people) - 1, 0\n\n        while left <= right :\n            if people[left] + people[right] <= limit :\n                left += 1\n                right -= 1\n            else :\n                right -= 1\n\n            boats += 1\n\n        return boats\n```\n```javascript []\n/**\n * @param {number[]} people\n * @param {number} limit\n * @return {number}\n */\nvar numRescueBoats = function(people, limit) {\n    people.sort((a, b) => a - b);\n    let left = 0, right = people.length - 1, boats = 0;\n\n    while(left <= right) {\n        if(people[left] + people[right] <= limit) {\n            left++;\n            right--;\n        } else {\n            right--;\n        }\n\n        boats++;\n    }\n\n    return boats;\n};\n```\n![sukuna.webp](https://assets.leetcode.com/users/images/76d873c8-057d-425e-a443-2c99d7488606_1714799474.3250282.webp)\n
['Array', 'Two Pointers', 'Greedy', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']