Note that any collision between any pair of monkeys is going to be at a single, distinct cell at only one possible moment in time. If the monkey on the leftmost column is at row ~i~ (call this monkey ~a~) and the monkey on the topmost column is at row ~j~ (call this monkey ~b~), the point of collision will be at cell ~(i, j)~.

If monkey ~a~ leaves at time ~x~, monkey ~b~ will need to leave at time ~x+j-i~. If we represent monkey ~b~'s departure time as ~y~ then we get the equation ~y = x+j-i \Rightarrow y+i = x+j~. Swap ~i~ and ~j~ and we get ~y-j = x-i~. Now these values ~y-j~ and ~x-i~ can easily be calculated through iteration over the departure times for monkeys on the topmost row and leftmost column.

We can then observe that over all distinct values of ~y-j~, we add to our answer the minimum between the number of occurrences of ~y-j~ and the number of occurrences of ~x-i~ such that ~y-j = x-i~. This is because each ~y-j~ must be paired with an ~x-i~ to achieve a collision, extras will not collide with any other monkey.

Implementation can be done using a map to count occurrences, resulting in a log factor. There is also another solution involving sorting.

Time Complexity: ~\mathcal{O}((N + M) \cdot \log (N + M))~

Additional Notes

Big thanks to 4fecta for suggesting this problem.