Skip to main content
Talentd

Last Moment Before All Ants Fall Out of a Plank - Solution & Explanation

MediumArrayBrainteaserSimulation15 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 104
  • 0 <= left.length <= n + 1
  • 0 <= left[i] <= n
  • 0 <= right.length <= n + 1
  • 0 <= right[i] <= n
  • 1 <= left.length + right.length <= n + 1
  • All values of left and right are unique, and each value can appear only in one of the two arrays.

Approach Overview

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 1: Simulate Ants Without Interaction

The direction change upon collision does not affect the final time an ant falls off. Therefore, the problem simplifies to determining the maximum time taken by any single ant to reach an edge and fall.

This solution loops through both the 'left' and 'right' arrays, calculating the maximum time required for both left-moving and right-moving ants to fall off. It calculates the time for left ants to reach position 0 and for right ants to reach position n, updating the maximum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m + k), where m and k are the sizes of the 'left' and 'right' arrays respectively.
Space Complexity: O(1), since we are using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Using Symmetry of Ants Simulation

In this approach, consider the fact that when two ants collide and change directions, it is equivalent to them passing through each other unaffected. Hence, it suffices to only measure how long it takes ants to fall off the plank.

This solution separately calculates the maximum times taken for ants from the left and right arrays to fall off the plank. It then utilizes a conditional check to determine the greater time value.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m + k) since we traverse both input arrays once.
Space Complexity: O(1) due to no extra memory required except primitives.

Try this approach in the editor →

Approach 3: Brain Teaser

The key point of the problem is that when two ants meet and then turn around, it is equivalent to the two ants continuing to move in their original directions. Therefore, we only need to find the maximum distance moved by any ant.

Note that the lengths of the left and right arrays may be 0.

The time complexity is O(n), where n is the length of the plank. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulate Ants Without Interaction

Time Complexity: O(m + k), where m and k are the sizes of the 'left' and 'right' arrays respectively.
Space Complexity: O(1), since we are using a constant amount of extra space.

Using Symmetry of Ants Simulation

Time Complexity: O(m + k) since we traverse both input arrays once.
Space Complexity: O(1) due to no extra memory required except primitives.

Brain Teaser—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate Ants Without InteractionO(n)O(1)When you want a straightforward calculation of fall times without modeling collisions
Using Symmetry of Ants SimulationO(n)O(1)Preferred interview solution that leverages the collision symmetry insight

Video Solution

Last Moment Before All Ants Fall Out of a Plank | Easy Explanation | GOOGLE | Leetcode - 1503 • codestorywithMIK • 6,300 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Last Moment Before All Ants Fall Out of a Plank easy or hard?
The problem is rated Medium because the implementation is simple but the key insight is not immediately obvious. Many candidates initially attempt a full simulation of collisions, which is unnecessary. Recognizing the symmetry that ants effectively pass through each other leads to the optimal O(n) solution.
Last Moment Before All Ants Fall Out of a Plank Python/Java solution
Python and Java implementations typically iterate through the left array to compute max(left) and through the right array to compute max(n - position). The final answer is the maximum of those two values. Both implementations run in O(n) time and use O(1) extra space.
How to solve Last Moment Before All Ants Fall Out of a Plank in O(n)?
Iterate through the ants moving left and track the maximum position value, since that is the time needed to fall from the left edge. Then iterate through ants moving right and track the maximum value of n - position. The result is the larger of these two maximums. This avoids collision simulation and completes in linear time.
What is the best approach for Last Moment Before All Ants Fall Out of a Plank?
The best approach uses the symmetry observation that ant collisions are equivalent to ants passing through each other. Instead of simulating direction changes, compute the farthest time any ant needs to reach an edge. For ants moving left the time is position, and for ants moving right the time is n - position. The maximum of these values gives the answer in O(n) time and O(1) space.
Is Last Moment Before All Ants Fall Out of a Plank asked at Google/Amazon/Meta?
Problems based on collision symmetry and simplified simulation frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. The question tests logical reasoning and the ability to recognize when a complex simulation can be simplified with a mathematical insight.
What data structure is used in Last Moment Before All Ants Fall Out of a Plank?
The problem primarily uses arrays to store the positions of ants moving left and right. No advanced data structures are required. The algorithm performs a simple linear scan while tracking the maximum fall time.
What is the time complexity of Last Moment Before All Ants Fall Out of a Plank?
The optimal solution runs in O(n) time where n is the number of ants. You scan the left-moving and right-moving arrays once to compute the farthest distance to an edge. Space complexity is O(1) because only a few variables are needed to track the maximum time.

Ready to solve this problem?

Practice Last Moment Before All Ants Fall Out of a Plank with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Collisions on a Road

Next

Movement of Robots