Two-Dimensional Arrays

A two-dimensional (2D) array is an array of arrays, where each element of the main array is another array. It's often visualized as a table or matrix with rows and columns. Two-dimensional arrays are essential in various algorithmic problems, particularly when handling matrices, grids, and dynamic programming solutions.

In this guide, we will cover the fundamentals of two-dimensional arrays, their applications, and common operations used in data structures and algorithms (DSA).

Learning Information​

Progress Tracker​

• Understood 2D array structure
• Practiced traversal techniques
• Implemented matrix operations
• Solved matrix-based problems

1. Video Explanation​

Watch

2. What is a Two-Dimensional Array?​

A two-dimensional array is an array that consists of a collection of elements arranged in rows and columns. Each element can be accessed using two indices – one representing the row and the other representing the column.

Representation:​

• A two-dimensional array can be visualized as:

  [a11, a12, a13]
  [a21, a22, a23]
  [a31, a32, a33]
  

Here, each row is an individual array, and all rows combined form the 2D array.

3. Declaration and Initialization of 2D Arrays​

Declaration:​

In most programming languages, a 2D array is declared by specifying the number of rows and columns. For example, in C++:

int arr[3][4];  // Declares a 2D array with 3 rows and 4 columns

In Python, a 2D array can be initialized using nested lists:

arr = [[0] * 4 for _ in range(3)]  # Creates a 3x4 matrix filled with zeros

Initialization:​

2D arrays can be initialized at the time of declaration:

int arr[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

4. Accessing and Modifying Elements in a 2D Array​

Each element in a 2D array is accessed using two indices – the first for the row and the second for the column.

Example:​

int element = arr[1][2];  // Accesses the element at row 1, column 2
arr[0][1] = 10;           // Modifies the element at row 0, column 1

In Python:

element = arr[1][2]
arr[0][1] = 10

5. Traversing a 2D Array​

Traversing a 2D array involves visiting each element of the array. Typically, this is done using nested loops, where the outer loop iterates over the rows, and the inner loop iterates over the columns.

Example in C++:​

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < columns; j++) {
        cout << arr[i][j] << " ";
    }
    cout << endl;
}

Example in Python:​

for row in arr:
    for element in row:
        print(element, end=" ")
    print()

6. Common Operations on 2D Arrays​

a. Matrix Addition​

Two matrices of the same dimensions can be added element-wise.

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < columns; j++) {
        result[i][j] = matrix1[i][j] + matrix2[i][j];
    }
}

b. Matrix Multiplication​

Matrix multiplication is performed by multiplying the rows of the first matrix by the columns of the second matrix.

for (int i = 0; i < rowsA; i++) {
    for (int j = 0; j < colsB; j++) {
        result[i][j] = 0;
        for (int k = 0; k < colsA; k++) {
            result[i][j] += matrixA[i][k] * matrixB[k][j];
        }
    }
}

c. Transposing a Matrix​

Transposing a matrix involves flipping its rows and columns.

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < columns; j++) {
        transpose[j][i] = matrix[i][j];
    }
}

7. Applications of 2D Arrays in DSA​

• Dynamic Programming: Many DP problems such as "Knapsack", "Longest Common Subsequence", and "Edit Distance" utilize 2D arrays to store solutions to subproblems.
• Graph Representation: Adjacency matrices use 2D arrays to represent graphs.
• Image Processing: A grayscale image can be represented as a 2D array of pixel intensities.
• Game Boards: Games like chess and tic-tac-toe use 2D arrays to represent the game board.
• Mathematical Operations: Matrix operations like addition, multiplication, and transposition are fundamental in linear algebra and often implemented using 2D arrays.

8. Example Problems​

Problem 1: Rotating a Matrix by 90 Degrees​

Given a n x n matrix, rotate the matrix by 90 degrees clockwise.

Problem 2: Spiral Matrix Traversal​

Given a matrix, print the elements in a spiral order starting from the top-left corner.

Problem 3: Find the Largest Island​

Given a binary matrix where 1 represents land and 0 represents water, find the largest connected land mass (island).

Problem 4: Matrix Multiplication​

Write a program to multiply two matrices of dimensions m x n and n x p.

Conclusion​

Two-dimensional arrays are a foundational data structure in computer science, used in a variety of real-world applications, including graph theory, dynamic programming, and game development. By understanding how to declare, traverse, and manipulate 2D arrays, you can effectively solve complex problems in DSA.