**Question:** If a canoe can hold 2 kids and a maximum weight of 150 pounds, write a function that returns the minimum number of canoes needed

Related Tags:

- Sort the array in ascending order.
`O(n log n)` - Start with indices on either ends
`i`, and`j`. - Compare the sum of values at
`i`and`j`to 150. If less than or equal, decrement both indices and increment`numBoats`. - If greater, check if heavier boy qualifies (is <= 150 lbs). If so, increment
`numBoats`. If not, do nothing. In either case decrement`j`.

Time: `O(n log n)` due to sorting at the beginning.

```
public class Canoe {
final static int MAX_WEIGHT = 150;
public static void main(String[] args) {
// Use sorting algorithm O(n log n)
int[] weightList = {45, 67, 84, 100, 120, 134, 150, 167, 180, 200, 213};
System.out.println(numBoatsNeeded(weightList));
}
public static int numBoatsNeeded(int[] weightList) {
int numBoats = 0;
int i = 0;
int j = weightList.length-1;
while (i <= j) {
// When only one child remains
if (i == j) {
if (weightList[i] <= MAX_WEIGHT) {
numBoats++;
}
break;
}
/**
* Check sum of both ends, and if sum is less than max weight,
* place both on same boat.
*/
if (weightList[i] + weightList[j] <= MAX_WEIGHT) {
// Handled both lighter/heavier kid, so decrement
i++;
j--;
numBoats++;
// Check if heavier rider must fit in his own boat.
} else {
if (weightList[j] <= MAX_WEIGHT) {
numBoats++;
}
// Handled heavier kid
j--;
}
}
return numBoats;
}
}
```

Came up with a better solution or have a question? Comment below!

Next Challenge: First 100 of Fibonacci