✔💯 DAY 368 | 100% | [JAVA/C++/PYTHON] | EXPLAINED | INTUTION | DRY RUN | PROOF 💫
Please Upvote as it really motivates me\n\n##### \u2022\tThere are several ways to solve the problem of finding the minimum number of boats required to transpor
# Please Upvote as it really motivates me\n![image.png](https://assets.leetcode.com/users/images/cbce75b2-741d-412e-951a-acc057ac9215_1680491397.7553709.png)\n##### \u2022\tThere are several ways to solve the problem of finding the minimum number of boats required to transport people across a river. \n##### \u2022\tGreedy algorithm: This is the most common approach to solving this problem. It involves sorting the array of people in non-decreasing order of weight and then using two pointers to keep track of the lightest and heaviest person respectively. We then try to fit the heaviest person with the lightest person in the same boat, and if they can fit, we move both pointers towards the center of the array. If they cannot fit, we put the heaviest person in their own boat and move the pointer at the end of the array towards the center. We repeat this process until the two pointers have crossed each other, at which point we have used the minimum number of boats.\n##### \u2022\tDynamic programming: This approach involves breaking the problem down into smaller subproblems and solving them recursively. We can define a function that takes as input the current state of the array (i.e., which people have already been placed in boats) and returns the minimum number of boats required to transport the remaining people. We can then use memoization or tabulation to avoid recomputing the same subproblems multiple times.\n##### \u2022\tBinary search: This approach involves using binary search to find the optimal number of people that can be placed in each boat. We start by setting the lower bound to 1 (i.e., each boat can only carry one person) and the upper bound to the total number of people. We then repeatedly check whether it is possible to transport all the people using boats that can carry at most k people, where k is the midpoint between the lower and upper bounds. If it is possible, we update the lower bound to k+1; otherwise, we update the upper bound to k-1. We repeat this process until the lower and upper bounds converge to the optimal number of people per boat.\n##### \u2022\tBacktracking: This approach involves generating all possible combinations of people that can be placed in each boat and selecting the one that uses the minimum number of boats. This approach is not practical for large inputs, but it can be useful for small inputs or as a way to verify the correctness of other algorithms.\n\n\n\n# Intuition &  Approach\n<!-- Describe your approach to solving the problem. -->\n##### \u2022\tBoats intuition:\n##### \u2022\tThe problem can be solved using a greedy approach. We want to minimize the number of boats used, so we should try to fit as many people as possible in each boat. We can start by sorting the array of people in non-decreasing order of weight. Then, we can use two pointers, one at the beginning and one at the end of the array, to keep track of the lightest and heaviest person respectively. We can then try to fit the heaviest person with the lightest person in the same boat. If they can fit, we move both pointers towards the center of the array. If they cannot fit, we put the heaviest person in their own boat and move the pointer at the end of the array towards the center. We repeat this process until the two pointers have crossed each other, at which point we have used the minimum number of boats.\n##### \u2022\tBoats approach:\n##### \u2022\tThe function sorts the array of people\'s weights in descending order.\n##### \u2022\tIt then uses a two-pointer approach to iterate through the array from both ends, trying to fit as many people as possible into each boat.\n##### \u2022\tIf the sum of the weights of the two people being considered is less than or equal to the maximum weight capacity of the boat, they are added to the boat and the pointers move towards the center of the array.\n##### \u2022\tIf the sum of the weights is greater than the maximum weight capacity, only the heavier person is added to the boat and the pointer corresponding to the lighter person moves towards the center of the array.\n##### \u2022\tThe function keeps track of the number of boats used and returns this value.\n##### \u2022\tBoats algorithm:\n##### \u2022\tDefine a function called "numRescueBoats" that takes in an array of integers called "people" and an integer called "limit".\n##### \u2022\tSort the "people" array in descending order.\n##### \u2022\tInitialize two pointers "s" and "e" to the start and end of the array respectively.\n##### \u2022\tInitialize a variable "bo" to 0 to keep track of the number of boats used.\n##### \u2022\tWhile "s" is less than or equal to "e":\na. If the sum of "people[s]" and "people[e]" is less than or equal to "limit", increment "s" and decrement "e".\nb. Otherwise, only increment "s".\nc. Increment "bo".\n##### \u2022\tReturn "bo".\n\n\n\n# Code\n```JAVA []\npublic int numRescueBoats(int[] A, int level) {\n        int bo=0,s=0,e=A.length-1;\n        Arrays.sort(A);\n        while (s<=e) {\n        if(A[s]+A[e]<=level) s++;\n        e--;\n        bo++;\n        }return bo;\n}   \n```\n```C++ []\nint numRescueBoats(vector<int>& A, int level) {\n        int bo = 0, s = 0, e = A.size() - 1;\n        sort(A.begin(), A.end());\n        while (s <= e) {\n            if (A[s] + A[e] <= level) s++;\n            e--;\n            bo++;\n        }\n        return bo;\n    }\n```\n```PYTHON []\ndef numRescueBoats(self, A: List[int], level: int) -> int:\n        bo, s, e = 0, 0, len(A) - 1\n        A.sort()\n        while s <= e:\n            if A[s] + A[e] <= level:\n                s += 1\n            e -= 1\n            bo += 1\n        return bo\n```\n\n\n# Complexity\n- Time complexity:O(SORT)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# 2ND WAY WITHOUT SORTING\n\n```JAVA []\npublic int numRescueBoats(int[] A, int level) {\nint B[]=new int[level+1];\n        for(int i=0;i<A.length;i++) B[A[i]]++;\n        int bo=B[level],s=1,e=level-1;\n        while(s<=e){\n            while(s<=e&& B[s]<=0)s++;\n            while(s<=e&& B[e]<=0)e--;\n            if(s>e)break;\n            if(s+e<=level){\n                bo++;\n                B[s]--;\n                B[e]--;\n            }else{\n                bo+=B[e];\n                e--;\n            }\n        }\n        return bo;\n    }\n```\n```C++ []\nint numRescueBoats(vector<int>& people, int limit) {\n        vector<int> B(limit+1, 0);\n        for(int i=0;i<people.size();i++) B[people[i]]++;\n        int bo=B[limit],s=1,e=limit-1;\n        while(s<=e){\n            while(s<=e&& B[s]<=0) s++;\n            while(s<=e&& B[e]<=0) e--;\n            if(s>e) break;\n            if(s+e<=limit){\n                bo++;\n                B[s]--;\n                B[e]--;\n            }else{\n                bo+=B[e];\n                e--;\n            }\n        }\n        return bo;\n    }\n```\n```PYTHON []\ndef numRescueBoats(self, people: List[int], limit: int) -> int:\n        B = [0] * (limit+1)\n        for p in people:\n            B[p] += 1\n        bo, s, e = B[limit], 1, limit-1\n        while s <= e:\n            while s <= e and B[s] <= 0:\n                s += 1\n            while s <= e and B[e] <= 0:\n                e -= 1\n            if s > e:\n                break\n            if s + e <= limit:\n                bo += 1\n                B[s] -= 1\n                B[e] -= 1\n            else:\n                bo += B[e]\n                e -= 1\n        return bo\n```\n\n# 3RD WAY \n```JAVA []\npublic int numRescueBoats(int[] people, int limit) {\n        int result = 0;\n        int min = Integer.MAX_VALUE;\n        int max = Integer.MIN_VALUE;\n        for(int p : people) {\n            min = Math.min(min, p);\n            max = Math.max(max, p);\n        }\n        int[] count = new int[max-min+1];\n        for(int p : people) {\n            count[p-min]++;\n        }\n        int l = min;\n        int r = max;\n        while(l<r) {\n            if(r+l>limit) {\n                result += count[r-min];\n                count[r-min] = 0;\n                while(l<r && count[r-min]==0) {\n                    r--;\n                }\n            } else {\n                int minCount = Math.min(count[l-min], count[r-min]);\n                count[l-min] -= minCount;\n                count[r-min] -= minCount;\n                result += minCount;\n                while(l<r && count[r-min]==0) {\n                    r--;\n                }\n                while(l<r && count[l-min]==0) {\n                    l++;\n                }\n            }\n        }\n        if(count[l-min]>0) {\n            int d = limit/l;\n            if(d==1)\n                result += count[l-min];\n            else\n                result += (count[l-min]/2)+(count[l-min]%2);\n        }\n        return result;       \n    }\n```\n```C++ []\nint numRescueBoats(vector<int>& people, int limit) {\n    int result = 0;\n    int min = INT_MAX;\n    int max = INT_MIN;\n    for(int p : people) {\n        min = std::min(min, p);\n        max = std::max(max, p);\n    }\n    vector<int> count(max-min+1);\n    for(int p : people) {\n        count[p-min]++;\n    }\n    int l = min;\n    int r = max;\n    while(l<r) {\n        if(r+l>limit) {\n            result += count[r-min];\n            count[r-min] = 0;\n            while(l<r && count[r-min]==0) {\n                r--;\n            }\n        } else {\n            int minCount = std::min(count[l-min], count[r-min]);\n            count[l-min] -= minCount;\n            count[r-min] -= minCount;\n            result += minCount;\n            while(l<r && count[r-min]==0) {\n                r--;\n            }\n            while(l<r && count[l-min]==0) {\n                l++;\n            }\n        }\n    }\n    if(count[l-min]>0) {\n        int d = limit/l;\n        if(d==1)\n            result += count[l-min];\n        else\n            result += (count[l-min]/2)+(count[l-min]%2);\n    }\n    return result;\n}\n```\n```PYTHON []\ndef numRescueBoats(people, limit):\n    result = 0\n    min_val = min(people)\n    max_val = max(people)\n    count = [0] * (max_val - min_val + 1)\n    for p in people:\n        count[p - min_val] += 1\n    l = min_val\n    r = max_val\n    while l < r:\n        if r + l > limit:\n            result += count[r - min_val]\n            count[r - min_val] = 0\n            while l < r and count[r - min_val] == 0:\n                r -= 1\n        else:\n            min_count = min(count[l - min_val], count[r - min_val])\n            count[l - min_val] -= min_count\n            count[r - min_val] -= min_count\n            result += min_count\n            while l < r and count[r - min_val] == 0:\n                r -= 1\n            while l < r and count[l - min_val] == 0:\n                l += 1\n    if count[l - min_val] > 0:\n        d = limit // l\n        if d == 1:\n            result += count[l - min_val]\n        else:\n            result += (count[l - min_val] // 2) + (count[l - min_val] % 2)\n    return result\n\n```\n[HERE IS MY POST LINK](https://leetcode.com/problems/boats-to-save-people/solutions/3372724/day-368-100-java-c-python-explained-intution-dry-run-proof/) PLEASE LIKE \n# DRY RUN \nInput: people = [1,2], limit = 3\nOutput: 1\nExplanation: 1 boat (1, 2)\n\n##### \u2022\tlet\'s dry run the given input:\n##### \u2022\tInitially, bo 0, s is 0, and e is 1. \n##### \u2022\tWe sort the array A , which becomes [1, 2] .\n##### \u2022\tIn the while loop, since s is less than or equal to e , we enter the loop. Since A[s] + A[e] is equal to 3, which is less than or equal to level (which is also 3), we increment s to 1. \n##### \u2022\tWe decrement e to 0. We increment bo to 1. \n##### \u2022\tNow, s is 1 and e is 0. Since s is greater than e , we exit the loop. \n##### \u2022\tFinally, we return bo , which is 1. Therefore, the output for the given input is 1.\n\n\n\n![BREUSELEE.webp](https://assets.leetcode.com/users/images/062630f0-ef80-4e74-abdb-302827b99235_1680054012.5054147.webp)\n\n![meme2.png](https://assets.leetcode.com/users/images/d588f492-3f95-45f6-8e4a-10d6069002a5_1680054021.7117147.png)\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A
['Two Pointers', 'Python', 'C++', 'Java', 'Python3']