Solution


Approach 1: Walk in a Spiral

Intuition

We can walk in a spiral shape from the starting square, ignoring whether we stay in the grid or not. Eventually, we must have reached every square in the grid.

Algorithm

Examining the lengths of our walk in each direction, we find the following pattern: 1, 1, 2, 2, 3, 3, 4, 4, ... That is, we walk 1 unit east, then 1 unit south, then 2 units west, then 2 units north, then 3 units east, etc. Because our walk is self-similar, this pattern repeats in the way we expect.

After, the algorithm is straightforward: perform the walk and record positions of the grid in the order we visit them. Please read the inline comments for more details.

Complexity Analysis

  • Time Complexity: . Potentially, our walk needs to spiral until we move in one direction, and in another direction, so as to reach every cell of the grid.

  • Space Complexity: , the space used by the answer.


Analysis written by: @awice.