1503. Last Moment Before All Ants Fall Out of a Plank

Time: O(n)

Space: O(1)

Intuition

Simulate race. Last car in position n-1. It can be blocked by slower car ahead. Compute time for each car to reach the end, block means they form a fleet.

Algorithm

1Process from right to left. Each car moves toward finish. If car catches up to car ahead, they move together (blocked).
2Actually: time[i] = (target - position[i]) / speed[i]. Count collisions going right to left.

Common Pitfalls

•Cars catch up when time_behind < time_ahead. Use simulation or stack-based approach.

1503.cs

// Approach: Key insight — when two ants meet they effectively pass through each other.
// So ants moving left take max(left) time; ants moving right take n - min(right) time.
// Return the maximum of these two values.
// Time: O(n) Space: O(1)
public class Solution
{
    public int GetLastMoment(int n, int[] left, int[] right)
    {
        int maxLeft = left.Length == 0 ? 0 : left.Max();
        int minRight = right.Length == 0 ? n : right.Min();
        return Math.Max(maxLeft, n - minRight);
    }
}

Was this solution helpful?