Last Moment Before All Ants Fall Out of a Plank solution and explanation
Google
9 more videos on this problem
Last Moment Before All Ants Fall Out of a Plank | Easy Explanation | GOOGLE | Leetcode - 1503codestorywithMIK · 23:50 · 6K views
1503. Last Moment Before All Ants Fall Out of a Plank || General Collision without speed degradationAryan Mittal · 7:00 · 3K views
last moment before all ants fall out of a plank leetcode | leetcode 1503Naresh Gupta · 10:38 · 1K views
1503 LeetCode Last Moment Before All Ants Fall Out of a Plank || FAANGM Interview || Medium problemSanskar Goyal · 12:17 · 1K views
1503. Last Moment Before All Ants Fall Out of a Plank (Leetcode Medium)Programming Live with Larry · 7:02 · 595 views
Last Moment Before All Ants Fall Out of a Plank | Leetcode 1503Competitive Coding · 5:05 · 571 views
Daily Leetcode #1313: Nov 04, 2023 - 1503. Last Moment Before All Ants Fall Out of a PlankProgramming Live with Larry · 9:59 · 523 views
Last Moment Before All Ants Fall Out of a Plank | Решение на Python | LeetCode 1503Сурен Хоренян · 8:02 · 376 views
Last Moment Before All Ants Fall Out of a Plank - LeetCode 1503 - PythonAlpha-Code · 11:50 · 278 views
Solving LeetCode 1503 Last Moment Before All Ants Fall Out of a Plank | Google Interview QuestionCode Harmony · 8:46 · 277 views
The problem
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 + 1- All values of
leftandrightare 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.
def getLastMoment(n, left, right):
max_time = 0
for pos in left:
max_time = max(max_time, pos)
for pos in right:
max_time = max(max_time, n - pos)
return max_time
n = 4
left = [4, 3]
right = [0, 1]
result = getLastMoment(n, left, right)import java.util.*;
public class Solution {
public int getLastMoment(int n, int[] left, int[] right) {
int maxTime = 0;
for (int position : left) { maxTime = Math.max(maxTime, position); }
for (int position : right) { maxTime = Math.max(maxTime, n - position); }
return maxTime;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] left = {4, 3};
int[] right = {0, 1};
int n = 4;
int result = solution.getLastMoment(n, left, right);
}
}#include <vector>
#include <algorithm>
int getLastMoment(int n, std::vector<int>& left, std::vector<int>& right) {
int maxTime = 0;
for (int pos : left) { maxTime = std::max(maxTime, pos); }
for (int pos : right) { maxTime = std::max(maxTime, n - pos); }
return maxTime;
}
int main() {
std::vector<int> left = {4, 3};
std::vector<int> right = {0, 1};
int n = 4;
int result = getLastMoment(n, left, right);
return 0;
}function getLastMoment(n, left, right) {
let maxTime = 0;
left.forEach(pos => { if (pos > maxTime) maxTime = pos; });
right.forEach(pos => { if (n - pos > maxTime) maxTime = n - pos; });
return maxTime;
}
let n = 4;
let left = [4, 3];
let right = [0, 1];
let result = getLastMoment(n, left, right);#include <stdio.h>
int getLastMoment(int n, int* left, int leftSize, int* right, int rightSize) {
int maxTime = 0;
for (int i = 0; i < leftSize; i++) {
if (left[i] > maxTime) maxTime = left[i];
}
for (int i = 0; i < rightSize; i++) {
if (n - right[i] > maxTime) maxTime = n - right[i];
}
return maxTime;
}
int main() {
int n = 4;
int left[] = {4, 3};
int right[] = {0, 1};
int result = getLastMoment(n, left, 2, right, 2);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int GetLastMoment(int n, int[] left, int[] right) {
int maxTime = 0;
foreach (int pos in left) { maxTime = Math.Max(maxTime, pos); }
foreach (int pos in right) { maxTime = Math.Max(maxTime, n - pos); }
return maxTime;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] left = {4, 3};
int[] right = {0, 1};
int n = 4;
int result = solution.GetLastMoment(n, left, right);
}
}In Python, we iterate through the positions provided in both direction arrays to compute the maximum time required for any ant to reach and fall off the plank's edges.
Time Complexity: O(m + k), where m and k are the sizes of the 'left' and 'right' arrays respectively.
Space Complexity: O(1), utilizing constant additional space.
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.
def getLastMoment(n, left, right):
max_time_left = max(left) if left else 0
max_time_right = max(n - r for r in right) if right else 0
return max(max_time_left, max_time_right)
n = 4
left = [4, 3]
right = [0, 1]
result = getLastMoment(n, left, right)import java.util.*;
public class Solution {
public int getLastMoment(int n, int[] left, int[] right) {
int maxTimeLeft = Arrays.stream(left).max().orElse(0);
int maxTimeRight = Arrays.stream(right).map(x -> n - x).max().orElse(0);
return Math.max(maxTimeLeft, maxTimeRight);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] left = {4, 3};
int[] right = {0, 1};
int n = 4;
System.out.println(sol.getLastMoment(n, left, right));
}
}#include <vector>
#include <algorithm>
int getLastMoment(int n, std::vector<int>& left, std::vector<int>& right) {
int maxTimeLeft = !left.empty() ? *std::max_element(left.begin(), left.end()) : 0;
int maxTimeRight = !right.empty() ? n - *std::min_element(right.begin(), right.end()) : 0;
return std::max(maxTimeLeft, maxTimeRight);
}
int main() {
std::vector<int> left = {4, 3};
std::vector<int> right = {0, 1};
int n = 4;
int result = getLastMoment(n, left, right);
return 0;
}function getLastMoment(n, left, right) {
const maxTimeLeft = left.length ? Math.max(...left) : 0;
const maxTimeRight = right.length ? Math.max(...right.map(r => n - r)) : 0;
return Math.max(maxTimeLeft, maxTimeRight);
}
const n = 4;
const left = [4, 3];
const right = [0, 1];
const result = getLastMoment(n, left, right);
console.log(result);#include <stdio.h>
int getLastMoment(int n, int* left, int leftSize, int* right, int rightSize) {
int max_time_left = 0, max_time_right = 0;
for (int i = 0; i < leftSize; i++)
if (left[i] > max_time_left)
max_time_left = left[i];
for (int i = 0; i < rightSize; i++)
if (n - right[i] > max_time_right)
max_time_right = n - right[i];
return max_time_left > max_time_right ? max_time_left : max_time_right;
}
int main() {
int n = 4;
int left[] = {4, 3};
int right[] = {0, 1};
printf("%d\n", getLastMoment(n, left, 2, right, 2));
return 0;
}using System;
using System.Linq;
public class Solution {
public int GetLastMoment(int n, int[] left, int[] right) {
int maxTimeLeft = left.Length > 0 ? left.Max() : 0;
int maxTimeRight = right.Length > 0 ? right.Select(x => n - x).Max() : 0;
return Math.Max(maxTimeLeft, maxTimeRight);
}
public static void Main(string[] args) {
int[] left = {4, 3};
int[] right = {0, 1};
int n = 4;
Solution solution = new Solution();
int result = solution.GetLastMoment(n, left, right);
}
}Python's mechanism to handle empty lists alongside max helps in implementing the solution with conditional expressions to evaluate the plausible maximum time for both directions of ants falling.
Time Complexity: O(m + k) owing to exploration through potential maximum positions.
Space Complexity: O(1) without extra data structures being initialized.
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).
function getLastMoment(n: number, left: number[], right: number[]): number {
let ans = 0;
for (const x of left) {
ans = Math.max(ans, x);
}
for (const x of right) {
ans = Math.max(ans, n - x);
}
return ans;
}func getLastMoment(n int, left []int, right []int) (ans int) {
for _, x := range left {
ans = max(ans, x)
}
for _, x := range right {
ans = max(ans, n-x)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulate Ants Without Interaction | Time Complexity: O(m + k), where m and k are the sizes of the 'left' and 'right' arrays respectively. |
| Using Symmetry of Ants Simulation | Time Complexity: O(m + k) owing to exploration through potential maximum positions. |
| Brain Teaser | – |
Complexity analysis
| 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 |
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.