Matrices and coordinate traversal

What is an array?

An array stores values in a sequence of numbered positions. A position is called an index. Indices usually start at 0: the first value is at index 0, the second at index 1. Knowing the index lets you go directly to that position; finding an unknown value may require checking many positions.

Example: In [4, 8, 15], index 1 contains 8. There are three elements, so the valid indices are 0, 1, and 2. A Python list is a dynamic array: its storage can grow when you append values.

Helpful before this chapter

If these ideas are new, begin with:

Programming foundations Time and space complexity

Understand the idea

A rectangular matrix has R rows, C columns, and coordinates 0≤r<R, 0≤c<C. Keep dimensions explicit. Transformations that assume a square require R=C. For a row-major flat representation, index=r*C+c and recovering coordinates uses r=index//C, c=index%C. This works only when C is the actual column count and every row has the same width.

Work through an example

Transposing [[1,2,3],[4,5,6]] produces [[1,4],[2,5],[3,6]]. Output (c,r) receives input (r,c); dimensions change from 2×3 to 3×2.

Time and space complexity

Θ(RC) time/output for this transpose; square in-place transpose O(1) auxiliary space.

Why it works

Each input coordinate maps to exactly one output coordinate.

Common mistakes

Swapping every symmetric pair twice undoes the transpose.
Jagged rows violate rectangular assumptions.

Chapter lab · Python implementation

Arrays make positions directly accessible. Our lab compacts a sorted list: read examines input; write marks the next output slot. Python lists are resizable arrays of references. Fixed-width address diagrams illustrate slots, rather than promising contiguous Python objects.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def compact_sorted(values):
    write = 0
    for read in range(len(values)):
        if write == 0 or values[read] != values[write-1]:
            values[write] = values[read]
            write += 1
    return write

def transpose(matrix):
    if not matrix:
        return []
    cols = len(matrix[0])
    if any(len(row) != cols for row in matrix):
        raise ValueError('rectangular matrix required')
    return [[matrix[r][c] for r in range(len(matrix))]
            for c in range(cols)]

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

a=[1,1,2,2,3]; k=compact_sorted(a)
assert a[:k]==[1,2,3]
assert compact_sorted([])==0
assert transpose([[1,2,3],[4,5,6]])==[[1,4],[2,5],[3,6]]
assert transpose([])==[]

CHECK YOUR UNDERSTANDING