1068. Ants on a Plank
A plank n centimetres long is laid across a stream and ants stand on its whole-number marks 0, 1, ..., n. Every ant listed in left starts at that mark and walks toward mark 0; every ant listed in right starts at that mark and walks toward mark n. Each ant covers one centimetre per second. Whenever two ants meet they both turn round at once, which costs no time. An ant reaching mark 0 or mark n drops off the plank.
Return the number of seconds until the very last ant has dropped off, or 0 when there are no ants at all. Either array may be empty and marks may repeat. Simulating every collision is too slow for large inputs; solve it in O(len(left) + len(right)) time and O(1) space.
Example 1
- Input:
- n = 12, left = [3,9], right = [5]
- Output:
- 9
- Explanation:
The slowest walker is the left-bound ant starting at mark 9, which needs 9 seconds; the right-bound ant at mark 5 needs 7.
Example 2
- Input:
- n = 20, left = [], right = [4,15]
- Output:
- 16
- Explanation:
No ant walks left, and the right-bound ant starting at mark 4 has 16 centimetres to go, so the answer is 16.
Example 3
- Input:
- n = 9, left = [2], right = [6]
- Output:
- 3
- Explanation:
The left ant needs 2 seconds and the right ant needs 3 seconds in total, so the last ant leaves at second 3.
Constraints
1 ≤ n ≤ 105
0 ≤ left.length, right.length ≤ 105
0 ≤ left[i], right[i] ≤ n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(a + b)
- Space
- O(1)