← All solutions

First, we trace the route of the laser beam from the entry through the maze. This can be done in O( N log N ) time (where we let N = n + m be the total number of mirrors) by keeping track of dictionary of the mirror positions in each row and column. This trace can be represented as a set of horizontal and vertical line segments.

If the laser beam exits at the exit, we’re done. Otherwise, we run the same trace backwards from the exit position, giving a second set of horizontal and vertical line segments. After this, the set of positions where a mirror can be inserted are simply all intersection points between line segments from the two traces. This can be found in O( N log N ) time using a standard sweepline approach, though one needs a datastructure that can do quick range counting, e.g., a Fenwick tree.