A. Programming Concepts and Skills · Algorithm Design and Analysis

Two-Dimensional Arrays: Rows, Columns and Traversals

A3.5 C2.2About 70 minutes

Learning goals

I can create a 2-D array (a list of lists) safely and access element [r][c].
I can traverse a 2-D array by rows and by columns to find totals, averages and the largest element with its position.
I can write algorithms that scale every element, swap elements or rows, mirror and transpose a 2-D array.
I can state the Big-O of a 2-D traversal as O(rows × columns).

Words to know

two-dimensional (2-D) array
An array arranged in rows and columns; in Python, a list whose elements are lists of the same length.

row-major order
Visiting a 2-D array row by row: all of row 0, then all of row 1, and so on.

column-major order
Visiting a 2-D array column by column.

square matrix
A 2-D array with the same number of rows and columns.

transpose
Turning rows into columns: the element at [r][c] moves to [c][r].

aliasing
Two names (or two slots) referring to the same list object, so a change through one is seen through the other.

A month of snow

A school records the snowfall each day for four weeks. It is natural to write it as a table: one row per week, one column per day of the week. Now you can ask questions of the rows (which week was snowiest?), of the columns (do Sundays get more snow?) and of single cells (how much fell on the third Thursday?).

A table like this is a two-dimensional array. Expectation A3.5 asks you to create algorithms that process the elements of 2-D arrays: multiplying each element by a constant, interchanging elements, multiplying matrices and processing the pixels of an image. This lesson covers the core traversals and rearrangements; the next one does matrices and images.

A list of lists

Python has no special 2-D array type in the standard language. Instead, a 2-D array is a list of rows, and each row is a list:

snow[2] is row 2, a whole list: [15, 6, 0, 0, 2, 0, 1].
snow[2][5] is row 2, column 5: first pick the row, then the element in it.
Number of rows: len(snow). Number of columns: len(snow[0]) (all rows have the same length in a proper 2-D array).

Always write row first, then column: [r][c]. Mixing them up is the most common 2-D bug, and it often goes unnoticed on square arrays.

The snowfall array. A row (row 2, shaded blue) is a list you can get in one step. A column (column 5, shaded green) has to be collected element by element, one from each row. The yellow cell is where they cross.

Creating a 2-D array safely

Multiplying a list of lists by 3 copies the reference to the same row three times (aliasing). The list comprehension builds a new row for each r.

bad = [[0] * 3] * 3

good = [[0] * 3 for r in range(3)]

bad[0][0] = 7

good[0][0] = 7

print(bad)

print(good)

Output, one line each: [[7, 0, 0], [7, 0, 0], [7, 0, 0]], [[7, 0, 0], [0, 0, 0], [0, 0, 0]]. The bug in bad is hard to spot, because printing it before the change looks perfect.

[0] * 3 is fine for a 1-D list of numbers, because numbers are immutable. But [row] * 3 puts the same row object in all three slots. Use [[0] * cols for r in range(rows)] (or a loop that appends a new row each time) whenever you build a 2-D array.

Traversing: rows, columns and the whole grid

A traversal of every element uses nested loops: the outer loop over rows, the inner loop over columns (row-major order). To total each column, keep one running total per column, or swap the loops so the outer loop is over columns.

snow = [

[0, 2, 5, 0, 0, 12, 3], # week 1, Monday to Sunday (cm)

[1, 0, 0, 8, 4, 0, 0], # week 2

[15, 6, 0, 0, 2, 0, 1], # week 3

[0, 0, 3, 3, 0, 9, 20], # week 4

]

rows = len(snow)

cols = len(snow[0])

# row totals: one per week

for r in range(rows):

total = 0

for c in range(cols):

total += snow[r][c]

print("Week", r + 1, "total:", total, "cm")

# column totals: one per day of the week

days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]

col_totals = [0] * cols

for r in range(rows):

for c in range(cols):

col_totals[c] += snow[r][c]

print(days)

print(col_totals)

# the snowiest day and where it is

best_r, best_c = 0, 0

for r in range(rows):

for c in range(cols):

if snow[r][c] > snow[best_r][best_c]:

best_r, best_c = r, c

print("Most snow:", snow[best_r][best_c], "cm in week", best_r + 1, "on", days[best_c])

Output, one line each: Week 1 total: 22 cm, Week 2 total: 13 cm, Week 3 total: 24 cm, Week 4 total: 35 cm, ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun'], [16, 8, 8, 11, 6, 21, 24], Most snow: 20 cm in week 4 on Sun. Row totals, column totals, and the largest element with its position, all from nested loops.

Cost: every full traversal visits each of the rows × columns elements once, so it is O(rows × cols). For an n × n array that is O(n²), even though there is "only one pass": the input itself has n² elements. A 1920 × 1080 photo has over two million pixels, so even one pass over it is real work.

Multiplying every element by a constant

Scaling changes each element. You can change the array in place, or build a new array and leave the original unchanged. The postcondition must say which.

def scaled(grid, k):

"""Return a new 2-D array with every element multiplied by k.

Postcondition: grid is unchanged."""

return [[value * k for value in row] for row in grid]

def scale_in_place(grid, k):

"""Multiply every element of grid by k. Returns None."""

for r in range(len(grid)):

for c in range(len(grid[r])):

grid[r][c] *= k

cm = [[2, 5], [12, 0]]

mm = scaled(cm, 10)

print(cm, mm)

scale_in_place(cm, 10)

print(cm)

Output, one line each: [[2, 5], [12, 0]] [[20, 50], [120, 0]], [[20, 50], [120, 0]]. Note that for row in grid: for value in row: value *= k would not work: value is a loop variable holding a number, and changing it does not change the list. You need the indexes to assign back into the grid.

Interchanging elements

Swap two cells: g[r1][c1], g[r2][c2] = g[r2][c2], g[r1][c1].
Swap two rows: because rows are lists, swap the references: g[i], g[j] = g[j], g[i]. That is O(1)!
Swap two columns: there is no column object, so loop over rows and swap one element in each: O(rows).
Mirror (flip left to right): reverse every row: swap row[c] with row[cols - 1 - c] for c in the left half.
Transpose: rows become columns. A new array has cols rows and rows columns, with t[c][r] = g[r][c]. For a square array you can transpose in place by swapping each pair above the diagonal with its mirror below it.

Worked example

Transpose a square grid in place

Write transpose_square(g) that transposes an n × n grid in place, and trace it on [[1, 2, 3], [4, 5, 6], [7, 8, 9]].

Element [r][c] must swap with [c][r]. Elements on the diagonal (r == c) stay put.
Each pair must be swapped exactly once. If you loop over every r and every c, each pair is swapped twice and the grid ends up unchanged! So only visit cells above the diagonal: c from r + 1 to n − 1.
def transpose_square(g): n = len(g) for r in range(n): for c in range(r + 1, n): g[r][c], g[c][r] = g[c][r], g[r][c]
Swaps made: (0,1)↔(1,0): 2 and 4; (0,2)↔(2,0): 3 and 7; (1,2)↔(2,1): 6 and 8. That is n(n − 1) ÷ 2 = 3 swaps, still O(n²).
Result: [[1, 4, 7], [2, 5, 8], [3, 6, 9]]. The first row is now the old first column.

[[1, 4, 7], [2, 5, 8], [3, 6, 9]], using 3 swaps. Looping c over all columns would undo every swap.

def transpose(g):

"""Return a new array with rows and columns exchanged (any shape)."""

rows, cols = len(g), len(g[0])

t = [[None] * rows for c in range(cols)]

for r in range(rows):

for c in range(cols):

t[c][r] = g[r][c]

return t

def mirror(g):

"""Reverse every row of g in place (flip left to right)."""

for row in g:

cols = len(row)

for c in range(cols // 2):

row[c], row[cols - 1 - c] = row[cols - 1 - c], row[c]

g = [[1, 2, 3], [4, 5, 6]]

print(transpose(g))

mirror(g)

print(g)

g[0], g[1] = g[1], g[0] # swap two rows

print(g)

Output, one line each: [[1, 4], [2, 5], [3, 6]], [[3, 2, 1], [6, 5, 4]], [[6, 5, 4], [3, 2, 1]]. A 2 × 3 array transposes to 3 × 2. mirror can use for row in g because it changes the row list through its own indexes.

Printing a grid neatly

print(grid) puts everything on one line. To see rows and columns, print one row per line and line up the columns with an f-string width, for example print(" ".join(f"{v:4}" for v in row)) for each row. Seeing the grid as a grid catches row/column mix-ups quickly.

Just for fun

Why did the 2-D array break up with the 1-D array?

It said, "I need someone with more depth. You only ever see things in one direction." (They are still on good terms: every row of a 2-D array is a 1-D array.)

Hands-on activity

Egg-carton grid and a weather table

You need: an empty egg carton with 2 rows of 6 cups (or a muffin tin), 12 small slips of paper, a pencil, and a computer with Python.

Label the carton's rows 0 and 1 and its columns 0 to 5. Write a number on each slip and put one in each cup. Copy the layout as a Python list of lists.
Have a family member call out positions like "row 1, column 4". Say the value, then check with Python: g[1][4].
Swap two rows in the carton (move all six slips). In Python it is one line: g[0], g[1] = g[1], g[0]. Why is Python's version so fast?
Mirror the carton (reverse each row). Count how many swaps you made (3 per row, 6 in total). Run mirror and compare.
Find a week of weather forecasts for your town (a weather website or app), and make a 7 × 2 array of [high, low] for each day. Write code for the average high, the average low, and the day with the biggest difference between high and low.

What to look for: row r, column c always written as [r][c]; the Python mirror makes cols // 2 swaps per row.

Your turn

For g = [[3, 8, 1], [4, 0, 9]], give len(g), len(g[0]), g[1] and g[0][2].

Write a loop that prints the sum of column 1 of g.

What is wrong with grid = [[""] * 3] * 3, and how do you fix it?

What is the Big-O of finding the largest element in an r × c array? In an n × n array?

Write one line that swaps rows 0 and 2 of g, and explain why it is O(1).

What does transpose([[1, 2], [3, 4], [5, 6]]) return?

Why does for value in row: value *= 2 not double the elements?

More practice: warm-up

In g[r][c], which index is the row?

Write code that creates a 4 × 5 array of zeros correctly.

How many elements does a 30 × 40 array have?

What is row-major order?

What happens to the diagonal elements when a square array is transposed?

More practice: on your own

Predict the output:

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

s = 0

for i in range(3):

s += g[i][i]

print(s)

Write col_max(g, c) that returns the largest value in column c.

Write swap_cols(g, a, b) that interchanges columns a and b. What is its Big-O?

A teacher stores marks as marks[student][test] for 25 students and 6 tests. Write expressions for (a) student 3's mark on test 0, (b) the number of tests.

Predict the output:

g = [[1, 2], [3, 4]]

h = g

h[0][0] = 9

k = [row[:] for row in g]

k[1][1] = 0

print(g, k)

Challenge

Write rotate_right(g) that returns a new n × n grid rotated 90° clockwise. (Hint: transpose, then mirror.) Check it on [[1, 2], [3, 4]].

Spiral order: describe an algorithm that prints a 2-D array's elements going around the outside clockwise, then the next ring in, and so on. What is its Big-O?

A "saddle point" is an element that is the smallest in its row and the largest in its column. Outline an O(rows × cols) algorithm to find all saddle points (a naive check of every cell against its whole row and column is O(rows × cols × (rows + cols))).

Check your understanding

Quiz

For g = [[5, 1, 7], [2, 8, 3]], what is g[1][2]?

Which expression gives the number of columns of a 2-D list g?

After g = [[0] * 2] * 2 and g[0][1] = 5, what is g?

What is the Big-O of adding up every element of an n × n array?

A square-transpose loop swaps g[r][c] with g[c][r] for every r and c. What happens?

Which one line interchanges rows i and j of a list-of-lists in O(1)?

For parents and teachers

Big idea: A3.5 asks students to create algorithms that process the elements of two-dimensional arrays. This lesson covers creation, traversal, totals and maximums, multiplying each element by a constant, and interchanging elements (cells, rows, columns, mirror, transpose). Matrix multiplication and image pixels follow in the next lesson. Big-O of 2-D traversals continues C2.2.

How to help: Use any grid at home: an egg carton, a muffin tin, a calendar page. Ask "What is at row 1, column 3?" and "How would the computer find the biggest number and where it is?"

Common difficulties:

Writing [c][r] instead of [r][c], which square test grids hide.
Creating rows with [[0] * n] * m (aliasing).
Trying to change elements through a for value in row loop variable.
Transposing in place by visiting every cell (which swaps each pair twice).