4. Last Moment Before All Ants Fall Out of a Plank.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	Arrays Simulation

🚀 4. Last Moment Before All Ants Fall Out of a Plank 🐜

The problem can be found at the following link: Problem Link

💡 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++)

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& 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)

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)

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. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count