Multidimensional Array

A multidimensional array stores values using two or more indices. Although it is written as a grid, matrix, or tensor, memory is still linear. The indexing formula maps each logical position to one physical offset.

You use it when data has natural row, column, plane, or tensor structure.

Problem

Given a two-dimensional array $A$ with $r$ rows and $c$ columns, support reading and writing an element at position $(i, j)$ where

$$ 0 \le i < r $$

and

$$ 0 \le j < c $$

Structure

In row-major layout, rows are stored one after another:

$$ A = \begin{bmatrix} a_{0,0} & a_{0,1} & a_{0,2}
a_{1,0} & a_{1,1} & a_{1,2} \end{bmatrix} $$

The linear offset for position $(i, j)$ is:

$$ offset = i \cdot c + j $$

Algorithm

Read an element from a row-major two-dimensional array:

get(A, r, c, i, j):
    if i < 0 or i >= r:
        error "row index out of bounds"
    if j < 0 or j >= c:
        error "column index out of bounds"

    offset = i * c + j
    return A[offset]

Write an element:

set(A, r, c, i, j, x):
    if i < 0 or i >= r:
        error "row index out of bounds"
    if j < 0 or j >= c:
        error "column index out of bounds"

    offset = i * c + j
    A[offset] = x

Example

Let

$$ A = \begin{bmatrix} 8 & 3 & 5
1 & 9 & 4 \end{bmatrix} $$

Here $r = 2$ and $c = 3$.

To read position $(1, 1)$:

$$ offset = 1 \cdot 3 + 1 = 4 $$

The flat storage is:

$$ [8, 3, 5, 1, 9, 4] $$

step	action	result
1	check row	$0 \le 1 < 2$
2	check column	$0 \le 1 < 3$
3	compute offset	$4$
4	read flat index $4$	$9$

Return $9$.

Correctness

Row-major layout stores each row contiguously. Every full row before row $i$ contributes $c$ elements, so those rows contribute $i \cdot c$ positions. Column $j$ then adds $j$ more positions inside row $i$. Therefore, the offset $i \cdot c + j$ identifies exactly $A[i][j]$.

The bounds checks ensure that only valid row and column positions are accessed.

Complexity

operation	time
get	$O(1)$
set	$O(1)$
scan all elements	$O(rc)$

Space usage:

$$ O(rc) $$

When to Use

Multidimensional arrays are appropriate when:

data is naturally tabular or grid-shaped
dimensions are known or change rarely
fast indexed access is required
row-wise or block-wise traversal is common

They are less suitable when the data is very sparse. In that case, use a sparse matrix or coordinate representation.

Implementation

class Matrix:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.a = [None] * (rows * cols)

    def index(self, i, j):
        if i < 0 or i >= self.rows:
            raise IndexError("row index out of bounds")
        if j < 0 or j >= self.cols:
            raise IndexError("column index out of bounds")
        return i * self.cols + j

    def get(self, i, j):
        return self.a[self.index(i, j)]

    def set(self, i, j, x):
        self.a[self.index(i, j)] = x

type Matrix[T any] struct {
    data []T
    rows int
    cols int
}

func NewMatrix[T any](rows, cols int) *Matrix[T] {
    return &Matrix[T]{
        data: make([]T, rows*cols),
        rows: rows,
        cols: cols,
    }
}

func (m *Matrix[T]) index(i, j int) (int, bool) {
    if i < 0 || i >= m.rows {
        return 0, false
    }
    if j < 0 || j >= m.cols {
        return 0, false
    }
    return i*m.cols + j, true
}

func (m *Matrix[T]) Get(i, j int) (T, bool) {
    var zero T
    k, ok := m.index(i, j)
    if !ok {
        return zero, false
    }
    return m.data[k], true
}

func (m *Matrix[T]) Set(i, j int, x T) bool {
    k, ok := m.index(i, j)
    if !ok {
        return false
    }
    m.data[k] = x
    return true
}