Problem Description

You have a wooden plank of length n units. Several ants are walking on this plank, each moving at a speed of 1 unit per second. Some ants move to the left, while others move to the right.

When two ants moving in opposite directions meet at any point on the plank, they immediately change their directions and continue moving. This direction change happens instantaneously without any time delay.

When an ant reaches either end of the plank (position 0 or position n), it falls off immediately.

You are given:

• An integer n representing the length of the plank
• An integer array left containing the initial positions of ants moving to the left
• An integer array right containing the initial positions of ants moving to the right

Your task is to find the time when the last ant falls off the plank.

The clever insight here is that when two ants collide and turn around, it's mathematically equivalent to the ants passing through each other without collision. This is because the ants are identical - when they "bounce" off each other, we can think of it as if they simply passed through each other instead.

Therefore, the problem simplifies to finding the maximum time any ant needs to reach an edge:

• For ants moving left from position x, they need x seconds to fall off
• For ants moving right from position x, they need n - x seconds to fall off

The answer is the maximum among all these times.

Intuition

The key realization comes from understanding what happens when two ants collide. Initially, we might think we need to track each ant's position and handle all the collisions, which would be complex.

But let's think about what actually happens when two ants meet:

• Ant A is moving right, Ant B is moving left
• They collide and turn around
• Now Ant A is moving left, Ant B is moving right

Here's the crucial insight: since all ants move at the same speed and are indistinguishable, the collision is functionally equivalent to the two ants passing through each other!

To visualize this, imagine the ants are identical dots. When they "bounce" off each other:

• Before collision: one dot going right at position p, another going left at position p
• After collision: one dot going left at position p, another going right at position p

From an outside observer's perspective who can't tell the ants apart, this looks exactly the same as if the ants had just passed through each other without interacting at all.

This transforms the problem dramatically. Instead of tracking collisions, we can simply calculate how long each ant would take to fall off the plank if it continued in its original direction without any collisions:

• An ant at position x moving left needs exactly x seconds to reach position 0 and fall off
• An ant at position x moving right needs exactly n - x seconds to reach position n and fall off

The last ant to fall off the plank will be the one that needs the maximum time to reach an edge. Therefore, we just need to find max(all distances to edges).

Solution Approach

Based on our intuition that collisions can be ignored and ants effectively pass through each other, the implementation becomes straightforward:

1. Initialize a variable to track the maximum time: We start with ans = 0 to keep track of the maximum time any ant needs to fall off the plank.

2. Process ants moving left: For each ant in the left array at position x:

   • This ant needs x seconds to reach the left edge (position 0)
   • Update ans = max(ans, x)

3. Process ants moving right: For each ant in the right array at position x:

   • This ant needs n - x seconds to reach the right edge (position n)
   • Update ans = max(ans, n - x)

4. Return the result: The value of ans represents the time when the last ant falls off the plank.

The implementation in Python:

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        ans = 0
        for x in left:
            ans = max(ans, x)
        for x in right:
            ans = max(ans, n - x)
        return ans

Time Complexity: O(L + R) where L is the length of the left array and R is the length of the right array. We iterate through each array once.

Space Complexity: O(1) as we only use a single variable ans to track the maximum time, regardless of input size.

Note that the arrays left and right might be empty, but this doesn't affect our solution since we simply wouldn't enter the respective loops, and ans would remain at its initialized value or be updated by the other array's values.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example:

• Plank length n = 7
• Ants moving left: left = [4, 6] (starting at positions 4 and 6)
• Ants moving right: right = [1] (starting at position 1)

Step 1: Visualize the initial setup

Position: 0  1  2  3  4  5  6  7
          |  →     ←     ←  |
             ↑     ↑     ↑
          right  left   left

Step 2: Apply the key insight Instead of tracking collisions, we treat ants as if they pass through each other. Each ant will fall off based on its initial position and direction:

Step 3: Calculate fall times for left-moving ants

• Ant at position 4 moving left → needs 4 seconds to reach position 0
• Ant at position 6 moving left → needs 6 seconds to reach position 0

Step 4: Calculate fall times for right-moving ants

• Ant at position 1 moving right → needs (7 - 1) = 6 seconds to reach position 7

Step 5: Find the maximum time

• Times: [4, 6, 6]
• Maximum = 6 seconds

Step 6: Verify with actual collision behavior Let's trace what actually happens to confirm our answer:

• t=0: Positions are [1→, 4←, 6←]
• t=1: Positions are [2→, 3←, 5←]
• t=2: Positions are [3→, 2←, 4←] (collision at position 2.5, they turn around)
• t=3: Positions are [2←, 3→, 3←] (another collision at position 3)
• t=4: Positions are [1←, 4→, 2←]
• t=5: Positions are [0←, 5→, 1←] (ant at position 0 falls off)
• t=6: Positions are [6→, 0←] (ant at position 0 falls off)
• t=7: Position [7→] (last ant falls off at the right edge)

Wait, that gives us 7 seconds, not 6. Let me recalculate...

Actually, I made an error. The last ant falls at t=6. Let me trace more carefully:

• t=0: [1→, 4←, 6←]
• t=1: [2→, 3←, 5←]
• t=2: [3→, 2←, 4←] (ants meet between 2-3, they bounce)
• Actually, after the bounce: [2←, 3→, 4←]
• t=3: [1←, 4→, 3←]
• t=4: [0←, 5→, 2←] (left ant falls)
• t=5: [6→, 1←]
• t=6: [7→, 0←] (both ants fall off)

The answer is 6 seconds, which matches our calculation using the simplified approach: max(4, 6, 6) = 6.

Solution Implementation

Time and Space Complexity

The time complexity is O(m + k), where m is the length of the left array and k is the length of the right array. This is because the algorithm iterates through each element in the left array once and each element in the right array once, performing constant-time operations (max comparison) for each element.

The space complexity is O(1) as the algorithm only uses a single variable ans to store the maximum value, regardless of the input size. No additional data structures are created that scale with the input.

Note: The reference answer states O(n) for time complexity where n is the length of the plank, which appears to be incorrect as the actual time complexity depends on the number of ants (elements in the arrays) rather than the plank length itself.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Collision Mechanics

Many people initially try to simulate the actual collisions between ants, tracking when they meet and changing their directions. This leads to overly complex solutions with nested loops and collision detection logic.

Why it's wrong: This approach unnecessarily complicates the problem and can lead to O(n²) or worse time complexity.

Correct approach: Recognize that when two ants collide and reverse directions, it's mathematically equivalent to them passing through each other. Each ant can be treated independently.

2. Off-by-One Errors with Plank Boundaries

A common mistake is confusing whether the plank positions are 0-indexed or 1-indexed, or miscalculating the distance to fall off.

Example mistake:

# Wrong: thinking ants at position n need 0 time to fall off
for position in right:
    max_time = max(max_time, position)  # Should be n - position

Correct approach: Remember that:

• Plank positions range from 0 to n (inclusive)
• Ants moving left from position x need exactly x seconds
• Ants moving right from position x need exactly (n - x) seconds

3. Not Handling Empty Arrays

If either left or right array is empty, some solutions might fail or return incorrect results.

Example mistake:

# Wrong: assumes both arrays have elements
return max(max(left), n - min(right))  # Fails if either array is empty

Correct approach: Initialize the result to 0 and use loops that naturally handle empty arrays:

max_time = 0
for position in left:  # If left is empty, loop doesn't execute
    max_time = max(max_time, position)
for position in right:  # If right is empty, loop doesn't execute
    max_time = max(max_time, n - position)

4. Using Built-in Functions Incorrectly

Trying to use Python's max() function directly on potentially empty lists causes errors.

Example mistake:

# Wrong: max() on empty sequence raises ValueError
left_max = max(left) if left else 0
right_max = max([n - x for x in right]) if right else 0
return max(left_max, right_max)

While this works, it's more complex than needed and requires explicit empty checks.

Better approach: Use a single variable and iterate through both arrays, which naturally handles all cases including empty arrays.