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.
Solutions
Solution
class Solution {public int maxContainers(int n, int w, int maxWeight) { return Math.min(n * n * w, maxWeight) / w; }}Video 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.