Watch 10 video solutions for Last Moment Before All Ants Fall Out of a Plank, a medium level problem involving Array, Brainteaser, Simulation. This walkthrough by codestorywithMIK has 6,000 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
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:
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 <= 1040 <= left.length <= n + 10 <= left[i] <= n0 <= right.length <= n + 10 <= right[i] <= n1 <= left.length + right.length <= n + 1left and right are unique, and each value can appear only in one of the two arrays.Problem Overview: You have a plank of length n with ants walking either left or right. Each ant moves at the same speed. When two ants meet, they turn around and keep walking. The task is to compute the last moment when any ant falls off the plank.
Approach 1: Simulate Ants Without Interaction (O(n) time, O(1) space)
A direct simulation idea focuses on when each ant reaches the nearest edge. Ants moving left fall after position seconds, while ants moving right fall after n - position seconds. Instead of simulating collisions, you iterate through the array of positions and compute these times. The final answer is simply the maximum fall time among all ants. This works because every ant moves at a constant speed and the only thing that matters is its distance to the edge it is heading toward.
Approach 2: Using Symmetry of Ants Simulation (O(n) time, O(1) space)
The key insight is that when two ants collide and turn around, the result is identical to them passing through each other while keeping their original directions. Since ants are indistinguishable, the swap of directions produces the same overall positions over time. This symmetry removes the need for collision handling entirely. You simply treat each ant as moving straight toward its respective edge and compute the maximum of max(left) and max(n - right). The approach turns what looks like a simulation problem into a simple linear scan.
This observation is a classic brainteaser. The challenge is not implementing movement but recognizing that collisions don't change the total fall time. Once you realize the symmetry, the solution becomes a single pass through the input.
Recommended for interviews: Interviewers expect the symmetry insight. A brute mental model of ants bouncing around shows you understand the scenario, but the optimal solution recognizes that collisions are equivalent to ants passing through each other. That reduces the problem to computing the farthest distance an ant must travel to an edge, giving an O(n) time and O(1) space solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Ants Without Interaction | O(n) | O(1) | When you want a straightforward calculation of fall times without modeling collisions |
| Using Symmetry of Ants Simulation | O(n) | O(1) | Preferred interview solution that leverages the collision symmetry insight |