We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with a speed of 1 unit per second. Some of the ants move to the left, the other move to the right.
When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions does not take any additional time.
When an ant reaches one end of the plank at a time t, it falls out of the plank immediately.
Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and 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: 4 Explanation: In the image above: -The ant at index 0 is named A and going to the right. -The ant at index 1 is named B and going to the right. -The ant at index 3 is named C and going to the left. -The ant at index 4 is named D and going to the left. The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).
Example 2:
Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7] Output: 7 Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.
Example 3:
Input: n = 7, left = [0,1,2,3,4,5,6,7], right = [] Output: 7 Explanation: All ants are going to the left, the ant at index 7 needs 7 seconds to fall.
Constraints:
1 <= n <= 1040 <= left.length <= n + 10 <= left[i] <= n0 <= right.length <= n + 10 <= right[i] <= n1 <= left.length + right.length <= n + 1left and right are unique, and each value can appear only in one of the two arrays.The direction change upon collision does not affect the final time an ant falls off. Therefore, the problem simplifies to determining the maximum time taken by any single ant to reach an edge and fall.
This solution loops through both the 'left' and 'right' arrays, calculating the maximum time required for both left-moving and right-moving ants to fall off. It calculates the time for left ants to reach position 0 and for right ants to reach position n, updating the maximum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m + k), where m and k are the sizes of the 'left' and 'right' arrays respectively.
Space Complexity: O(1), since we are using a constant amount of extra space.
In this approach, consider the fact that when two ants collide and change directions, it is equivalent to them passing through each other unaffected. Hence, it suffices to only measure how long it takes ants to fall off the plank.
This solution separately calculates the maximum times taken for ants from the left and right arrays to fall off the plank. It then utilizes a conditional check to determine the greater time value.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m + k) since we traverse both input arrays once.
Space Complexity: O(1) due to no extra memory required except primitives.
| Approach | Complexity |
|---|---|
| Simulate Ants Without Interaction | Time Complexity: O(m + k), where m and k are the sizes of the 'left' and 'right' arrays respectively. |
| Using Symmetry of Ants Simulation | Time Complexity: O(m + k) since we traverse both input arrays once. |
Last Moment Before All Ants Fall Out of a Plank | Easy Explanation | GOOGLE | Leetcode - 1503 • codestorywithMIK • 4,151 views views
Watch 9 more video solutions →Practice Last Moment Before All Ants Fall Out of a Plank with our built-in code editor and test cases.
Practice on FleetCode