We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Last Moment Before All Ants Fall Out of a Plank

Number: 1627

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

You are given a plank of length n. Ants are positioned on the plank, moving either left or right with a speed of 1 unit per second. When two ants meet, they instantly change directions, and when an ant reaches the end of the plank at time t, it falls off immediately. Given the positions of ants moving left and right, determine the moment when the last ant falls off.

Key Insights

  • The collision of ants that swap directions is equivalent to ants passing through each other without interfering.
  • Therefore, the time for an ant to fall off depends solely on its initial position and its moving direction.
  • For ants moving left, the fall time is simply their position value.
  • For ants moving right, the fall time is (n − position).
  • The answer is the maximum of these times across all ants.

Space and Time Complexity

Time Complexity: O(k) where k is the total number of ants (which is at most n+1).
Space Complexity: O(1)

Solution

We take advantage of the fact that the collision behavior is equivalent to ants passing through each other. This means we can ignore the collisions and simply calculate, for each ant, the time it takes to fall off the plank. For ants moving left, their fall-off time is equal to their position. For ants moving right, it is equal to (n − position). The answer is the maximum value among these times. We iterate through the left and right arrays once, calculating the corresponding times, and then take the maximum.

Code Solutions

# Function to determine the last moment an ant falls
def getLastMoment(n, left, right):
    # Calculate maximum time for ants moving left (position value itself)
    max_left_time = max(left) if left else 0
    # Calculate maximum time for ants moving right (n - position)
    max_right_time = max(n - pos for pos in right) if right else 0
    # The answer is the maximum of the computed times
    return max(max_left_time, max_right_time)

# Example usage:
n = 4
left = [4,3]
right = [0,1]
print(getLastMoment(n, left, right))  # Expected output: 4
← Back to All Questions