Boats to Save People - Practice Coding Problems

Boats to Save People - Problem

You are given an array people where people[i] is the weight of the i-th person, and an infinite number of boats where each boat can carry a maximum weight of limit.

Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

Input & Output

Example 1 — Basic Pairing

$ Input: people = [1,2], limit = 3

› Output: 1

💡 Note: Both people can fit in one boat: 1 + 2 = 3 ≤ 3, so we need only 1 boat total

Example 2 — Mixed Pairing

$ Input: people = [3,2,2,1], limit = 3

› Output: 3

💡 Note: After sorting [1,2,2,3]: pair (1,2)→boat 1, remaining 2 and 3 need separate boats since 2+3>3

Example 3 — No Pairing Possible

$ Input: people = [5,5,5,5], limit = 5

› Output: 4

💡 Note: Each person weighs exactly the limit, so each needs their own boat. Total: 4 boats

Constraints

1 ≤ people.length ≤ 5 × 10⁴
1 ≤ people[i] ≤ limit ≤ 3 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of people weights and boat weight limit

Process

Sort and use greedy pairing with two pointers

Output

Minimum number of boats required

Key Takeaway

🎯 Key Insight: Greedy pairing of lightest with heaviest people minimizes total boats needed

Asked in

a Amazon 45 G Google 32 f Facebook 28 M Microsoft 24

The key insight is using a greedy two-pointer approach after sorting. Always try to pair the lightest remaining person with the heaviest - this guarantees optimal boat usage. Best approach is Two Pointers with Sorting. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Sorting	O(n log n)	O(1)	Sort people by weight, then greedily pair lightest with heaviest when possible
Brute Force - Try All Combinations	O(2ⁿ)	O(n)	Generate all possible ways to group people into boats and find minimum
Two Pointers Optimization	O(n log n)	O(1)	Sort and use two pointers from ends to optimally pair people

Greedy with Sorting — Algorithm Steps

Sort people by weight in ascending order
Use two pointers: left (lightest) and right (heaviest)
Try to pair left and right person in same boat
If they fit together, move both pointers; otherwise only move right pointer
Count boats needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Arrange people by weight: [1,2,2]

Two Pointers

Left at lightest, right at heaviest

Greedy Pairing

Try to fit both, else just take heaviest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* people, int n, int limit) {
    qsort(people, n, sizeof(int), compare);
    int left = 0, right = n - 1;
    int boats = 0;
    
    while (left <= right) {
        if (left == right) {
            boats++;
            break;
        }
        
        if (people[left] + people[right] <= limit) {
            left++;
        }
        right--;
        boats++;
    }
    
    return boats;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int people[100];
    int n = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        people[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int limit;
    scanf("%d", &limit);
    
    int result = solution(people, n, limit);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting dominates with O(n log n), then O(n) for two-pointer traversal

⚡ Linearithmic

Space Complexity

O(1)

Only using two pointer variables, sorting in-place

✓ Linear Space

186.7K Views

Medium Frequency

~15 min Avg. Time

3.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler