LeetCode 1503 - Last Moment Before All Ants Fall Out of a Plank

The problem describes a plank of length n on which ants are walking either to the left or to the right at a constant spe

leetcodemediumarraybrainteasersimulation

LeetCode Problem 1503

Difficulty: 🟡 Medium
Topics: Array, Brainteaser, Simulation

Solution

Problem Understanding

The problem describes a plank of length n on which ants are walking either to the left or to the right at a constant speed of 1 unit per second. We are given two arrays: left contains the starting positions of ants moving left, and right contains the starting positions of ants moving right. When two ants moving in opposite directions meet, they “swap” directions, but the key insight is that swapping is equivalent to them passing through each other without affecting the final falling times, because ants are indistinguishable for the purpose of determining the last fall.

The goal is to determine the last moment when an ant is still on the plank before all ants fall off. An ant falls off the plank immediately upon reaching either end. The plank starts at position 0 and ends at position n.

The constraints guarantee that the plank length n is up to 10,000 units, and the total number of ants is at most n + 1. Each position is unique, and no position is shared between the left and right arrays. This means we do not have to handle duplicate ants or overlapping positions.

Important edge cases include an empty left or right array, ants starting at the extreme ends, and all ants moving in the same direction.

Approaches

Brute Force

A brute-force approach simulates the movement of ants second by second. At each time step, we would move every ant according to its direction, handle collisions by swapping directions, and remove ants that fall off. We would continue this simulation until all ants fall off.

While this approach is correct, it is inefficient. For example, if an ant starts at the opposite end from its falling direction, it may require up to n seconds to fall. With multiple ants, this approach could result in an O(n * k) simulation, where k is the number of ants. Given n up to 10,000, this can be slow.

Optimal Approach

The key observation is that ants passing through each other is equivalent to ignoring the collisions because the time each ant takes to fall off is independent of collisions if we just track distances to the nearest ends. For an ant moving left, its fall time is equal to its starting position. For an ant moving right, its fall time is n - position. Therefore, the last moment is simply the maximum of these fall times.

This approach avoids simulating movement entirely and computes the answer in linear time with respect to the number of ants.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k) O(k) Simulate each second for all ants, handle collisions
Optimal O(k) O(1) Compute max of left[i] and n - right[i] for all ants

Algorithm Walkthrough

  1. Initialize a variable last_moment to 0. This will store the latest time any ant falls off the plank.
  2. Iterate through each ant in the left array:
  • The ant is moving left, so its fall time is exactly its starting position pos.
  • Update last_moment to be the maximum of last_moment and pos.
  1. Iterate through each ant in the right array:
  • The ant is moving right, so its fall time is n - pos.
  • Update last_moment to be the maximum of last_moment and n - pos.
  1. After processing all ants, return last_moment.

Why it works: Each ant falls independently if we ignore the collisions. By taking the maximum of all fall times, we capture the last moment any ant remains on the plank. The collisions do not affect the final time due to the symmetry of ants swapping directions.

Python Solution

from typing import List

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

Explanation: We iterate over left to check how long each left-moving ant will take to fall, which is just its position. Similarly, right-moving ants take n - pos seconds to fall. We maintain a running maximum in last_moment and return it at the end.

Go Solution

func getLastMoment(n int, left []int, right []int) int {
    lastMoment := 0
    
    for _, pos := range left {
        if pos > lastMoment {
            lastMoment = pos
        }
    }
    
    for _, pos := range right {
        if n - pos > lastMoment {
            lastMoment = n - pos
        }
    }
    
    return lastMoment
}

Explanation: The Go solution mirrors the Python logic. We iterate over the left and right slices, updating lastMoment with the maximum time for each ant to fall. Go requires explicit comparison for the maximum rather than a built-in function like Python's max.

Worked Examples

Example 1: n = 4, left = [4,3], right = [0,1]

Ant Direction Position Fall Time
A right 0 4 - 0 = 4
B right 1 4 - 1 = 3
C left 3 3
D left 4 4

Maximum fall time = 4. Output = 4.

Example 2: n = 7, left = [], right = [0,1,2,3,4,5,6,7]

Right-moving ants fall in times [7,6,5,4,3,2,1,0]. Maximum = 7.

Example 3: n = 7, left = [0,1,2,3,4,5,6,7], right = []

Left-moving ants fall in times [0,1,2,3,4,5,6,7]. Maximum = 7.

Complexity Analysis

Measure Complexity Explanation
Time O(k) Iterate over left and right arrays once, where k = total number of ants
Space O(1) Only a single variable last_moment is used

The time complexity is linear in the number of ants, which is acceptable given the constraints. No extra data structures are required.

Test Cases

# Provided examples
assert Solution().getLastMoment(4, [4,3], [0,1]) == 4  # Mixed directions
assert Solution().getLastMoment(7, [], [0,1,2,3,4,5,6,7]) == 7  # All right
assert Solution().getLastMoment(7, [0,1,2,3,4,5,6,7], []) == 7  # All left

# Edge cases
assert Solution().getLastMoment(1, [0], []) == 0  # Single left ant at start
assert Solution().getLastMoment(1, [], [1]) == 0  # Single right ant at end
assert Solution().getLastMoment(10, [0,10], [5]) == 10  # Ants at ends and middle
Test Why
Mixed directions Verifies algorithm finds max of both sides
All right Verifies single direction case
All left Verifies single direction case
Single ant at start Edge: minimal plank and ant at left end
Single ant at end Edge: minimal plank and ant at right end
Ants at extremes and middle Validates multiple positions including ends

Edge Cases

  1. Empty left or right arrays: If there are no ants moving in one direction, the algorithm must still consider the other direction correctly. The solution handles this by iterating only over existing arrays.
  2. Ants at the ends: If an ant starts at position 0 moving left or position n moving right, it falls immediately. The algorithm correctly computes 0 or n - n = 0 for these cases, which is handled by the max function.
  3. Single ant plank: For n = 1 or a very short plank, the calculation must correctly handle minimal distances. Since we compute fall times directly from positions, this edge case is naturally covered.