Maximum Containers on a Ship
EasyPrompt
You are given a positive integer n representing an n x n cargo deck on a ship. Each cell on the deck can hold one container with a weight of exactly w.
However, the total weight of all containers, if loaded onto the deck, must not exceed the ship's maximum weight capacity, maxWeight.
Return the maximum number of containers that can be loaded onto the ship.
Example 1:
Input: n = 2, w = 3, maxWeight = 15
Output: 4
Explanation:
The deck has 4 cells, and each container weighs 3. The total weight of loading all containers is 12, which does not exceed maxWeight.
Example 2:
Input: n = 3, w = 5, maxWeight = 20
Output: 4
Explanation:
The deck has 9 cells, and each container weighs 5. The maximum number of containers that can be loaded without exceeding maxWeight is 4.
Constraints:
1 <= n <= 10001 <= w <= 10001 <= maxWeight <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process of loading containers one by one onto the ship's deck. We start with zero containers and iteratively check if adding one more container is feasible. A container can be added only if there is still physical space on the deck and if adding it does not cause the total weight to exceed the ship's maximum weight capacity. We continue this process until we can no longer add any more containers.
Algorithm
- Calculate the total number of cells available:
totalCells = n * n. - Initialize a counter for the number of containers:
numContainers = 0. - Loop from
i = 1tototalCells. - Inside the loop, check if the total weight of
icontainers (i * w) is less than or equal tomaxWeight. - If
i * w <= maxWeight, it means we can successfully loadicontainers. We updatenumContainers = i. - If
i * w > maxWeight, we cannot loadicontainers. The maximum we could load isi - 1. We can break the loop immediately. - After the loop finishes,
numContainersholds the maximum possible number of containers. ReturnnumContainers.
Walkthrough
The algorithm maintains a count of the containers currently loaded. It iterates from 1 up to the total number of cells on the deck (n * n). In each step, it calculates the potential total weight if one more container were to be added. The loop stops when either all cells are filled or the weight limit would be exceeded by adding another container. The final count is the maximum number of containers.
class Solution { public int maxContainers(int n, int w, int maxWeight) { long totalCells = (long) n * n; int numContainers = 0; for (int i = 1; i <= totalCells; i++) { // Use long for weight calculation to prevent overflow if ((long) i * w <= maxWeight) { numContainers = i; } else { // Weight limit exceeded, break the loop break; } } return numContainers; }}Complexity
Time
O(min(n*n, maxWeight/w)). The loop iterates up to `n*n` times, but it can terminate early if the weight limit is reached. The number of iterations is determined by the smaller of the two constraints: the total number of cells (`n*n`) or the maximum number of containers allowed by weight (`maxWeight/w`). In the worst case, this can be up to `1000*1000 = 1,000,000` iterations.
Space
O(1). We only use a few variables to store the counts and intermediate values, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement as it directly models the physical process.
Cons
Inefficient for large inputs. The loop can perform up to a million iterations, which is much slower than a direct calculation.
Prone to timeout errors on platforms with strict time limits for larger values of
n.
This is the most efficient approach. It solves the problem by directly calculating the maximum number of containers allowed by each constraint and then taking the minimum of the two. The problem has two independent constraints: the physical space on the deck and the maximum weight capacity of the ship.
Algorithm
- Calculate the maximum number of containers limited by space:
maxBySpace = n * n. It's good practice to use alongtype for this calculation to avoid potential overflow, although withn <= 1000, anintwould suffice. - Calculate the maximum number of containers limited by weight:
maxByWeight = maxWeight / w. Integer division automatically handles the floor operation. - The result is the minimum of these two values:
Math.min(maxBySpace, maxByWeight). - Since the function should return an
int, we cast the final result back toint.
Walkthrough
First, we determine the maximum number of containers that can fit on the n x n deck. Since each cell can hold one container, the maximum is simply the total number of cells, which is n * n. Let's call this maxBySpace.
Second, we determine the maximum number of containers that can be loaded without exceeding the maxWeight. Each container weighs w. If we load k containers, the total weight is k * w. This must be less than or equal to maxWeight. So, k * w <= maxWeight, which implies k <= maxWeight / w. The maximum integer k satisfying this is floor(maxWeight / w). In integer arithmetic, this is simply maxWeight / w. Let's call this maxByWeight.
The actual maximum number of containers must satisfy both the space and weight constraints. Therefore, the answer is the minimum of maxBySpace and maxByWeight.
class Solution { public int maxContainers(int n, int w, int maxWeight) { // Calculate maximum containers based on deck space long maxBySpace = (long) n * n; // Calculate maximum containers based on weight capacity long maxByWeight = maxWeight / w; // The result is the minimum of the two constraints return (int) Math.min(maxBySpace, maxByWeight); }}Complexity
Time
O(1). The solution involves a fixed number of arithmetic operations (multiplication, division, and finding the minimum), which execute in constant time, regardless of the input values.
Space
O(1). The memory usage is constant as we only need a few variables to store the intermediate and final results.
Trade-offs
Pros
Extremely efficient, providing an instant solution.
Optimal in terms of both time and space complexity.
Elegant and concise.
Cons
Requires a small amount of mathematical insight to derive the formula, rather than just simulating the process.
Solutions
Solution
class Solution {public int maxContainers(int n, int w, int maxWeight) { return Math.min(n * n * w, maxWeight) / w; }}class Solution { public: int maxContainers ( int n , int w , int maxWeight ) { return min ( n * n * w , maxWeight ) / w ; } };class Solution: def maxContainers(self, n: int, w: int, maxWeight: int) -> int: return min(n * n * w, maxWeight) // wVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.