# Multidimensional Array

# 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:

```id="4b7qn2"
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:

```id="7h2mka"
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

```id="mq7t0x"
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
```

```id="xp9d4v"
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
}
```