Last Moment Before All Ants Fall Out

Time: O(n)

Space: O(1)

Intuition

Ants on a plank walk to edges; when they collide they reverse. Key insight: collision = pass-through. Answer = max distance any ant travels.

Algorithm

1Ignore collisions (ants just pass through). Max time = max(max(left_positions), max(n - right_positions)).

Common Pitfalls

•Same as LC 1503. Collision = pass-through trick. Just find the ant that takes longest to reach its end.

Last Moment Before All Ants Fall Out.java

Java

// Approach: Ants colliding effectively pass through each other. Max time = max of (max left ant, n - min right ant).
// Time: O(n) Space: O(1)
class Solution {
    public int getLastMoment(int n, int left[], int right[]) {
        // Find maximum distance for ants moving left (from their position to left edge)
        int maxLeftDistance = 0;
        for (int position : left)
            maxLeftDistance = Math.max(maxLeftDistance, position);

        // Find maximum distance for ants moving right (from their position to right
        // edge)
        int maxRightDistance = 0;
        for (int position : right)
            maxRightDistance = Math.max(maxRightDistance, n - position);

        // The last ant to fall will be the one with the maximum distance to travel
        return Math.max(maxLeftDistance, maxRightDistance);
    }
}

Was this solution helpful?