Ants Off the Beam

Medium

Ants crawl along a beam of length length, each at 1 unit per second. The ants in to_left start at the given points and head left; the ants in to_right head right. When two ants moving toward each other collide, both turn around instantly and keep going. An ant that reaches an end of the beam (point 0 or length) falls off at once. Return the moment when the last ant falls off the beam.

Example 1

length=10, to_left=[3], to_right=[8] → 3

They never meet: the left-walking ant leaves after 3 seconds, the other after 10 - 8 = 2. The last fall is at 3.

Example 2

length=6, to_left=[4], to_right=[2] → 4

The ants meet at 3 and turn around. That is the same as passing through each other, so the answer is max(4, 6 - 2) = 4.

Example 3

length=5, to_left=[], to_right=[0, 5] → 5

Constraints

1 ≤ length ≤ 10⁴
0 ≤ to_left[i], to_right[i] ≤ length
1 ≤ len(to_left) + len(to_right) ≤ length + 1
All positions are distinct, and none appears in both lists

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Brainteaser Array Simulation

Similar problems

Spiral Readout Medium Spiral-Numbered Square Medium Next Step of a Cell Colony Medium Zigzag Diagonal Sweep Medium Match-Three Cascade Medium

Input

length=10, to_left=[3], to_right=[8]

Expected

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.