# Jagged Array

# Jagged Array

A jagged array stores a collection of rows where each row can have a different length. It is usually represented as an array of arrays.

You use it when the data is grouped by row, but each group may contain a different number of elements.

## Problem

Given a jagged array $A$, support reading and writing an element at row $i$ and column $j$ where:

$$
0 \le i < rows(A)
$$

and

$$
0 \le j < length(A[i])
$$

## Structure

A jagged array stores each row separately:

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

Rows do not need the same length.

## Algorithm

Read an element:

```id="jagged-get"
get(A, i, j):
    if i < 0 or i >= rows(A):
        error "row index out of bounds"
    if j < 0 or j >= length(A[i]):
        error "column index out of bounds"
    return A[i][j]
```

Write an element:

```id="jagged-set"
set(A, i, j, x):
    if i < 0 or i >= rows(A):
        error "row index out of bounds"
    if j < 0 or j >= length(A[i]):
        error "column index out of bounds"
    A[i][j] = x
```

## Example

Let

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

To read position $(2, 1)$:

| step | action       | result        |
| ---- | ------------ | ------------- |
| 1    | check row    | $0 \le 2 < 3$ |
| 2    | check column | $0 \le 1 < 2$ |
| 3    | read value   | $4$           |

Return $4$.

## Correctness

The row bounds check ensures that $A[i]$ exists. The column bounds check ensures that index $j$ exists inside that specific row. Since each row owns its own storage, reading or writing $A[i][j]$ affects exactly the requested element.

## Complexity

| operation         | time             |
| ----------------- | ---------------- |
| get               | $O(1)$           |
| set               | $O(1)$           |
| append row        | $O(1)$ amortized |
| scan all elements | $O(m)$           |

Here $m$ is the total number of stored elements across all rows.

Space usage:

$$
O(m + r)
$$

where $r$ is the number of rows.

## When to Use

Jagged arrays are appropriate when:

* rows have different lengths
* rectangular storage would waste space
* each row is processed independently
* adjacency lists or grouped records are needed

They are less suitable when uniform matrix operations or cache-friendly full-row scans dominate.

## Implementation

```python id="jagged-python"
class JaggedArray:
    def __init__(self):
        self.rows = []

    def append_row(self, row):
        self.rows.append(list(row))

    def get(self, i, j):
        if i < 0 or i >= len(self.rows):
            raise IndexError("row index out of bounds")
        if j < 0 or j >= len(self.rows[i]):
            raise IndexError("column index out of bounds")
        return self.rows[i][j]

    def set(self, i, j, x):
        if i < 0 or i >= len(self.rows):
            raise IndexError("row index out of bounds")
        if j < 0 or j >= len(self.rows[i]):
            raise IndexError("column index out of bounds")
        self.rows[i][j] = x
```

```go id="jagged-go"
type JaggedArray[T any] struct {
    rows [][]T
}

func (j *JaggedArray[T]) AppendRow(row []T) {
    copied := make([]T, len(row))
    copy(copied, row)
    j.rows = append(j.rows, copied)
}

func (j *JaggedArray[T]) Get(i, k int) (T, bool) {
    var zero T
    if i < 0 || i >= len(j.rows) {
        return zero, false
    }
    if k < 0 || k >= len(j.rows[i]) {
        return zero, false
    }
    return j.rows[i][k], true
}

func (j *JaggedArray[T]) Set(i, k int, x T) bool {
    if i < 0 || i >= len(j.rows) {
        return false
    }
    if k < 0 || k >= len(j.rows[i]) {
        return false
    }
    j.rows[i][k] = x
    return true
}
```