# Maximum Containers on a Ship
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-containers-on-a-ship)
Canonical: https://scaleengineer.com/dsa/problems/maximum-containers-on-a-ship
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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 <= 1000`
* `1 <= w <= 1000`
* `1 <= maxWeight <= 109`

# Approaches
## Iterative Simulation
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.
**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.
**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`.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Calculate the total number of cells available: `totalCells = n * n`.
- Initialize a counter for the number of containers: `numContainers = 0`.
- Loop from `i = 1` to `totalCells`.
- Inside the loop, check if the total weight of `i` containers (`i * w`) is less than or equal to `maxWeight`.
- If `i * w <= maxWeight`, it means we can successfully load `i` containers. We update `numContainers = i`.
- If `i * w > maxWeight`, we cannot load `i` containers. The maximum we could load is `i - 1`. We can break the loop immediately.
- After the loop finishes, `numContainers` holds the maximum possible number of containers. Return `numContainers`.

## Direct Mathematical Calculation
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.
**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.
**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.
### Explanation
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`.

```java
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);
    }
}
```
### Algorithm
- Calculate the maximum number of containers limited by space: `maxBySpace = n * n`. It's good practice to use a `long` type for this calculation to avoid potential overflow, although with `n <= 1000`, an `int` would 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 to `int`.

# Solutions
### Java

```java
class Solution {
public
  int maxContainers(int n, int w, int maxWeight) {
    return Math.min(n * n * w, maxWeight) / w;
  }
}

```

### CPP

```cpp
class Solution { public: int maxContainers ( int n , int w , int maxWeight ) { return min ( n * n * w , maxWeight ) / w ; } };
```

### Python

```python
class Solution:
    def maxContainers(self, n: int, w: int,
                      maxWeight: int) -> int: return min(n * n * w, maxWeight) // w

```