Two dimensional Array In Data Structure

A two-dimensional (2D) array is a data structure that organizes elements in a grid with rows and columns, forming a matrix. It is essentially an array of arrays, where each element is accessed using two indices: arr[row][col]. 2D arrays are widely used to represent tabular data, matrices, images, and game boards.

Structure of a 2D Array

A 2D array can be visualized as a table with m rows and n columns. The total number of elements is m × n.

     col0  col1  col2
row0 [ 1,   2,   3 ]
row1 [ 4,   5,   6 ]
row2 [ 7,   8,   9 ]

Access: arr[1][2] = 6  (row 1, column 2)

Declaration and Initialization

In Python (using nested lists)

# 2D array with 3 rows and 4 columns (initialized with zeros)
rows, cols = 3, 4
matrix = [[0 for _ in range(cols)] for _ in range(rows)]

# Initialized with values
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Using NumPy
import numpy as np
arr = np.array([[1, 2, 3], [4, 5, 6]])

In Java

// Declaration and initialization
int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// Declaration with size
int[][] matrix = new int[3][4];  // 3 rows, 4 columns
matrix[0][1] = 5;

// Ragged/Jagged array (different column lengths)
int[][] jagged = new int[3][];
jagged[0] = new int[2];
jagged[1] = new int[4];
jagged[2] = new int[3];

In C/C++

// Static 2D array
int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// Dynamic 2D array (heap)
int** matrix = new int*[rows];
for (int i = 0; i < rows; i++) {
    matrix[i] = new int[cols];
}

Memory Representation

2D arrays are stored in contiguous memory locations. There are two common ways to map 2D indices to memory addresses:

Row-Major Order

Elements are stored row by row. This is used in C, C++, Python (lists/NumPy), and Java (when using array of arrays).

For a 2D array: arr[rows][cols]
Address(arr[i][j]) = base_address + (i * cols + j) * element_size

Example: arr[2][3] in a 4×5 array
Offset = 2 * 5 + 3 = 13

Column-Major Order

Elements are stored column by column. This is used in Fortran, MATLAB, and some numerical computing libraries.

For a 2D array: arr[rows][cols]
Address(arr[i][j]) = base_address + (j * rows + i) * element_size

Example: arr[2][3] in a 4×5 array
Offset = 3 * 4 + 2 = 14

Common Operations

1. Traversal

def traverse_2d(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            print(matrix[i][j], end=" ")
        print()

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
traverse_2d(matrix)
# Output:
# 1 2 3
# 4 5 6
# 7 8 9

2. Matrix Addition

def matrix_add(A, B):
    rows = len(A)
    cols = len(A[0])
    result = [[0 for _ in range(cols)] for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            result[i][j] = A[i][j] + B[i][j]
    return result

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
print(matrix_add(A, B))  # Output: [[6, 8], [10, 12]]

3. Matrix Multiplication

def matrix_multiply(A, B):
    rows_A = len(A)
    cols_A = len(A[0])
    rows_B = len(B)
    cols_B = len(B[0])

    if cols_A != rows_B:
        return None  # Invalid multiplication

    result = [[0 for _ in range(cols_B)] for _ in range(rows_A)]
    for i in range(rows_A):
        for j in range(cols_B):
            for k in range(cols_A):
                result[i][j] += A[i][k] * B[k][j]
    return result

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
print(matrix_multiply(A, B))  # Output: [[19, 22], [43, 50]]

4. Matrix Transpose

def transpose(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    result = [[0 for _ in range(rows)] for _ in range(cols)]
    for i in range(rows):
        for j in range(cols):
            result[j][i] = matrix[i][j]
    return result

matrix = [[1, 2, 3], [4, 5, 6]]
print(transpose(matrix))  # Output: [[1, 4], [2, 5], [3, 6]]

5. Searching

def search_2d(matrix, target):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == target:
                return (i, j)
    return (-1, -1)  # Not found

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(search_2d(matrix, 5))  # Output: (1, 1)

Complexity Analysis

Applications

• Image Processing: Pixels are stored as 2D arrays (grayscale or RGB channels).
• Game Development: Game boards (chess, tic-tac-toe, Sudoku, Minecraft terrain).
• Scientific Computing: Matrices for linear algebra, physics simulations, finite element analysis.
• Spreadsheets: Tabular data representation.
• Computer Graphics: Transformation matrices, texture mapping.
• Geographic Information Systems (GIS): Grid-based terrain and map data.
• Machine Learning: Feature matrices, confusion matrices.
• Graph Representation: Adjacency matrices for weighted/unweighted graphs.

Advantages & Disadvantages

Advantages

• Structured data: Naturally represents tabular and grid data.
• Fast access: O(1) time to access any element using row and column indices.
• Cache-friendly: Contiguous memory allocation improves performance.
• Ease of use: Intuitive and widely supported in programming languages.

Disadvantages

• Fixed size: In many languages, the size is fixed at declaration (unless using dynamic structures).
• Memory overhead: May waste space if the matrix is sparse (many zeros).
• Row/column length restrictions: In languages with strict typing, all rows must have the same length (unless using jagged arrays).