Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 225 ยท Arrays and Lists

Matrix Classics: Pascal, Magic Squares, Toeplitz, Sudoku and Max-Sum Rectangle

Practice 2D array skills in Python with six classic exercises: Pascal's triangle, odd magic squares, Toeplitz check, Sudoku validation, tic-tac-toe and max-sum rectangle.

Once you can build, traverse and rotate a grid, the best way to get fluent is to solve a set of small, well-known exercises. Each one in this lesson uses a different "index trick", and together they cover most of what interviewers and contests ask about 2D arrays.

You will generate Pascal's triangle row by row, fill an odd magic square with a movement rule, test a Toeplitz matrix by comparing diagonal neighbours, validate a Sudoku board with sets, decide the winner of a tic-tac-toe game, and find the maximum-sum rectangle by reducing a 2D problem to the 1D Kadane algorithm. If grids still feel awkward, revisit Matrices and 2D Arrays first.

Pascal's triangle

Pascal's triangle starts with 1. Every other entry is the sum of the two entries above it, and the edges are always 1. Row k (counting from 0) holds the binomial coefficients C(k, 0) .. C(k, k). The triangle is also the smallest example of building a table from the previous row, which is the heart of dynamic programming.

Python Pascal's triangle, row by row

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because each row only needs the one before it, you can keep a single row in memory. The sum of row k is 2**k, which is a handy self-check.

Odd magic square

A magic square of size n contains the numbers 1 .. n*n so that every row, every column and both diagonals add up to the same number, n * (n*n + 1) / 2. For odd n there is a simple construction called the Siamese method:

  1. Put 1 in the middle of the top row.
  2. Move one step up and one step right, wrapping around the edges, and write the next number.
  3. If that cell is already filled, move down one row from the previous cell instead.
Python Siamese method and a magic check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The modulo operator does the wrapping for you; Python's % returns a non-negative result for a negative left side, so (0 - 1) % 5 is 4.

Toeplitz matrix

A matrix is Toeplitz if every top-left to bottom-right diagonal holds one repeated value. In other words m[r][c] == m[r-1][c-1] for every cell that has an up-left neighbour. That gives a one-pass, O(m * n) test with no extra memory.

Valid Sudoku

A partly filled 9x9 board is valid if no row, column or 3x3 box repeats a digit (empty cells are .). This only validates the numbers placed so far; it does not solve the puzzle (for solving, see Sudoku and Puzzles). The trick is the box index: the cell (r, c) belongs to box (r // 3) * 3 + c // 3. Keep one set per row, column and box.

Python Toeplitz check and Sudoku validation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tic-tac-toe winner

A 3x3 board has only eight winning lines: three rows, three columns and two diagonals. A clean solution lists those lines as coordinates and checks them. Writing the lines as data keeps the logic small, and it generalizes to an n x n board if you build the lines with comprehensions.

Python Who has won?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Maximum-sum rectangle

Given a matrix of positive and negative numbers, find the rectangle (a block of consecutive rows and columns) with the largest sum. A brute force over all rectangles with prefix sums is O(m^2 * n^2). The classic improvement:

  1. Fix a pair of rows top <= bottom.
  2. Collapse those rows into a 1D array col[c] = sum of grid[top..bottom][c].
  3. Run Kadane's algorithm on that array; it gives the best column range for this row pair.

Updating col while bottom moves down costs O(n), so the total is O(m^2 * n). Make m the smaller dimension (transpose first if needed).

Python Max-sum rectangle by compressing rows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a 2D problem asks for the best sub-rectangle, "fix two boundaries and solve the rest as a 1D problem" is the usual reduction.

Common mistakes

  • Forgetting that Python indexes wrap. sq[-1] is the last row, so explicit bounds checks matter wherever you do not use % on purpose.
  • Using [[0]*n]*n. Rows are shared; always use a comprehension.
  • Wrong box index in Sudoku. It is (r // 3) * 3 + c // 3, not r // 3 + c // 3.
  • Mixing up the two diagonals. r == c is the main one, r + c == n - 1 the other.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the sum of all entries in row k (from 0) of Pascal's triangle?

    Row k lists C(k, 0) through C(k, k), and these binomial coefficients add up to 2**k.
  2. 2. In the Siamese method for an odd magic square, what do you do when the up-right cell is already filled?

    The rule is: up and right, wrapping at the edges; if occupied, step down from the cell you just wrote.
  3. 3. Which box does the cell (r, c) of a 9x9 Sudoku board belong to?

    Integer division by 3 gives the box row and box column; multiplying the box row by 3 and adding the box column numbers the nine boxes 0 to 8.
  4. 4. What is the time complexity of the max-sum rectangle method that fixes two rows and runs Kadane on the compressed columns?

    There are O(m^2) row pairs, and each is processed in O(n) (updating the column sums and running Kadane).

Summary

  • Pascal's triangle builds each row from the previous one; row k sums to 2**k.
  • The Siamese method fills an odd magic square using "up-right with wrap, else down".
  • A Toeplitz matrix satisfies m[r][c] == m[r-1][c-1] everywhere.
  • Validate Sudoku with one set per row, column and box, using box index (r // 3) * 3 + c // 3.
  • List the winning lines of tic-tac-toe as data and check them in a loop.
  • Max-sum rectangle: fix two rows, collapse them to a 1D array, run Kadane, for O(m^2 * n).

Next: Next Permutation, another array trick built on careful index reasoning.