Matrix traversal

When to use it

Use it when the task states the order to visit the cells of a grid, or the new place of each cell, and neither depends on what the cells hold.

It belongs to the math & bits group: Work on the cells, the digits or the bits themselves, in a fixed order.

Watch it work

A board game has rows rows of cols squares. A path of numbers starts with 1 at the top left, runs right along the first row, back left along the second, and so on to the last row. Return the board with every square numbered.

Input
rows = 3
cols = 3

Output
[[1, 2, 3], [6, 5, 4], [7, 8, 9]]

The method

1. Make an empty board; the first number to write is 1
2. An even row runs right: move i is column i
3. An odd row runs left: move i is column cols - 1 - i
4. Every square has its number: return the board

The run, one moment at a time

1. Step 1. The board has 3 rows and 3 columns. Every square holds 0, which means no number yet. The first number to write is 1.

   row 0: 0 0 0
   row 1: 0 0 0
   row 2: 0 0 0
   

2. Step 2. Row 0 is even, so the path runs right. Move 0 is column 0, the top left square. Write 1.

   row 0: 1 0 0
   row 1: 0 0 0
   row 2: 0 0 0
   

3. Step 2. Move 1 of row 0 is column 1. Write 2.

   row 0: 1 2 0
   row 1: 0 0 0
   row 2: 0 0 0
   

4. Step 2. Move 2 of row 0 is column 2, the last column. Write 3. The row is full.

   row 0: 1 2 3
   row 1: 0 0 0
   row 2: 0 0 0
   

5. Step 3. Row 1 is odd, so the path runs left. Move 0 is column 3 - 1 - 0 = 2, straight below the 3. Write 4.

   row 0: 1 2 3
   row 1: 0 0 4
   row 2: 0 0 0
   

6. Step 3. Move 1 of row 1 is column 3 - 1 - 1 = 1. Write 5.

   row 0: 1 2 3
   row 1: 0 5 4
   row 2: 0 0 0
   

7. Step 3. Move 2 of row 1 is column 3 - 1 - 2 = 0, the first column. Write 6. The row is full.

   row 0: 1 2 3
   row 1: 6 5 4
   row 2: 0 0 0
   

8. Step 2. Row 2 is even, so the path runs right again. Move 0 is column 0, straight below the 6. Write 7.

   row 0: 1 2 3
   row 1: 6 5 4
   row 2: 7 0 0
   

9. Step 2. Move 1 of row 2 is column 1. Write 8.

   row 0: 1 2 3
   row 1: 6 5 4
   row 2: 7 8 0
   

10. Step 2. Move 2 of row 2 is column 2, the last column. Write 9. The row is full.

    row 0: 1 2 3
    row 1: 6 5 4
    row 2: 7 8 9
    

11. Step 4. 9 squares, 9 writes: each square was visited once. Nothing was searched for. A square's row and its move number gave its column.

    row 0: 1 2 3
    row 1: 6 5 4
    row 2: 7 8 9
    

The code

The numbered comments are the steps of the method.

function solve(rows, cols) {
  // 1. Make an empty board; the first number to write is 1
  const board = [];
  for (let r = 0; r < rows; r++) board.push(new Array(cols).fill(0));
  let count = 1;
  for (let r = 0; r < rows; r++) {
    for (let i = 0; i < cols; i++) {
      if (r % 2 === 0) {
        // 2. An even row runs right: move i is column i
        board[r][i] = count;
      } else {
        // 3. An odd row runs left: move i is column cols - 1 - i
        board[r][cols - 1 - i] = count;
      }
      count += 1;
    }
  }
  // 4. Every square has its number: return the board
  return board;
}

def solve(rows, cols):
    # 1. Make an empty board; the first number to write is 1
    board = []
    for r in range(rows):
        board.append([0] * cols)
    count = 1
    for r in range(rows):
        for i in range(cols):
            if r % 2 == 0:
                # 2. An even row runs right: move i is column i
                board[r][i] = count
            else:
                # 3. An odd row runs left: move i is column cols - 1 - i
                board[r][cols - 1 - i] = count
            count += 1
    # 4. Every square has its number: return the board
    return board

How to spot it

Asked: Return the values of the grid in a stated order

The order is known before you start. Loops over the row and column numbers produce it, so nothing is searched and nothing is marked.

Asked: Flip, turn or shift the whole grid

The new cell of a value depends only on its old row and column. One rule with those two numbers moves every value.

Limits: Move the values inside the grid itself; a second grid is not allowed

Values must trade places directly. The walk is planned so that every value moves once and none is written over before it has moved.

Looks like it, but is not

• Cells that touch and hold the same value form a region, and you must count or measure the regions. Use Grid connected components. Which cells belong together depends on what they hold. You must spread out from a cell and mark what you reach.
• Each cell needs the best total of a walk that ends there. Use Two-dimensional dynamic programming. The grid is then a table of answers. Each cell is worked out from the answers in the cells before it, not only read or moved.
• You need the fewest moves from one cell to another, around walls. Use Breadth-first search by distance. The order of the visit is not given. It spreads out from the start one move at a time, and the walls shape it.

Cost and mistakes

Time is one write for each square, rows times columns in all, written O(rows × cols), because every square is visited exactly once. Extra space is nothing beyond the board that is returned, written O(1).

Watch out

• The last column is cols - 1, not cols. So the mirror of column i is cols - 1 - i. Without the - 1, the first move of an odd row lands outside the board.
• The row comes first: board[r][c] is row r, then column c. On a board that is not square, swapping the two reaches for a square that does not exist.

In the 150

2 problems of the 150 use it. Naming them gives their method away, so the list is folded.