Last Moment Before All Ants Fall Out of a Plank

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 ≤ 10⁴
0 ≤ left.length ≤ n + 1
0 ≤ right.length ≤ n + 1
1 ≤ left[i] ≤ n
0 ≤ right[i] ≤ n - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Plank of length n with ants at specific positions moving left or right

Process

Ants move at speed 1 unit/second, change directions when they collide

Output

Time when the last ant falls off either edge

Key Takeaway

🎯 Key Insight: Collisions don't change the total time - just calculate max distance to nearest edge

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that when ants collide and change directions, it's equivalent to them passing through each other. The optimal approach calculates the maximum time any ant needs to reach an edge: position for left-moving ants and n - position for right-moving ants. Time: O(m), Space: O(1) where m is the total number of ants.

Common Approaches

Approach	Time	Space	Notes
✓ Simulate Every Movement	O(n × k)	O(m)	Track each ant's position and direction, simulate collisions step by step
Mathematical Insight	O(m)	O(1)	Realize that collisions don't change total time - just calculate maximum distance any ant needs to travel

Simulate Every Movement — Algorithm Steps

Create ant objects with position and direction
For each time step, move all ants
Check for collisions and reverse directions
Remove ants that fall off edges
Return the time when last ant falls

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create ant objects with positions and directions

Move & Collide

Move all ants, detect collisions, reverse directions

Remove

Remove ants that fall off edges, continue until none remain

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int pos;
    int dir;
} Ant;

int solution(int n, int* left, int leftSize, int* right, int rightSize) {
    int totalAnts = leftSize + rightSize;
    Ant* ants = (Ant*)malloc(totalAnts * sizeof(Ant));
    int antCount = 0;
    
    // Create ants with position and direction (-1 for left, 1 for right)
    for (int i = 0; i < leftSize; i++) {
        ants[antCount].pos = left[i];
        ants[antCount].dir = -1; // moving left
        antCount++;
    }
    for (int i = 0; i < rightSize; i++) {
        ants[antCount].pos = right[i];
        ants[antCount].dir = 1;  // moving right
        antCount++;
    }
    
    int time = 0;
    while (antCount > 0) {
        time++;
        // Move all ants
        for (int i = 0; i < antCount; i++) {
            ants[i].pos += ants[i].dir;
        }
        
        // Check for collisions and reverse directions
        for (int i = 0; i < antCount; i++) {
            for (int j = i + 1; j < antCount; j++) {
                if (ants[i].pos == ants[j].pos) {
                    // Collision detected, reverse both ants
                    ants[i].dir *= -1;
                    ants[j].dir *= -1;
                }
            }
        }
        
        // Remove ants that fell off
        int newCount = 0;
        for (int i = 0; i < antCount; i++) {
            if (ants[i].pos > 0 && ants[i].pos < n) {
                ants[newCount] = ants[i];
                newCount++;
            }
        }
        antCount = newCount;
    }
    
    free(ants);
    return time;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Read and parse left array
    char leftStr[1000];
    scanf(" %s", leftStr);
    int left[100], leftSize = 0;
    if (strcmp(leftStr, "[]") != 0) {
        char* token = strtok(leftStr + 1, ",]");
        while (token != NULL) {
            left[leftSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    // Read and parse right array
    char rightStr[1000];
    scanf(" %s", rightStr);
    int right[100], rightSize = 0;
    if (strcmp(rightStr, "[]") != 0) {
        char* token = strtok(rightStr + 1, ",]");
        while (token != NULL) {
            right[rightSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    printf("%d\n", solution(n, left, leftSize, right, rightSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

Where k is the maximum time any ant stays on plank, could be O(n²) in worst case

✓ Linear Growth

Space Complexity

O(m)

Where m is total number of ants (left.length + right.length)

✓ Linear Space

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulate Every Movement — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler