👏Beats 98.97% of users with Java🎉|| ✅Best Explanation || Greedy Solution 🔥💥|| 2 Pointers
Intuition\n\u2B50 What\'s the Goal?\n\nWe aim to determine the minimum number of boats required to transport all individuals present in the array, ensuring that
# Intuition\n**\u2B50 What\'s the Goal?**\n\nWe aim to determine the minimum number of boats required to transport all individuals present in the array, ensuring that each boat\'s capacity doesn\'t exceed the limit.\n\n**\u2B50 How Do We Achieve This?**\n\nTo achieve this, we employ a **greedy approach**. We begin by **sorting the individuals in ascending order** based on their weights. Then, we pair individuals starting from the two ends of the sorted array. **By prioritizing the heavier individuals first, we maximize the space utilization in each boat, enabling us to potentially accommodate more individuals overall.**\n\nThis approach exploits the fact that **if we transport the heaviest individual first, we can then fit as many lighter individuals as possible into the boat without exceeding the weight limit.** Consequently, this strategy minimizes the total number of boats required for transportation.\n\n\n![Screenshot 2024-05-04 135435.png](https://assets.leetcode.com/users/images/a42f36e7-1160-45ec-840d-9d131ae9828c_1714811156.114191.png)\n\n\n# Approach\n\n**1.Sort the array:** Firstly, the array of people is sorted in ascending order. This step is essential for the algorithm\'s efficiency.\n`Arrays.sort(people);`\n\n\n**2. Initialize pointers:** \nTwo pointers, i and j, are initialized at the beginning and end of the sorted array, respectively.\n`int i = 0, j = people.length - 1;`\n\n\n**3. Iterate through the array:** \nA while loop is used to iterate through the array from both ends (i from the beginning and j from the end) until they meet or cross each other.\n```\nwhile (i <= j) {\n    // Code \n}\n\n```\n\n**4. Check if two people can fit in a boat:** \nWithin the loop, it checks if the sum of the weights of the person at index i and the person at index j is less than or equal to the given limit.\n```\nif ((people[j] + people[i]) <= limit) {\n    i++; // If they can fit, move to the next person from the lighter side.\n}\n```\n\n**5. Move pointers:** \nRegardless of whether two people can fit in a boat or not, the pointer j is decremented in each iteration to consider the next person from the heavier end of the array.\n`j--;\n`\n\n**6. Count boats:** \nIncrement the boats variable in each iteration to keep track of the number of boats required.\n```\nboats++;\n\n```\n\n **7. Return the total number of boats:**\n  Finally, the function returns the total number of boats required to rescue all the people.\n`return boats;\n`\n\n**This approach ensures that the algorithm efficiently determines the minimum number of boats required to rescue all individuals while adhering to the given weight limit for each boat.**\n# Complexity\n- **Time complexity:**\n    <!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    **Sorting Step**: Sorting the array of people takes O(n log n) time complexity, where n is the number of people.\n\n    **Iterating through the Array:** The while loop iterates through the array once, which takes O(n) time in the worst case.\n\n    **Overall, the time complexity** is dominated by the sorting step, resulting in **O(n log n).**\n\n- **Space complexity:**\n    <!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    For sorting algorithms, including the one used here (Arrays.sort()), the space complexity is O(1) or constant space, as the sorting is typically performed in-place.\n\n    Apart from the input array and a few variables (i, j, boats), no additional space is used in the algorithm.\n\n    Therefore, **the space complexity is O(1).**\n\n# Code\n```\nclass Solution {\n    public int numRescueBoats(int[] people, int limit) {\n        Arrays.sort(people);\n        int i=0;int j=people.length-1; int boats=0;\n        while(i<=j){\n            if(people[i]+people[j]<=limit){\n                i++;\n            }\n            j--;\n            boats++;\n        }\n        return boats;\n    }\n}\n```\n\n**UpVote Please**\n\n![upvote2.jpeg](https://assets.leetcode.com/users/images/a8bed379-2d8d-4379-9fdd-1845ef1bc33e_1714811124.616744.jpeg)\n
['Array', 'Two Pointers', 'Greedy', 'Java']