Last Moment Before All Ants Fall Out of a Plank
We have a wooden plank of length n units. Some ants are walking on the plank, and each ant moves with a speed of 1 unit per second. Some ants move to the left, and the others move to the right.
When two ants moving in different directions meet at some point, they change their directions and continue moving. Assume changing directions does not take any 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, where left contains the positions of ants moving to the left and right contains the positions of ants moving to the right, return the moment when the last ant(s) fall out of the plank.
Example 1
Input
n = 4, left = [4,3], right = [0,1]Output
4The last moment when an ant is on the plank is at t = 4 seconds; immediately after that, no ants remain on the plank.
Example 2
Input
n = 7, left = [], right = [0,1,2,3,4,5,6,7]Output
7All ants are going to the right, and the ant at index 0 needs 7 seconds to fall.
Constraints
- 1 <= n <= 10^4
- 0 <= left.length <= n + 1
- 0 <= left[i] <= n
- 0 <= right.length <= n + 1
- 0 <= right[i] <= n
- 1 <= left.length + right.length <= n + 1
- All values of left and right are unique, and each value can appear only in one of the two arrays.