Leetcode 1503. Last Moment Before All Ants Fall Out of a Plank

Problem Description

In this problem, we have a one-dimensional wooden plank of length "n" units. There are some ants moving on this plank. The ants can move either to the left or to the right with a speed of 1 unit per second.

When two ants moving in different directions meet at any one point, they change their directions and continue moving. However, changing directions doesn't take any additional time.

The trip of an ant ends when it reaches one end of the plank. At this point, it falls off the plank immediately.

Given the length of the plank and the current positions of all the ants, the task is to determine the time it takes for the last of the ants to fall off the plank.

For this, we are given an integer "n", and two integer arrays "left" and "right". "n" is the length of the plank. The "left" array includes the starting positions of all ants moving towards the left, while the "right" array includes the starting positions of all ants moving towards the right.

We have to return the time it takes for the last ant(s) to fall out of the plank.

Example Walkthrough

Let's consider an example for better understanding:

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

In this case, the ant at index 0 and 1 are moving to the right, while the ant at index 3 and 4 are moving to the left. The last moment when an ant was on the plank is at t = 4 seconds, after which it falls off the plank immediately. Therefore, the output for this example would be 4.

Solution Approach

The solution of this problem is somewhat counter-intuitive. A major point to understand is that when two ants meet and change their directions, it is equivalent to them just passing through each other without changing directions.

Therefore, we need to find the ant which is furthest from the edge in its direction of movement. It will be the last one to fall off the plank.

For the ants moving to the left, we look for the maximum index in the "left" array, as it means the ant is furtherest from the left edge. For the ants moving to the right, we look for the minimum index in the "right" array. As it is moving to the right, we subtract the index from n to get the distance from the right edge.

The maximum of these two values will give us the time when the last ant(s) fall out of the plank.

Python Solution

1
2python
3class Solution:
4    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
5        # getMaxLeft() gets the maximum index of ants moving to left
6        maxLeft = max(left, default=0)
7        
8        # getMinRight() gets the minimum index of ants moving to right
9        # we subtract it from n to get the distance from the right edge
10        minRight = n - min(right, default=n)
11        
12        # the maximum of these two values will be our result
13        return max(maxLeft, minRight)

Java Solution

1
2java
3class Solution {
4    public int getLastMoment(int n, int[] left, int[] right) {
5        int maxLeft = Arrays.stream(left).max().orElse(0);
6        int minRight = n - Arrays.stream(right).min().orElse(n);
7        return Math.max(maxLeft, minRight);
8    }
9}

Javascript Solution

1
2js
3class Solution {
4    getLastMoment(n, left, right) {
5        let maxLeft = Math.max(...left, 0);
6        let minRight = n - Math.min(...right, n);
7        return Math.max(maxLeft, minRight);
8    }
9}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
6        int maxLeft = *max_element(left.begin(), left.end());
7        int minRight = n - *min_element(right.begin(), right.end());
8        return max(maxLeft, minRight);
9    }
10};

C# Solution

1
2csharp
3public class Solution {
4    public int GetLastMoment(int n, int[] left, int[] right) {
5        int maxLeft = left.Length == 0 ? 0 : left.Max();
6        int minRight = right.Length == 0 ? n : n - right.Min();
7        return Math.Max(maxLeft, minRight);
8    }
9}

Ruby Solution

1
2ruby
3class Solution
4    def get_last_moment(n, left, right)
5        max_left = left.empty? ? 0 : left.max
6        min_right = right.empty? ? n : n - right.min
7        return [max_left, min_right].max
8    end
9end

Go Solution

1
2go
3import (
4    "math"
5)
6
7func getLastMoment(n int, left []int, right []int) int {
8    var maxLeft, minRight int
9    for _,v := range left {
10        maxLeft = int(math.Max(float64(maxLeft), float64(v)))
11    }
12    for _,v := range right {
13        minRight = int(math.Max(float64(minRight), float64(n-v)))
14    }
15    return int(math.Max(float64(maxLeft), float64(minRight)))
16}

PHP Solution

1
2php
3class Solution {
4    
5    function getLastMoment($n, $left, $right) {
6        $maxLeft = count($left) > 0 ? max($left) : 0;
7        $minRight = count($right) > 0 ? $n - min($right) : $n;
8        return max($maxLeft, $minRight);
9    }
10}

Kotlin Solution

1
2kotlin
3class Solution {
4    fun getLastMoment(n: Int, left: IntArray, right: IntArray): Int {
5        val maxLeft = left.maxOrNull() ?: 0
6        val minRight = n - (right.minOrNull() ?: n)
7        return maxOf(maxLeft, minRight)
8    }
9}

Swift Solution

1
2swift
3class Solution {
4    func getLastMoment(_ n: Int, _ left: [Int], _ right: [Int]) -> Int {
5        let maxLeft = left.isEmpty ? 0 : left.max()!
6        let minRight = right.isEmpty ? n : n - right.min()!
7        return max(maxLeft, minRight)
8    }
9}

These above solutions are efficient and concise. They simply calculate the maximum time it takes for the ant furthest from the edge in its direction to reach the edge of the plank. They take into consideration the edge cases where any of the lists may be empty using default values or conditional checks. These solutions should work for any reasonable input size within the constraints of the problem.