Last Moment Before All Ants Fall Out of a Plank - Problem

We have a wooden plank of length n units. Some ants are walking on the plank, each ant moves with a speed of 1 unit per second. Some ants move to the left, others move to the right.

When two ants moving in different directions meet at some point, they change directions and continue moving. Assume changing directions takes no additional time.

When an ant reaches one end of the plank at time t, it falls out of the plank immediately.

Given an integer n and two integer arrays left and right, representing the positions of ants moving left and right respectively, return the moment when the last ant(s) fall out of the plank.

Input & Output

Example 1 — Basic Case
$ Input: n = 4, left = [4,3], right = [0,1]
Output: 4
💡 Note: Ant at position 4 moving left takes 4 seconds to reach position 0. Ant at position 3 moving left takes 3 seconds. Ant at position 0 moving right takes 4 seconds to reach position 4. Ant at position 1 moving right takes 3 seconds. Maximum time is 4.
Example 2 — Only Left Moving
$ Input: n = 7, left = [0,1,2,3,4,5,6,7], right = []
Output: 7
💡 Note: All ants move left. The ant at position 7 takes the longest time (7 seconds) to reach the left edge at position 0.
Example 3 — Single Ant
$ Input: n = 7, left = [], right = [5]
Output: 2
💡 Note: Single ant at position 5 moving right takes 7-5=2 seconds to reach the right edge at position 7.

Constraints

  • 1 ≤ n ≤ 104
  • 0 ≤ left.length ≤ n + 1
  • 0 ≤ right.length ≤ n + 1
  • 1 ≤ left[i] ≤ n
  • 0 ≤ right[i] ≤ n - 1

Visualization

Tap to expand
Ants on a Plank - Last Moment to Fall INPUT Plank (n = 4) 0 1 2 3 4 L L R R Input Values: n = 4 left = [4, 3] right = [0, 1] Legend: = Moving Left = Moving Right ALGORITHM STEPS 1 Key Observation Collisions are irrelevant! Ants pass through each other 2 Left-moving ants Time to fall = position max(left) = max(4,3) = 4 3 Right-moving ants Time to fall = n - position max(4-0, 4-1) = max(4,3) = 4 4 Final Calculation Answer = max(step2, step3) = max(4, 4) = 4 Formula: max(max(left), n - min(right)) FINAL RESULT t = 0 t = 4 (all ants fallen) Fell! Fell! OUTPUT 4 Status: OK Last ant falls at t=4 Complexity: Time: O(n) | Space: O(1) Key Insight: When two ants collide and reverse direction, it's equivalent to them passing through each other! Therefore, we only need to find the maximum distance any ant needs to travel to reach an edge: max(leftmost position going left, n - rightmost position going right) TutorialsPoint - Last Moment Before All Ants Fall Out of a Plank | Mathematical Insight Approach
Asked in
Google 15 Facebook 12 Amazon 8
25.0K Views
Medium Frequency
~15 min Avg. Time
850 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen