Senior Software Engineer

Using Stack
The time complexity can be easily reduced to linear by using extra space. The idea is to use the stack data structure.

For each element x in the array, pop all elements from the stack smaller than x, and set their next greater element to x.
Loop till we have a greater element on top of the stack or stack becomes empty. Then push the current element x on top of the stack.
Repeat the process for every array element.
class Main
{
// Find the next greater element for every array element
public static int[] findNextGreaterElements(int[] input)
{
// base case
if (input == null) {
return input;
}

int[] result = new int[input.length];
Arrays.fill(result, -1);

// create an empty stack
Stack s = new Stack<>();

// do for each element
for (int i = 0; i < input.length; i++)
{
// loop till we have a greater element on top or stack becomes empty.

// Keep popping elements from the stack smaller than the current
// element, and set their next greater element to the current element

while (!s.isEmpty() && input[s.peek()] < input[i]) {
result[s.pop()] = input[i];
}

// push current "index" into the stack
s.push(i);
}

return result;
}

The idea is to merge the arrival and departure times of trains and consider them in sorted order. Maintain a counter to count the total number of trains present at the station at any point. The counter also represents the total number of platforms needed at that time.

If the train is scheduled to arrive next, increase the counter by one and update the minimum platforms needed if the count is more than the minimum platforms needed so far.
If the train is scheduled to depart next, decrease the counter by 1.
One special case needs to be handled – when two trains are scheduled to arrive and depart simultaneously, depart the train first.

class Main
{
// Function to find the minimum number of platforms needed
// to avoid delay in any train arrival
public static int findMinPlatforms(double[] arrival, double[] departure)
{
// sort arrival time of trains
Arrays.sort(arrival);

// sort departure time of trains
Arrays.sort(departure);

// maintains the count of trains
int count = 0;

// stores minimum platforms needed
int platforms = 0;

// take two indices for arrival and departure time
int i = 0, j = 0;

// run till all trains have arrived
while (i < arrival.length)
{
// if a train is scheduled to arrive next
if (arrival[i] < departure[j])
{
// increase the count of trains and update minimum
// platforms if required
platforms = Integer.max(platforms, ++count);

// move the pointer to the next arrival
i++;
}

// if the train is scheduled to depart next i.e.
// `departure[j] < arrival[i]`, decrease trains' count
// and move pointer `j` to the next departure.

// If two trains are arriving and departing simultaneously,
// i.e., `arrival[i] == departure[j]`, depart the train first
else {
count--;
j++;
}
}

return platforms;
}
The time complexity of the above solution is O(n.log(n)) and doesn’t require any extra space, where n is the total number of trains.

Every ant has two choices (pick either of two edges going through the corner on which ant is initially sitting).
Since every ant has two choices (pick either of two edges going through the corner on which ant is initially sitting), there are total 23 possibilities.

Out of 23 possibilities, only 2 don’t cause collision. So, the probability of collision is 6/8 and the probability of non-collision is 2/8.