# Last Moment Before All Ants Fall Out of a Plank
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/last-moment-before-all-ants-fall-out-of-a-plank)
Canonical: https://scaleengineer.com/dsa/problems/last-moment-before-all-ants-fall-out-of-a-plank
**Data structures:** Array
---
## Problem
We have a wooden plank of the length `n` **units**. Some ants are walking on the plank, each ant moves with a speed of **1 unit per second**. Some of the ants move to the **left**, the other move to the **right**.

When two ants moving in two **different** directions meet at some point, they change their directions and continue moving again. Assume changing directions does not take any additional time.

When an ant reaches **one end** of the plank at a time `t`, it falls out of the plank immediately.

Given an integer `n` and two integer arrays `left` and `right`, the positions of the ants moving to the left and the right, return _the moment when the last ant(s) fall out of the plank_.

**Example 1:**

![](https://assets.glich.co/dsa/last-moment-before-all-ants-fall-out-of-a-plank/image0.jpg) 

**Input:** n = 4, left = [4,3], right = [0,1]
**Output:** 4
**Explanation:** In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

**Example 2:**

![](https://assets.glich.co/dsa/last-moment-before-all-ants-fall-out-of-a-plank/image1.jpg) 

**Input:** n = 7, left = [], right = [0,1,2,3,4,5,6,7]
**Output:** 7
**Explanation:** All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

**Example 3:**

![](https://assets.glich.co/dsa/last-moment-before-all-ants-fall-out-of-a-plank/image2.jpg) 

**Input:** n = 7, left = [0,1,2,3,4,5,6,7], right = []
**Output:** 7
**Explanation:** All ants are going to the left, the ant at index 7 needs 7 seconds to fall.

**Constraints:**

* `1 <= n <= 104`
* `0 <= left.length <= n + 1`
* `0 <= left[i] <= n`
* `0 <= right.length <= n + 1`
* `0 <= right[i] <= n`
* `1 <= left.length + right.length <= n + 1`
* All values of `left` and `right` are unique, and each value can appear **only in one** of the two arrays.

# Approaches
## Brute-Force Simulation
This approach involves simulating the movement of each ant over time. We would maintain the current position and direction of every ant. Instead of stepping one second at a time, a more robust simulation would calculate the time until the next 'event' (a collision or an ant falling off). We would then advance time by that amount and update the state of the system. The simulation continues until the plank is empty, and the total elapsed time is the answer.
**Time:** O((L+R)^3) or worse. In each step of the simulation (of which there can be many), we might need to check all pairs for collisions. This makes the approach infeasible for the given constraints. · **Space:** O(L+R) to store the state (position and direction) of all ants, where L and R are the lengths of the input arrays.
**Pros:** Conceptually follows the problem description directly.
**Cons:** Extremely inefficient. The time complexity would be very high, likely `O(T * (L+R)^2)` where `T` is the final time, and `L` and `R` are the number of ants. This will not pass the given constraints.; Complex to implement correctly. Handling collisions, especially multiple ants colliding at the same point, is tricky.; The simulation needs to handle continuous time, not just discrete steps, which adds another layer of complexity (e.g., calculating the exact time of the next event).
### Explanation
We can model the plank and the ants. Each ant has a position and a direction.
The simulation proceeds by finding the next event:
1.  For each ant, calculate the time it would take to fall off the plank if it doesn't collide with any other ant.
2.  For each pair of ants moving towards each other, calculate the time it would take for them to collide.
3.  The next event time is the minimum of all these calculated times.
4.  Advance the simulation clock by this minimum time and update all ant positions.
5.  Resolve the event: if it was a collision, swap the directions of the involved ants. If an ant reached an end, remove it from the simulation.
6.  Repeat this process until no ants are left on the plank.
This method is conceptually straightforward but computationally very expensive and complex to implement correctly, especially handling simultaneous events.

```java
// This is a conceptual representation and would be very complex to implement fully and efficiently.
// A full, correct implementation is non-trivial and would likely exceed time limits.
class Ant {
    double position;
    int direction; // -1 for left, 1 for right
    Ant(double pos, int dir) {
        this.position = pos;
        this.direction = dir;
    }
}

public int getLastMomentSimulation(int n, int[] left, int[] right) {
    // A full event-driven simulation is too complex for a typical coding challenge
    // but would be the 'correct' way to simulate. It involves:
    // 1. Creating a list of all ants.
    // 2. In a loop, calculating time to next collision for all pairs and time to fall for all ants.
    // 3. Finding the minimum of these times.
    // 4. Advancing the simulation by that minimum time.
    // 5. Updating all ant positions.
    // 6. Handling the event (swap directions or remove ant).
    // 7. Repeating until no ants are left.
    // This is infeasible under contest constraints.
    return -1; // Placeholder for a complex implementation.
}
```
### Algorithm
- 1. Initialize a list of `Ant` objects, each with a starting position and direction.
- 2. Initialize a time counter to 0.
- 3. Start a loop that continues as long as there are ants on the plank.
- 4. Inside the loop, advance time to the next event (either a collision or an ant falling off). This requires calculating the time for all possible next events and picking the minimum.
- 5. Update the positions of all ants based on the elapsed time.
- 6. Handle the event: if it's a collision, swap the directions of the two ants. If an ant falls off, remove it from the list.
- 7. Once the list of ants is empty, the loop terminates. The final value of the time counter is the answer.

## Logical Deduction (Optimal)
The crucial insight for this problem is how to handle collisions. When two ants moving in opposite directions meet, they reverse direction. However, since the ants are identical, this event is indistinguishable from the ants simply passing through each other and continuing in their original directions. The set of positions occupied by ants at any moment remains the same in both scenarios. This simplifies the problem immensely: we can ignore collisions entirely.
**Time:** O(L + R), where `L` is the length of the `left` array and `R` is the length of the `right` array. We perform a single pass through each array. · **Space:** O(1). We only use a few variables to keep track of the maximum time, regardless of the number of ants.
**Pros:** Extremely efficient and simple.; Avoids all the complexity of simulating collisions.; Solves the problem in a single pass over the input arrays.
**Cons:** Requires a non-obvious logical leap to understand that collisions can be ignored. The direct simulation approach might seem more intuitive at first.
### Explanation
By ignoring collisions, we can treat each ant's journey independently. The time it takes for an ant to fall off the plank only depends on its starting position, its direction, and the plank's length.

- An ant starting at position `p` and moving to the left needs to travel `p` units to reach the left end (position 0). Since the speed is 1 unit/second, this takes `p` seconds.
- An ant starting at position `p` and moving to the right needs to travel `n - p` units to reach the right end (position `n`). This takes `n - p` seconds.

The problem asks for the time when the *last* ant falls off. This is simply the maximum of the times taken for each individual ant to fall off.

Therefore, we need to find the maximum time among all left-moving ants and all right-moving ants.
- The maximum time for a left-moving ant is the time for the one starting furthest from the left end, i.e., `max(p)` for all `p` in the `left` array.
- The maximum time for a right-moving ant is the time for the one starting furthest from the right end, i.e., `max(n - p)` for all `p` in the `right` array.

The final answer is the maximum of these two values.

```java
class Solution {
    public int getLastMoment(int n, int[] left, int[] right) {
        // The time for the last ant to fall off is determined by the ant that has to travel the farthest.
        // When ants collide, they reverse direction. This is equivalent to them passing through each other
        // since the ants are identical. So we can ignore collisions.

        // For ants moving to the left, the time to fall off is their initial position.
        // We need the maximum of these times.
        int maxLeftTime = 0;
        for (int pos : left) {
            maxLeftTime = Math.max(maxLeftTime, pos);
        }

        // For ants moving to the right, the time to fall off is (n - their initial position).
        // We need the maximum of these times.
        int maxRightTime = 0;
        for (int pos : right) {
            maxRightTime = Math.max(maxRightTime, n - pos);
        }

        // The last moment is the maximum of the times for the last left-moving ant and the last right-moving ant.
        return Math.max(maxLeftTime, maxRightTime);
    }
}
```
### Algorithm
- 1. Initialize a variable `maxTime` to 0.
- 2. Iterate through the `left` array. For each position `p`, the time for that ant to fall off is `p`. Update `maxTime` to be the maximum of its current value and `p`.
- 3. Iterate through the `right` array. For each position `p`, the time for that ant to fall off is `n - p`. Update `maxTime` to be the maximum of its current value and `n - p`.
- 4. After checking all ants, `maxTime` will hold the time for the last ant to fall off. Return `maxTime`.

# Solutions
### Java

```java
class Solution {
public
  int getLastMoment(int n, int[] left, int[] right) {
    int ans = 0;
    for (int x : left) {
      ans = Math.max(ans, x);
    }
    for (int x : right) {
      ans = Math.max(ans, n - x);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getLastMoment(int n, vector<int> &left, vector<int> &right) {
    int ans = 0;
    for (int &x : left) {
      ans = max(ans, x);
    }
    for (int &x : right) {
      ans = max(ans, n - x);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int: ans = 0 for x in left: ans = max(ans, x) for x in right: ans = max(ans, n - x) return ans

```