Chapter 11: 2D Arrays

Continuing my journey with DSA in Java, I am excited to delve into the world of 2D Arrays. This chapter will explore a key concept in data structures that is both foundational and extremely useful in solving complex problems. Let's walk through the concept of 2D arrays, their real-life applications, representation, creation, and usage in memory. We will also dive into some interesting problems like Spiral Matrix, Diagonal Sum, and searching in a Sorted Matrix, with clear code examples to help understand how these concepts work in Java.

---

1. Introduction to 2D Arrays

In our studies in the 11th and 12th grades, we learned about matrices, which are essentially collections of numbers arranged in rows and columns. A matrix is represented as ( m * n ) (read as "m by n"), where ( m ) denotes the number of rows and ( n ) denotes the number of columns.

Understanding Multi-Dimensional Arrays

To grasp the concept of multi-dimensional arrays, let’s visualize how arrays can be structured:

• 1D Array: This is a simple linear array with a single dimension.

    1D:  [1, 2, 3]
  

• 2D Array: A two-dimensional array can be visualized as a grid or a table, where data is organized in rows and columns.

    2D: 
         [1, 3, 4]
         [5, 6, 7]
  

• 3D Array: A three-dimensional array can be thought of as a collection of 2D arrays stacked on top of each other. You can visualize it like a cube, where each layer of the cube is a 2D array.

    3D: 
         Layer 1:  [1, 3, 4]
                    [5, 6, 7]
  
         Layer 2:  [8, 9, 10]
                    [11, 12, 13]
  

This concept can extend further into 4D, 5D, and even n-D arrays, though such higher dimensions are less commonly used in typical programming tasks. They often find application in specialized fields like machine learning, where multi-dimensional arrays can represent complex data structures, such as tensors.

2D Arrays in Java

A 2D array in Java is an array that stores multiple arrays as its elements. This allows us to store data in a matrix-like structure, where each element can be accessed using two indices: one for the row and another for the column. This structure is incredibly useful when dealing with grids, tables, or any organized data format requiring both rows and columns.

---

2. Real Life Examples

Real-Life Examples of 2D Arrays

Example 1: Storing Student Marks

Let's consider an example involving students and their marks. If we want to store the marks of 10 students for 5 subjects, we can effectively use a 2D array to represent this data. Each row of the 2D array corresponds to a student, while each column corresponds to the marks obtained in a specific subject.

Here’s how the data structure would look:

Student Marks (10 students, 5 subjects):
[
    [85, 90, 78, 92, 88],  // Student 1
    [76, 82, 85, 90, 89],  // Student 2
    [91, 87, 88, 76, 84],  // Student 3
    [65, 70, 75, 80, 85],  // Student 4
    [88, 92, 91, 90, 93],  // Student 5
    [79, 85, 80, 82, 78],  // Student 6
    [92, 94, 95, 90, 89],  // Student 7
    [73, 68, 75, 72, 77],  // Student 8
    [81, 83, 87, 85, 88],  // Student 9
    [78, 80, 75, 70, 72]   // Student 10
]

In this example:

• Each row corresponds to a student.

• Each column represents marks in a specific subject.

• This structure allows us to easily access and manipulate the marks of any student for any subject.

Example 2: RGB Color Representation

Another real-life application of 2D arrays is in color representation on screens, particularly using the RGB color model. In digital images, colors are often represented by the combination of Red, Green, and Blue values.

For example, consider a single pixel in an image:

• White color can be represented as RGB (255, 255, 255).

• To represent the color values for an image, we can use three separate 2D arrays: one for Red, one for Green, and one for Blue.

Here’s how it can be visualized:

• Red Array:

[
    [255, 0, 0],   // Pixel (0,0)
    [0, 255, 0],   // Pixel (0,1)
]

• Green Array:

[
    [0, 255, 0],   // Pixel (0,0)
    [255, 0, 0],   // Pixel (0,1)
]

• Blue Array:

[
    [0, 0, 255],   // Pixel (0,0)
    [255, 255, 255] // Pixel (0,1)
]

In this setup:

• Each pixel in an image can be represented using a combination of values from these three 2D arrays.

• For example, the pixel at position (0,0) can be defined by accessing values from all three arrays: Red (255), Green (0), Blue (0), which corresponds to the color Red.

This RGB model allows for the creation of millions of colors by varying the intensity of Red, Green, and Blue for each pixel, making it an essential concept in graphics programming and image processing.

---

3. Representation of 2D Arrays

To represent a 2D array as a matrix, let’s create a box structure of size 4 rows and 3 columns. This can be visualized as follows:

Structure of a 2D Array (4x3)

• Rows: 4 (left to right)

• Columns: 3 (top to bottom)

The cells in this structure can be indexed using two coordinates: the first index represents the row, and the second index represents the column. Here’s how we can visualize it:

          Column 0    Column 1    Column 2
Row 0      (0,0)       (0,1)       (0,2)
Row 1      (1,0)       (1,1)       (1,2)
Row 2      (2,0)       (2,1)       (2,2)
Row 3      (3,0)       (3,1)       (3,2)

Visual Representation

+-------+-------+-------+
| (0,0) | (0,1) | (0,2) |
+-------+-------+-------+
| (1,0) | (1,1) | (1,2) |
+-------+-------+-------+
| (2,0) | (2,1) | (2,2) |
+-------+-------+-------+
| (3,0) | (3,1) | (3,2) |
+-------+-------+-------+

Explanation

• Each cell is represented by its coordinates (row, column).

• The total number of cells in this 2D array is calculated as:

  No. Of Cells: Rows * Columns

---

4. Creation of 2D Arrays

Declaration

To declare a 2D array in Java, use the following syntax:

int[][] matrix = new int[3][3];  // Declares a 3x3 2D array

Input

When filling the 2D array with data, it’s common to go through the array row-wise, then column-wise. Here’s how to take input using a Scanner:

Scanner sc = new Scanner(System.in);
for (int i = 0; i < n; i++) { // n is the number of rows
    for (int j = 0; j < m; j++) { // m is the number of columns
        matrix[i][j] = sc.nextInt(); // Assign input to each cell
    }
}

Calculating Length

To get the number of rows and columns in the matrix, use:

int n = matrix.length; // Number of rows
int m = matrix[0].length; // Number of columns

Output

To display the contents of the 2D array, you can use nested loops:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        System.out.print(matrix[i][j] + " "); // Print each element
    }
    System.out.println(); // New line after each row
}

Complete Code Example

import java.util.Scanner;

public class Creation {

    public static void main(String[] args) {
        // Creation of 2D Arrays
        int[][] matrix = new int[3][3];
        int n = matrix.length;
        int m = matrix[0].length;

        // For input
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter elements for a 3x3 matrix:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt(); // Assign input to each cell
            }
        }

        // For output
        System.out.println("The 3x3 matrix is:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(matrix[i][j] + " "); // Print each element
            }
            System.out.println(); // New line after each row
        }


    }
}

Sample Input and Output

Input:

Enter elements for a 3x3 matrix:
1 2 3
4 5 6
7 8 9

Output:

The 3x3 matrix is:
1 2 3 
4 5 6 
7 8 9

Homework Assignment

Task 1: Find the Largest Element in a 2D Array

Write a Java program that reads a 3x3 matrix from user input and finds the largest element in the matrix.

Code:

import java.util.Scanner;

public class LargestElementFinder {

    public static void largest(int matrix[][]) {
        int max = Integer.MIN_VALUE; // Initialize max with the smallest possible integer
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] > max) {
                    max = matrix[i][j]; // Update max if current element is larger
                }
            }
        }
        System.out.println("Largest element found: " + max);
    }

    public static void main(String[] args) {
        // Creation of 2D Arrays
        int[][] matrix = new int[3][3];
        Scanner sc = new Scanner(System.in);

        // For input
        System.out.println("Enter elements for a 3x3 matrix:");
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                matrix[i][j] = sc.nextInt(); // Assign input to each cell
            }
        }

        // Find largest element
        largest(matrix);
    }
}

Sample Input:

Enter elements for a 3x3 matrix:
1 4 3
9 2 6
5 8 7

Output:

Largest element found: 9

---

Task 2: Find the Smallest Element in a 2D Array

Write a Java program that reads a 3x3 matrix from user input and finds the smallest element in the matrix.

Code:

import java.util.Scanner;

public class SmallestElementFinder {

    public static void smallest(int matrix[][]) {
        int min = Integer.MAX_VALUE; // Initialize min with the largest possible integer
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] < min) {
                    min = matrix[i][j]; // Update min if current element is smaller
                }
            }
        }
        System.out.println("Smallest element found: " + min);
    }

    public static void main(String[] args) {
        // Creation of 2D Arrays
        int[][] matrix = new int[3][3];
        Scanner sc = new Scanner(System.in);

        // For input
        System.out.println("Enter elements for a 3x3 matrix:");
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                matrix[i][j] = sc.nextInt(); // Assign input to each cell
            }
        }

        // Find smallest element
        smallest(matrix);
    }
}

Sample Input:

Enter elements for a 3x3 matrix:
1 4 3
9 2 6
5 8 7

Output:

Smallest element found: 1

---

5. How 2D Arrays are Stored in Memory?

When we talk about how 2D arrays are stored in memory, it's important to understand that they are stored in a linear, contiguous block of memory, similar to 1D arrays. However, the way we access and visualize them as two dimensions leads us to the concept of row-major order and column-major order.

1. Row-Major Order

In row-major order, the elements of the rows of the array are stored in contiguous memory locations. This means that all the elements of the first row are stored first, followed by all the elements of the second row, and so on.

Example:

Let's consider a 2D array with the following structure:

Index:   0   1   2
Row 0:   0   1   2
Row 1:   3   4   5
Row 2:   6   7   8

In a 2D array like the one above, when stored in memory using row-major order, the elements are arranged as follows:

• Memory Representation:

Address:  100   104   108   112   116   120   124   128   132
Values:     0     1     2     3     4     5     6     7     8

Here’s the breakdown:

• The first row (0, 1, 2) is stored in memory at addresses 100, 104, and 108.

• The second row (3, 4, 5) is stored at addresses 112, 116, and 120.

• The third row (6, 7, 8) is stored at addresses 124, 128, and 132.

2. Memory Calculation in Row-Major Order

To access an element in a 2D array stored in row-major order, we can use the following formula to calculate the address of the element at position (i, j):

Address of A[i][j] = BaseAddress + ((i * NumberOfColumns) + j) * SizeOfDataType

• BaseAddress: The starting address of the array in memory.

• i: The row index.

• j: The column index.

• NumberOfColumns: The total number of columns in the array.

• SizeOfDataType: The size of each element in the array (for example, 4 bytes for an int).

For our example:

• If BaseAddress = 100 (starting address of the array)

• NumberOfColumns = 3 (since there are 3 columns)

• SizeOfDataType = 4 bytes (for integers)

Using the formula, the address for the element A[1][2] (which is 5) can be calculated as:

Address of A[1][2] = 100 + ((1 * 3) + 2) * 4
                    = 100 + (3 + 2) * 4
                    = 100 + 20
                    = 120

3. Column-Major Order (For Contrast)

Though Java uses row-major order, it's worth mentioning that some programming languages, like Fortran, use column-major order. In this method, the elements of the columns are stored in contiguous memory locations.

For the same 2D array, the column-major order would be represented as:

• Memory Representation:

Address:  100   104   108   112   116   120   124   128   132
Values:     0     3     6     1     4     7     2     5     8

Memory Calculation in Column-Major Order:

The formula for column-major order would be:

Address of A[i][j] = BaseAddress + ((j * NumberOfRows) + i) * SizeOfDataType

Understanding how 2D arrays are stored in memory is crucial for optimizing algorithms that access these arrays, as it affects cache performance and overall computational efficiency. In summary, 2D arrays are stored in a linear format in memory, primarily in row-major order in languages like Java, which simplifies memory management and element access while maintaining the logical 2D structure we utilize in programming.

---

6. Spiral Matrix

A spiral matrix problem is a common interview question. The idea is to traverse a 2D array in a spiral order (clockwise direction starting from the top-left corner).

For example, given the matrix:

1  2  3
4  5  6
7  8  9

The spiral traversal would output: 1, 2, 3, 6, 9, 8, 7, 4, 5.

---

7. Spiral Matrix Code

Below is the Java code to print a 2D array in a spiral order:

public class SpiralMatrix {
    public static void printSpiral(int[][] matrix) {
        if (matrix.length == 0) return;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            // Traverse from left to right
            for (int i = left; i <= right; i++) {
                System.out.print(matrix[top][i] + " ");
            }
            top++;

            // Traverse downwards
            for (int i = top; i <= bottom; i++) {
                System.out.print(matrix[i][right] + " ");
            }
            right--;

            if (top <= bottom) {
                // Traverse from right to left
                for (int i = right; i >= left; i--) {
                    System.out.print(matrix[bottom][i] + " ");
                }
                bottom--;
            }

            if (left <= right) {
                // Traverse upwards
                for (int i = bottom; i >= top; i--) {
                    System.out.print(matrix[i][left] + " ");
                }
                left++;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        printSpiral(matrix);
    }
}

---

8. Diagonal Sum

Another common problem with 2D arrays is calculating the sum of diagonal elements.

For example, given this matrix:

1  2  3
4  5  6
7  8  9

The primary diagonal elements are: 1, 5, 9, and the secondary diagonal elements are: 3, 5, 7.

• Primary Diagonal Sum: 1 + 5 + 9 = 15

• Secondary Diagonal Sum: 3 + 5 + 7 = 15

---

9. Search in Sorted Matrix

In a sorted matrix, each row and column are sorted in ascending order. The challenge is to find an element in this matrix efficiently.

---

10. Search in Sorted Matrix Code

Here's the Java code to search for an element in a sorted matrix:

public class SortedMatrixSearch {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].length - 1;

        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {10, 20, 30, 40},
            {15, 25, 35, 45},
            {27, 29, 37, 48},
            {32, 33, 39, 50}
        };
        int target = 29;
        boolean found = searchMatrix(matrix, target);
        System.out.println("Element found: " + found);
    }
}

---

Assignment Problems

• Create a 2D array and find the transpose of the matrix.

• Implement a function that rotates a 2D matrix by 90 degrees clockwise.

• Solve the Spiral Matrix problem for larger matrices.

---

This concludes Chapter 11 of DSA in Java. Stay tuned for more insightful chapters ahead!

Related Posts in My Series:

DSA in Java Series:

• Chapter 2: Operators in Java – Learn about the different types of operators in Java, including arithmetic, relational, logical, and assignment operators, along with examples to understand their usage.

• Chapter 33: Trie in Java – Explore the implementation and use of Trie data structure in Java, a powerful tool for handling strings, with practical coding examples.

Other Series:

• Full Stack Java Development – Master the essentials of Java programming and web development with this series. Topics include object-oriented programming, design patterns, database interaction, and more.

• Full Stack JavaScript Development – Become proficient in JavaScript with this series covering everything from front-end to back-end development, including frameworks like React and Node.js.

---

Connect with Me
Stay updated with my latest posts and projects by following me on social media:

• LinkedIn: Connect with me for professional updates and insights.

• GitHub: Explore my repositories and contributions to various projects.

• LeetCode: Check out my coding practice and challenges.

Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast