LeetCode 3492 - Maximum Containers on a Ship

This problem describes a cargo ship with an n × n deck. Since each cell on the deck can hold exactly one container, the deck has a total capacity of: physical container positions. Every container has the same weight, w. The ship also has a maximum total weight limit, maxWeight.

leetcodeeasymath

LeetCode Problem 3492

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

This problem describes a cargo ship with an n × n deck. Since each cell on the deck can hold exactly one container, the deck has a total capacity of:

$$n^2$$

physical container positions.

Every container has the same weight, w. The ship also has a maximum total weight limit, maxWeight. Even if the deck has enough space, we cannot load containers whose combined weight exceeds this limit.

The goal is to determine the maximum number of containers that can be loaded while satisfying both constraints:

  1. The number of containers cannot exceed the number of deck cells, n².
  2. The total weight cannot exceed maxWeight.

If we load k containers, their total weight is:

$$k \times w$$

Therefore, the largest valid value of k must satisfy:

$$k \times w \le maxWeight$$

and

$$k \le n^2$$

The output is the maximum possible value of k.

The constraints are relatively small for n:

  • 1 <= n <= 1000
  • 1 <= w <= 1000
  • 1 <= maxWeight <= 10^9

Since n² is at most 1,000,000, and all calculations fit comfortably within standard integer ranges, this problem is fundamentally a mathematical observation problem rather than a simulation problem.

Important edge cases include situations where the deck has far more space than the weight limit allows, situations where the weight limit is large enough to fill the entire deck, and the smallest possible input values. The problem guarantees that all inputs are positive integers, so division by zero is never a concern.

Approaches

Brute Force

A straightforward approach is to try loading containers one at a time.

Start with zero containers and keep adding another container as long as:

  • There is still an empty deck cell.
  • Adding another container does not exceed maxWeight.

Eventually, either the deck becomes full or the weight limit is reached. The number of successfully loaded containers is the answer.

This approach is correct because it explicitly simulates the loading process and stops exactly when another container would violate a constraint.

However, it is unnecessarily expensive. In the worst case, the deck may contain up to n² = 1,000,000 cells, meaning we could perform up to one million iterations just to compute a value that can be obtained directly through arithmetic.

Optimal Mathematical Observation

The key observation is that the two constraints are independent:

The deck can physically hold at most:

$$n^2$$

containers.

The weight limit allows at most:

$$\left\lfloor \frac{maxWeight}{w} \right\rfloor$$

containers.

The actual answer must satisfy both constraints simultaneously, so it is simply the smaller of these two values:

$$\min\left(n^2,\left\lfloor\frac{maxWeight}{w}\right\rfloor\right)$$

This eliminates any need for iteration and produces the answer in constant time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Simulates loading containers one by one
Optimal O(1) O(1) Uses direct mathematical computation

Algorithm Walkthrough

  1. Compute the total number of deck cells.

Since the deck is an n × n grid, the maximum number of containers that can physically fit is:

$$deckCapacity = n^2$$ 2. Compute the maximum number of containers allowed by weight.

Each container weighs w, so the number of containers that can be loaded before exceeding the weight limit is:

$$weightCapacity = \left\lfloor \frac{maxWeight}{w} \right\rfloor$$

Integer division naturally performs this floor operation. 3. Take the smaller of the two capacities.

Even if the deck has room for more containers, the weight limit may stop us earlier. Similarly, even if the weight limit allows more containers, the deck may run out of space.

Therefore:

$$answer = \min(deckCapacity, weightCapacity)$$ 4. Return the result.

Why it works

Any valid loading must satisfy both constraints simultaneously. The deck capacity imposes an upper bound of n², while the weight limit imposes an upper bound of ⌊maxWeight / w⌋. Since every feasible solution must be less than or equal to both bounds, the largest feasible solution is exactly the minimum of the two. Therefore the algorithm always returns the maximum possible number of containers. This problem asks us to determine the maximum number of containers that can be loaded onto a square cargo deck of size n x n without exceeding the ship's maximum weight capacity. Each cell on the deck can hold exactly one container, and each container has a fixed weight w. The inputs are n, which defines the total number of cells as n * n, w for the weight of each container, and maxWeight, the maximum allowable weight the ship can carry.

The output is a single integer representing the maximum number of containers that can fit without exceeding maxWeight. This requires considering both the number of cells available and the weight constraint simultaneously. The constraints suggest that the deck size could be up to 1000 x 1000, which is one million cells, and container weights can be up to 1000, with a maximum weight up to one billion. These constraints ensure we cannot rely on any algorithm that examines each potential container individually in a complex way; a direct mathematical calculation is feasible.

Edge cases to consider include when maxWeight is smaller than a single container, resulting in zero containers being loaded, or when the total weight of filling all cells is exactly equal to maxWeight. The problem guarantees all inputs are positive integers.

Approaches

A brute-force approach would attempt to iterate through every cell, adding containers one by one and checking the total weight against maxWeight. While this would produce the correct answer, it is inefficient because in the worst case we could iterate over a million cells, performing arithmetic operations at each step. This is unnecessary because the problem allows a direct computation based on simple math.

The key observation for the optimal solution is that the maximum number of containers is the smaller of two quantities: the total number of cells (n * n) and the maximum number of containers allowed by weight (maxWeight // w). We take the integer division of maxWeight by w to find the number of containers that will not exceed the weight capacity. Then, we simply return the minimum of this value and the total number of available cells.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Iterate over each cell and sum weights until reaching maxWeight
Optimal O(1) O(1) Direct mathematical computation using min(n*n, maxWeight//w)

Algorithm Walkthrough

  1. Compute the total number of cells on the deck by calculating total_cells = n * n. This represents the maximum containers the deck can physically hold.
  2. Compute the maximum number of containers allowed by weight using integer division: max_by_weight = maxWeight // w. This ensures we do not exceed the weight capacity.
  3. Take the minimum of total_cells and max_by_weight to get the final number of containers: result = min(total_cells, max_by_weight).
  4. Return the result.

This works because the problem has only two limiting factors: physical space and total weight. The algorithm ensures we respect both constraints simultaneously.

Python Solution

class Solution:
    def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
        deck_capacity = n * n
        weight_capacity = maxWeight // w
        return min(deck_capacity, weight_capacity)

The implementation directly mirrors the mathematical observation.

First, deck_capacity stores the number of available cells on the deck. Since the deck is square, this is simply n * n.

Next, weight_capacity computes how many containers can be supported by the ship's weight limit. Integer division (//) automatically performs the floor operation required by the formula.

Finally, the answer is the smaller of the two capacities because both constraints must hold simultaneously. total_cells = n * n max_by_weight = maxWeight // w return min(total_cells, max_by_weight)


In this Python implementation, we first calculate the total number of cells, then calculate how many containers can fit within the weight limit. Finally, `min` ensures we do not exceed either the deck capacity or the maximum weight, giving the correct maximum number of containers.

## Go Solution

```go
func maxContainers(n int, w int, maxWeight int) int {
	deckCapacity := n * n
	weightCapacity := maxWeight / w

	if deckCapacity < weightCapacity {
		return deckCapacity
	}

	return weightCapacity
}

The Go implementation follows the exact same logic as the Python solution.

Integer division in Go automatically truncates toward zero for positive integers, which is exactly the floor operation needed for maxWeight / w.

The constraints ensure that n * n is at most 1,000,000, so there is no risk of integer overflow on standard LeetCode platforms. totalCells := n * n maxByWeight := maxWeight / w if totalCells < maxByWeight { return totalCells } return maxByWeight }


In Go, we handle the same calculations explicitly using variables `totalCells` and `maxByWeight`. Go does not have a built-in `min` for integers, so we use an `if` statement to return the smaller of the two values. Otherwise, the logic mirrors the Python implementation.

## Worked Examples

### Example 1

**Input**

n = 2 w = 3 maxWeight = 15


#### Step-by-Step

| Variable | Value |
| --- | --- |
| deckCapacity | 2 × 2 = 4 |
| weightCapacity | 15 // 3 = 5 |
| answer | min(4, 5) = 4 |

**Output**

4


The deck only has four cells, so even though the weight limit would allow five containers, only four can be loaded.

### Example 2

**Input**

n = 3 w = 5 maxWeight = 20


#### Step-by-Step

| Variable | Value |
| --- | --- |
| deckCapacity | 3 × 3 = 9 |
| weightCapacity | 20 // 5 = 4 |
| answer | min(9, 4) = 4 |

**Output**

4


The deck has room for nine containers, but the weight limit only allows four.
Input: `n = 2, w = 3, maxWeight = 15`

Step calculation:

| Step | Calculation | Result |
| --- | --- | --- |
| Total cells | `2 * 2` | 4 |
| Max by weight | `15 // 3` | 5 |
| Minimum | `min(4, 5)` | 4 |

Output: 4

### Example 2

Input: `n = 3, w = 5, maxWeight = 20`

Step calculation:

| Step | Calculation | Result |
| --- | --- | --- |
| Total cells | `3 * 3` | 9 |
| Max by weight | `20 // 5` | 4 |
| Minimum | `min(9, 4)` | 4 |

Output: 4

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(1) | Only a few arithmetic operations are performed |
| Space | O(1) | No additional data structures are used |

The algorithm performs one multiplication, one integer division, and one minimum comparison. None of these operations depend on the size of the input, so the running time is constant. The memory usage is also constant because only a few integer variables are stored.
| Time | O(1) | Only a few arithmetic operations and a comparison are performed, regardless of input size |
| Space | O(1) | Only a constant number of variables are used |

The reasoning is straightforward because the solution uses simple arithmetic and does not iterate over arrays or collections of size `n*n`.

## Test Cases

sol = Solution()

assert sol.maxContainers(2, 3, 15) == 4 # Example 1 assert sol.maxContainers(3, 5, 20) == 4 # Example 2

assert sol.maxContainers(1, 1, 1) == 1 # Smallest valid input assert sol.maxContainers(1, 5, 100) == 1 # Weight allows more, deck limits

assert sol.maxContainers(10, 1, 50) == 50 # Weight limit binds assert sol.maxContainers(10, 1, 100) == 100 # Exactly fills deck

assert sol.maxContainers(10, 1000, 999) == 0 # Cannot load any container assert sol.maxContainers(10, 1000, 1000) == 1 # Exactly one container

assert sol.maxContainers(1000, 1, 109) == 1000000 # Maximum deck size assert sol.maxContainers(1000, 1000, 109) == 1000000 # Weight also allows full deck

assert sol.maxContainers(5, 4, 17) == 4 # Floor division behavior assert sol.maxContainers(4, 7, 100) == 14 # Weight limit smaller than deck


### Test Summary

| Test | Why |
| --- | --- |
| `(2, 3, 15)` | First provided example |
| `(3, 5, 20)` | Second provided example |
| `(1, 1, 1)` | Minimum constraints |
| `(1, 5, 100)` | Single-cell deck |
| `(10, 1, 50)` | Weight constraint limits answer |
| `(10, 1, 100)` | Full deck utilization |
| `(10, 1000, 999)` | Weight too small for any container |
| `(10, 1000, 1000)` | Exactly one container fits |
| `(1000, 1, 10^9)` | Maximum deck size |
| `(1000, 1000, 10^9)` | Large values with full deck usage |
| `(5, 4, 17)` | Verifies floor division |
| `(4, 7, 100)` | General mixed case |

## Edge Cases

### Weight Limit Too Small for Even One Container

Consider:

n = 10 w = 1000 maxWeight = 999


A common mistake is to assume at least one container can always be loaded. In reality:

$$999 // 1000 = 0$$

so no container fits within the weight limit. The formula correctly returns `min(100, 0) = 0`.

### Deck Capacity Is the Limiting Factor

Consider:

n = 2 w = 1 maxWeight = 100


The weight limit would allow one hundred containers, but the deck only contains four cells. The implementation correctly returns:

$$\min(4, 100) = 4$$

ensuring we never exceed the physical capacity of the deck.

### Weight Capacity Is the Limiting Factor

Consider:

n = 100 w = 10 maxWeight = 35


The deck can hold 10,000 containers, but the weight limit allows only:

$$35 // 10 = 3$$

containers. The implementation correctly returns `3`.

### Exact Divisibility by Weight

Consider:

n = 10 w = 5 maxWeight = 20


Since the weight limit is exactly divisible by the container weight:

$$20 // 5 = 4$$

the answer should be exactly four containers, not three. Integer division naturally handles this case correctly.

### Maximum Constraint Values

Consider:

n = 1000 w = 1000 maxWeight = 10^9


Here:

$$n^2 = 1,000,000$$

and

$$10^9 // 1000 = 1,000,000$$

Both limits are equal, so the answer is `1,000,000`. The implementation handles these values safely and efficiently in constant time.
# Provided examples
assert Solution().maxContainers(2, 3, 15) == 4  # Total cells = 4, max by weight = 5
assert Solution().maxContainers(3, 5, 20) == 4  # Total cells = 9, max by weight = 4

# Edge cases
assert Solution().maxContainers(1, 10, 5) == 0  # maxWeight smaller than single container
assert Solution().maxContainers(1, 5, 5) == 1  # maxWeight exactly matches single container
assert Solution().maxContainers(1000, 1, 10**9) == 1000000  # maxWeight larger than all cells
assert Solution().maxContainers(1000, 1000, 1000000) == 1000  # maxWeight limits number of containers
Test Why
n=2, w=3, maxWeight=15 Checks standard case where weight is not limiting
n=3, w=5, maxWeight=20 Checks standard case where weight limits container count
n=1, w=10, maxWeight=5 Tests weight smaller than a single container
n=1, w=5, maxWeight=5 Tests exact weight match for one container
n=1000, w=1, maxWeight=10^9 Tests large deck, weight is not limiting
n=1000, w=1000, maxWeight=10^6 Tests weight limiting number of containers

Edge Cases

The first important edge case occurs when maxWeight is less than the weight of a single container. In this scenario, no containers can be loaded, and the algorithm correctly returns zero because integer division truncates down to zero.

A second edge case is when maxWeight exactly matches the total weight of all possible containers. Here, the algorithm correctly calculates maxWeight // w as equal to n*n, and the min function returns the total deck capacity.

The third edge case is when n is extremely large and maxWeight is extremely large as well. The algorithm handles this efficiently with O(1) operations, avoiding any iteration or large memory allocation, which could otherwise cause performance or overflow issues. The calculation remains accurate due to Python and Go handling large integer arithmetic safely.