---
Difficulty: Medium
Source: 160 Days of Problem Solving (BONUS PROBLEMS π)
Tags:
- Arrays
- Simulation
---
# π _4. Last Moment Before All Ants Fall Out of a Plank_ π
The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/array-bonus-problems/problem/last-moment-before-all-ants-fall-out-of-a-plank)
## π‘ **Problem Description:**
We have a wooden plank of length `n` units. Some ants are walking on the plank, each moving at a speed of `1` unit per second.
- Ants in the `left[]` array are moving to the left.
- Ants in the `right[]` array are moving to the right.
When two ants collide, they simply reverse their directions and continue moving. Collisions don't impact the overall result because reversing directions is equivalent to swapping identities.
The task is to find the time at which the **last ant** falls off the plank.
### Constraints:
- $1 \leq n \leq 10^5$
- $0 \leq \text{left.length}, \text{right.length} \leq n + 1$
- $0 \leq \text{left}[i], \text{right}[i] \leq n$
- $1 \leq \text{left.length} + \text{right.length} \leq n + 1$
- All values of `left` and `right` are unique.
## π **Example Walkthrough:**
**Input:**
```
n = 4
left[] = [2]
right[] = [0, 1, 3]
```
**Output:**
```
4
```
**Explanation:**
The ant at position `2` takes `2` seconds to fall off the left end. The ant at position `3` takes `1` second to fall off the right end, and so on. The last ant to fall does so at `t = 4`.
**Input:**
```
n = 4
left[] = []
right[] = [0, 1, 2, 3, 4]
```
**Output:**
```
4
```
**Explanation:**
All ants are moving to the right. The ant at position `0` takes `4` seconds to fall off the plank.
**Input:**
```
n = 3
left[] = [0]
right[] = [3]
```
**Output:**
```
0
```
**Explanation:**
The ants are already at the edges of the plank and fall off immediately.
## π― **My Approach:**
1. **Observation:**
- The time it takes for an ant in the `left[]` array to fall off the plank is equal to its position.
- The time it takes for an ant in the `right[]` array to fall off the plank is `n - pos`, where `pos` is the position of the ant.
- Collisions do not affect the result because the ants' movement post-collision is equivalent to their original behavior.
2. **Calculate the Last Moment:**
- For ants moving left, find the maximum position (`max(left[])`) as they will take the longest to fall off.
- For ants moving right, find the maximum of `n - pos` for all positions in `right[]`.
- The result is the maximum of these two values.
## π **Time and Auxiliary Space Complexity**
- **Time Complexity:** O(L + R), where `L` is the size of `left[]` and `R` is the size of `right[]`. The algorithm involves iterating over both arrays once.
- **Space Complexity:** O(1), as no additional space is used apart from variables for computation.
## π **Solution Code**
### Code (C++)
```cpp
class Solution {
public:
int getLastMoment(int n, vector& left, vector& right) {
int lastMoment = 0;
for (int pos : left) {
lastMoment = max(lastMoment, pos);
}
for (int pos : right) {
lastMoment = max(lastMoment, n - pos);
}
return lastMoment;
}
};
```
### Code (Java)
```java
class Solution {
public int getLastMoment(int n, int[] left, int[] right) {
int lastMoment = 0;
for (int pos : left) {
lastMoment = Math.max(lastMoment, pos);
}
for (int pos : right) {
lastMoment = Math.max(lastMoment, n - pos);
}
return lastMoment;
}
}
```
### Code (Python)
```python
class Solution:
def getLastMoment(self, n, left, right):
lastMoment = 0
for pos in left:
lastMoment = max(lastMoment, pos)
for pos in right:
lastMoment = max(lastMoment, n - pos)
return lastMoment
```
## π― Contribution and Support:
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
---
πVisitor Count
