2-D Arrays

What are 2-D Arrays?

Two-dimensional arrays can be defined as several arrays within an array. 2D arrays are a collection of rows and columns. It is very common to design 2D arrays to accomplish a task of building a database that is similar to the data structure.

Source

The Need for 2-D Arrays:

Using 2-D arrays, you can store so much data at one moment, which can be passed at any number of functions whenever required.

Declaration & Initialisation of a 2-D Array:

//Syntax for declaration
data_type[][] array_name = new data_type[x][y];


//For example: 
int[][] arr = new int[10][20];

/*In the below example, the name of the 2-D array is multi_dim consisting of
2 rows and 3 columns of integer data types. */

int multi_dim[2][3];


//To initialise a value at a particular index, the syntax is: 

array_name[row_index][column_index] = value;

//For example: 

arr[0][0] = 1;

Sample Problems:

1. Transpose a Matrix:

Transposing a matrix basically means to swap the values of its rows with the values of its columns.

For every cell result[i][j] we need to replace the value with input[j][i]where input is the matrix to be transposed and result is the placeholder for the transposed matrix

2. Search a 2-D Matrix:

We need to search for a specific value in a sorted matrix. A sorted matrix basically means that the value at the cell A[i][j] will always be greater than the values of all cells preceding(before) it. The basic approach for us to solve this is to iterate through each row and each column until we have the target element or reached the end of the sorted matrix.

3. Search a 2-D Matrix II:

Unlike a sorted matrix where all the elements are sorted, here a preceding(previous) row can have higher values than the rows following it. As a result, we cannot use a binary search algorithm to determine a particular row for searching the target.The values increase as we go downward and values decrease as we move towards left. Using this information we can use the same algorithm as used for Search in a 2D Matrix problem to solve this.

Source

4. Spiral Matrix:

Source

Step 1: Imagine we are solving this on paper in which case we can only move in 4 directions: we start with the right direction, then move downwards, then towards left and finally upwards(followed by right direction again).

Step 2: Consider the matrix to be the shrinking space between the boundaries that are moving in. We will know that we have traversed the entirety of the matrix when these boundaries meet.

Step 3: In Step 1,we discussed the directions to move in.Now,we determine how the boundaries change when we traverse in the specified directions (refer Step 1).

Step 4: To avoid traversing an element that we have already passed through — To do this we maintain another matrix where we store the information of which positions are already traversed with a boolean value.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer>ans=new ArrayList<>();
        int n=matrix.length;
        int m=matrix[0].length;

        int l=0,r=m-1; //col
        int t=0,b=n-1;//row

        int num=1;
        int dir=0; //direction
       /* dir1→ go right
           dir2→go down
        dir3→go left
       dir4→go up*/

        while(l<=r && t<=b){
            if(dir==0){
                for(int i=l;i<=r;i++){
                    ans.add(matrix[t][i]);
                }
                dir=1;
                t++; // increased row
            }
            else if(dir==1){
                for(int i=t;i<=b;i++){
                    ans.add(matrix[i][r]);
                }
                dir=2;
                r--;
            }
            else if(dir==2){
                for(int i=r;i>=l;i--){
                    ans.add(matrix[b][i]);
                }
                dir=3;
                b--;
            }
            else if(dir==3){
                for(int i=b;i>=t;i--){
                    ans.add(matrix[i][l]);
                }
                dir=0;
                l++;
            }
        }
        return ans;
    }
}

5. Diagonal Traverse:

Diagonally Up(DU), Diagonally Down(DD), Right(R) by 1 step, Down(D) by 1 step.

Source

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.