Day 93 || Sorting + Two Pointer || Easiest Beginner Friendly Solution
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n\n# Intuitio
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Intuition of this Problem :\n*The given code solves the problem of finding the minimum number of boats required to rescue a group of people from a sinking ship. Each boat has a weight limit, and each person has a specific weight. The goal is to load the people onto the boats in such a way that no boat exceeds its weight limit, and the minimum number of boats are used.*\n\n*The algorithm first sorts the input vector of people\'s weights in ascending order using the sort() function, as it helps in optimizing the solution. We can then start loading the heaviest person and the lightest person together onto the boat. If their weights add up to more than the boat\'s weight limit, then we load only the heaviest person on the boat. We repeat this process until all the people have been loaded onto the boats.*\n\n*The intuition behind this code is to load the heaviest and lightest person together onto the boat, to make the most efficient use of the available space. By sorting the input vector of people\'s weights, we ensure that we can always load the heaviest person pointed to by lastIndex onto the boat, without having to worry about the weights of other people. The use of two pointers allows us to efficiently iterate over the input vector and keep track of the weights of the people being loaded onto the boats.*\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach for this Problem :\n1. Sort the given people array in non-decreasing order.\n2. Initialize minBoatRequired variable to 0, firstIndex to 0 and lastIndex to size of people array minus 1.\n3. While firstIndex is less than or equal to lastIndex, do the following:\n4. Check if people[firstIndex] + people[lastIndex] is less than or equal to the given limit.\n5. If yes, then increment minBoatRequired and move the firstIndex to next index and lastIndex to previous index.\n6. If no, then increment minBoatRequired and move the lastIndex to previous index.\n7. Return the minBoatRequired.\n<!-- Describe your approach to solving the problem. -->\n\n# Code :\n```C++ []\nclass Solution {\npublic:\n    int numRescueBoats(vector<int>& people, int limit) {\n        sort(people.begin(), people.end());\n        //without sorting people you will get wrong and on below test case\n        //people = [3,8,7,1,4], limit = 9, output you will get = 4, expected output = 3\n        int minBoatRequired = 0;\n        int lastIndex = people.size() - 1;\n        int firstIndex = 0;\n        while (firstIndex <= lastIndex) {   \n            if (people[firstIndex] + people[lastIndex] <= limit) {\n                minBoatRequired++;\n                firstIndex++;\n                lastIndex--;\n            }\n            else {\n                minBoatRequired++;\n                lastIndex--;\n            }\n        }\n        return minBoatRequired;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int numRescueBoats(int[] people, int limit) {\n        Arrays.sort(people);\n        int minBoatRequired = 0;\n        int lastIndex = people.length - 1;\n        int firstIndex = 0;\n        while (firstIndex <= lastIndex) {\n            if (people[firstIndex] + people[lastIndex] <= limit) {\n                minBoatRequired++;\n                firstIndex++;\n                lastIndex--;\n            } else {\n                minBoatRequired++;\n                lastIndex--;\n            }\n        }\n        return minBoatRequired;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def numRescueBoats(self, people: List[int], limit: int) -> int:\n        people.sort()\n        minBoatRequired = 0\n        lastIndex = len(people) - 1\n        firstIndex = 0\n        while firstIndex <= lastIndex:\n            if people[firstIndex] + people[lastIndex] <= limit:\n                minBoatRequired += 1\n                firstIndex += 1\n                lastIndex -= 1\n            else:\n                minBoatRequired += 1\n                lastIndex -= 1\n        return minBoatRequired\n\n```\n\n# Time Complexity and Space Complexity:\n- **Time Complexity :** **O(nlogn + n) = O(nlogn)**, where n is the size od people array\n- O(nlogn) is for sorting and O(n) is for two pointer approach\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space Complexity :** **O(logn)**, since we are using sorting, then in worst cse it will take logn space\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Two Pointers', 'Sorting', 'C++', 'Java', 'Python3']