Boats to Save People

Approach 1

We can find the optimal solution by pairing the heaviest and lightest passengers together. This will minimize the number of boats required. This can be done by sorting the array first and using a two-pointer approach. Let's discuss the two-pointer approach using the algorithm and dry run for the same.

Algorithm

• Sort the passengers array so that two pointer approach can be used to find the maximum and minimum weight passenger.
   
• Initialize the left and right variables as l = 0 and r = size-1.
   
• Now check for the following conditions and take the given actions.
  
  
  • If passengers[ l ] + passengers[ r ] <= max_weight, then we can transport them on the same boat. Increment the answer variable. Update l = l+1 and r = r-1.
     
  • Else, the total weight of two passengers exceeded the max_weight, and both can't be placed on the same boat. Place only the heavier passenger. Increment the number of boats and update r = r-1.
     
• Repeat this until l<r so that all the passengers are transported.
   
• Check if l=r, i.e. only one passenger is left; Increment the answer. 
   
• Print the least number of boats required.

Dry Run

First, sort the given array. The resultant will look like this.

Now initialize two variables and start checking the conditions.

Iteration 1

Left, l = 0 and right, r = 3. passengers[0] = 1, passengers[3] = 5 

Since passengers[0] + passengers[3] > 5; So only passengers with a weight of 5 can be transported. Update r = 3-1, i.e. 2 and answer = 1.

Iteration 2

Now l = 0 and r = 2. passengers[0] = 1, passengers[2] = 4 

Since passengers[0] + passengers[2] = 5, Both passengers can be transported on the same boat. Update l = 0+1, i.e. 1 and r = 2-1, i.e. 1 and answer = 2.

Iteration 3

Now l = 1 and r = 1, i.e. only one passenger is left.

Simply increment the answer, i.e. answer = 3.

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

int main() {
	int n = 4;
	int max_weight = 5;
	vector<int> passengers = {4, 1, 3, 5};
   
	int answer = 0 ;

	// Sort the input array
	sort(passengers.begin(), passengers.end());

	// Initialize two variables
	int l = 0, r = n-1;

	// Loop until l<r
	while(l<r) {
		if(passengers[l] + passengers[r] <= max_weight) {
			l = l+1;
		}
		r = r-1;
		answer++;
	}

	// single passenger left
	if(l == r) {
		answer++;
	}

	// print the answer
	cout<<"Minimum boats required are: "<< answer << endl;
return 0;
}

Java Implementation

import java.io.*;
import java.util.*;
 
class boats {
	public static void main (String[] args) {
		int n = 4;
		int max_weight = 5;
		int passengers[] = { 4, 1, 3, 5 };

		int answer = 0;

		// Sort the input array
		java.util.Arrays.sort(passengers);

		// Initialize two variables
		int l = 0, r = n-1;
       
		// Loop until l<r
		while(l<r) {
			if(passengers[l] + passengers[r] <= max_weight) {
				l = l+1;
			}
			r = r-1;
			answer++;
		}

		// single passenger left
		if(l == r) {
			answer++;
		}

		// print the answer
		System.out.print("Minimum boats required are: " + answer);
	}
}

Python Implementation

import numpy as np

n = 4
max_weight = 5
passengers = np.array([4,1,3,5])

answer = 0;

# Sort the input array
np.sort(passengers)

# Initialize two variables
l = 0
r = n-1

# Loop until l<r
while(l<r):
	if(passengers[l] + passengers[r] <= max_weight):
		l = l+1
		
	r = r-1;
	answer = answer+1

# single passenger left
if(l == r):
	answer = answer+1
   
# print the answer
print("Minimum boats required are:", end=" ")
print(answer)

Output

Time Complexity

The time complexity for the above solution is O(n* log n), as sorting the array takes n* log n time, and we are traversing the array only once, which will take O(n) time. Therefore overall complexity = O(n + n* log n ) = O(n * log n)

Space Complexity

The array, when sorted, will take log(n) space, so the overall space complexity will be O(log n ), where 'n' represents the number of passengers.

Also see, Euclid GCD Algorithm

Approach 2

The other approach is to use bucket sort to reduce the time complexity. We will create a bucket array and iterate through it using two pointers. This approach will reduce the time complexity to O(max_weight). This might not be that efficient if max_weight is too large.

Algorithm

• Create a bucket array of size max_weight+ 1 and initialize the elements to 0.
   
• Fill the bucket array by incrementing the bucket[ passengers[ i ] ] for i ranging from 0 to n-1.
   
• Initialize the two variables left and right as 0 and max_weight, respectively.
   
• Perform these steps until left <= right.
  
  
  • Increment the left variable until bucket[ left ] <= 0 and left <= right
     
  • Decrement the right variable until bucket[ right ] <= 0 and left <= right
     
  • Break the loop if left > right or both bucket[ right] and bucket[ left ] are 0
     
  • If left + right <= max_weight, we can transport both the passengers with weights left and right. Decrement the bucket[ left ] and bucket[ right ]
     
  • Else, decrement only the bucket[ right ] as only heavy passenger is transported.
     
  • Increment the answer variable as one boat is used to transport passengers
     
• Print the answer as all the passengers are transported.

Dry Run

First, create a bucket array of size max_weight + 1, i.e., 5+1 = 6. Initialize it with zeroes. Now traverse the passengers array and fill the bucket. Also, initialize two variables, left = 0 and right = 5, and start checking the conditions.

Iteration 1

Increment the left variable to 1 as bucket[ left ] = 0.

Now left + right = 6. Since 6 is greater than the max_weight, only the heavy passenger can be transported. So decrement the bucket[ right ] and increment the answer by one. answer = 1, bucket[ right ] = 0.

Iteration 2

Now left = 1 and right = 5. Decrement the right variable as bucket[ right ] = 0. Now right = 4.
 

The sum of left and right = 5, which is equal to the max_weight. Increment the answer, decrement the bucket[ left ] and bucket[ right ]. answer = 2, bucket[ left ] = bucket[ right ] = 0.

Iteration 3

Now left = 1 and right = 4. Increment the left to 2 and decrement the right to 3 since both bucket[ left ] and bucket[ right ] = 0.

Since bucket[ left ] = 0, increment the left variable.

The sum of left and right = 6, which is greater than the max_weight. Decrement the bucket[ right ] and Increment the answer. answer = 3, bucket[ right ] = 0.

Iteration 4

Now left = right = 3.

Increment the left as bucket[ left ] = 0. Break the loop since left > right, so the answer is 3.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n = 4;
	int max_weight = 5;
	vector<int> passengers = {4, 1, 3, 5};

	int answer = 0;

	/*
		Creating bucket of size 'max_weight + 1'.
	*/
	vector<int> bucket(max_weight + 1, 0);

	// Filling the buckets.
	for (int i = 0; i < n; i++) {
		bucket[passengers[i]]++;
	}

	int left = 0, right = max_weight;

	// Iterating over the bucket array.
	while (left <= right) {
		while (left <= right && bucket[left] <= 0) {
			left++;
		}
		while (left <= right && bucket[right] <= 0) {
			right--;
		}
		if (left > right || (bucket[right] == 0 && bucket[left] == 0)) {
			break;  
		}

		if (right + left <= max_weight) {
			bucket[left]--;
			bucket[right]--;
		}
		else {
			bucket[right]--;
		}
		answer++;
	}

	// print the answer
	cout << "Minimum boats required are: " << answer << endl;
	return 0;
}

Java Implementation

import java.io.*;
import java.util.*;
 
class boats {
	public static void main (String[] args) {
		int n = 4;
		int max_weight = 5;
		int passengers[] = { 4, 1, 3, 5 };

		int answer = 0;

		/*
			Creating bucket of size 'max_weight + 1'.
		*/
		int[] bucket = new int[max_weight + 1];
       
		// Filling the buckets.
		for (int i = 0; i < n; i++) {
			bucket[passengers[i]]++;
		}
       
		int left = 0, right = max_weight;

		// Iterating over the bucket array.
		while (left <= right) {
			while (left <= right && bucket[left] <= 0) {
				left++;
			}
			while (left <= right && bucket[right] <= 0) {
				right--;
			}
			if (left > right || (bucket[right] == 0 && bucket[left] == 0)) {
				break;  
			}

			if (right + left <= max_weight) {
				bucket[left]--;
				bucket[right]--;
			}
			else {
				bucket[right]--;
			}
			answer++;
		}

		// print the answer
		System.out.print("Minimum boats required are: " + answer);
	}
}

Python Implementation

import array as arr
import numpy as np

n = 4
max_weight = 5
passengers = arr.array('i', [4, 1, 3, 5])

'''Creating bucket of size 'max_weight + 1'.
'''
bucket = np.zeros(max_weight+1)
answer = 0;

# Filling the buckets
for i in passengers:
	bucket[i] = bucket[i] + 1

left = 0
right = max_weight

# Iterating over the bucket array
while (left <= right):
	while (left <= right and bucket[left] <= 0):
		left = left+1

	while (left <= right and bucket[right] <= 0):
		right = right-1

	if (left > right or (bucket[right] == 0 and bucket[left] == 0)):
		break

	if (right + left <= max_weight):
		bucket[left] = bucket[left]-1
		bucket[right] = bucket[right]-1
	else:
		bucket[right] = bucket[right]-1

	answer = answer+1

# print the answer
print("Minimum boats required are:", end=" ")
print(answer)

Output

Time Complexity

The time complexity for the above solution is O( max(n, max_weight) ), where n represents the number of passengers and max_weight is the maximum weight of a passenger since we are traversing the passengers array and bucket array once, so the time taken will be maximum of lengths of both.

Space Complexity

The overall space complexity will be O(max_weight), as we use a bucket array of size max_weight + 1.

Also check out - Inorder Predecessor

Frequently Asked Questions

What is an Array?

An array data structure consists of a collection of elements, each of which is identified by at least one array index or key. An array is stored so that the position of the individual elements can be calculated using a mathematical formula.

What is a Greedy algorithm?

A greedy algorithm is an algorithm that optimizes the solution at each step. It aims to find the best possible solution at every iteration. It does not consider the consequences of the current choice on further steps.

Is Backtracking better than the Greedy algorithm?

This depends on the problem and its constraints. A greedy algorithm is easy to understand, and it is much more efficient. But it may not always produce the optimal solution. In contrast, backtracking explores all possible solutions to find the optimal one.

What are the advantages of Greedy algorithms?

The greedy algorithms are a much more efficient algorithm. They are easier to understand and can be applied to various problems. They are used to find the best possible solution at each step. They provide an optimal solution for subproblems.

What is a Bucket sort algorithm?

Bucket sort is used to sort the elements of an array by placing them into buckets based on their value. The elements are distributed into buckets, and each bucket is then sorted individually. It is efficient for sorting large-size arrays.

Conclusion

In the article, we have understood a famous coding problem, 'Boats to Save People'. We have seen two approaches, the brute force and the optimized method, for the same. We have discussed the dry run and have implemented the same. We have also analyzed the time and space complexity for both.

To solve more such problems, you can check out our other blogs:

• Count pairs (i, j) from the given array such that i K * arr[j]
• Next greater/smaller elements using an array
• Check if reversing a sub-array makes the array sorted
• The intersection of two arrays

 

To learn more about Data Structures and Algorithms, you can enroll in our course on DSA in Java.

Happy Learning, Ninjas!