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:

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:

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

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

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
}