Categories: Data Structure

DSA: 2D Array

What is a 2D Array?
  • A 2D matrix is a two-dimensional array that contains rows and columns in data structures and methods. It is also known as a two-dimensional array.
  • A matrix can be represented in code as a 2D array, where each element of the array is itself an array, and each row of the matrix is represented by an inner array.
  • Column major matrix is a two-dimensional array in which entries are stored column by column.
  • Row major matrix is a two-dimensional array in which elements are stored row by row.

Let’s understand it better through the given diagram:

Note: Working with 2D matrices frequently involves iterating over the matrix’s rows and columns and executing operations on the individual elements.

Need of 2D Arrays in DSA:

Here are some of the reasons why 2D arrays are important in data structures and algorithms:

  • Storing and accessing data
  • Image processing where images are represented as matrices of pixel values.
  • Graphs can be represented using 2D arrays where the rows and columns represent the vertices, and the elements represent the edges connecting the vertices.
  • Two-dimensional arrays are used in dynamic programming where the problem is solved by breaking it down into smaller subproblems that are solved and stored in a 2D table.
  • Matrices can be represented as 2D arrays in algorithms such as matrix multiplication, Gaussian elimination, and matrix inversion.

Let us now discuss various 2D matrix examples:

Program to return all elements of the matrix in spiral order:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Solution:

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) 
{
     int n = matrix.length;
    int m = matrix[0].length;
    ArrayList<Integer> arr = new ArrayList<>();
    int top = 0 ;
    int bottom = n-1;
    int right = m-1;
    int left = 0;
    while(top<=bottom && left<=right){
       for(int i = left ; i<=right ;i++){
            arr.add(matrix[top][i]);    
         }
        top++;
        for(int i  = top ;i<=bottom;i++ ){
            arr.add(matrix[i][right]);
        }
        right--;
        if(top<=bottom){
            for(int i = right;i>=left;i--){
                arr.add(matrix[bottom][i]);
            }
            bottom--;
        }
      if(left<=right){

            for(int i = bottom;i>=top;i--){
                arr.add(matrix[i][left]);
            }
            left++;
        }
    }
    return arr;
}
     public static void main(String[] args) {
     Solution obj= new Solution();
     Scanner sc= new Scanner (System.in);
     int array[][] = new int[3][3];   
    // Read the matrix values   
    System.out.println("Enter the elements of the array: ");   
      //loop for row  
    for (int i = 0; i < 3; i++)   {
      //inner for loop for column  
      for (int j = 0; j < 3; j++)   
        array[i][j] = sc.nextInt(); 
      }     
      System.out.println(obj.spiralOrder(array));
    }
 }

To print the matrix in spiral the loop iterates through the matrix in four directions:

  1. Traverse from left to right: This loop iterates from left to right, adding each element to the arr ArrayList.
  2. Traverse from top to bottom: This loop iterates from top to bottom, adding each element to the arr ArrayList.
  3. Traverse from right to left: This loop iterates from right to left, adding each element to the arr ArrayList.
  4. Traverse from bottom to top: This loop iterates from bottom to top, adding each element to the arr ArrayList.
Program to rotate the image by 90 degrees (clockwise):
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Solution:

public class Solution {
    public void rotate(int[][] M) {
        for (int i = 0; i < (M.length+1)/2; i++) {
            for (int j = 0; j < M.length/2; j++) {
                int tmp = M[i][j];
                M[i][j] = M[M.length-j-1][i];
                M[M.length-j-1][i] = M[M.length-i-1][M.length-j-1];
                M[M.length-i-1][M.length-j-1] = M[j][M.length-i-1];
                M[j][M.length-i-1] = tmp;
            }
        }
    }
}

Instead of using the longer method, the approach used in this solution is to divide the matrix into smaller concentric squares and rotate each square individually. That is,

  • The outermost square is rotated first, followed by the next inner square, and so on.
  • For each square, we use four temporary variables to store the values of the four corners, and then perform a cyclic rotation of the values in that square.

Note: also read about DSA: SubArray

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py

Recent Posts

Generate Parenthesis | Intuition + Code | Recursion Tree | Backtracking | Java

Problem Statement: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example…

2 months ago

Square Root of Integer

Given an integer A. Compute and return the square root of A. If A is…

1 year ago

Build Array From Permutation

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where…

1 year ago

DSA: Heap

A heap is a specialized tree-based data structure that satisfies the heap property. It is…

1 year ago

DSA: Trie

What is a Trie in DSA? A trie, often known as a prefix tree, is…

1 year ago

Trees: Lowest Common Ancestor

What is the Lowest Common Ancestor? In a tree, the lowest common ancestor (LCA) of…

1 year ago