Sponsored
Sponsored
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.
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.
1#include <vector>
2#include <algorithm>
3
4int getLastMoment(int n, std::vector<int>& left, std::vector<int>& right) {
5 int maxTime = 0;
6 for (int pos : left) { maxTime = std::max(maxTime, pos); }
7 for (int pos : right) { maxTime = std::max(maxTime, n - pos); }
8 return maxTime;
9}
10
11int main() {
12 std::vector<int> left = {4, 3};
13 std::vector<int> right = {0, 1};
14 int n = 4;
15 int result = getLastMoment(n, left, right);
16 return 0;
17}This C++ solution uses the max function to determine the maximum time taken by ants moving both directions to fall off the plank.
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.
Time Complexity: O(m + k) since we traverse both input arrays once.
Space Complexity: O(1) due to no extra memory required except primitives.
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.