Data Structures and Algorithms(DSA) Concept- 2D Matrix -Part 1

Topic : Problems based on 2D matrix ; Search for element in sorted matrix , Print a matrix in spiral order.

2D Array

2D array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns.

Q 1. Search for a value in a 2D matrix with sorted rows and columns.

Eg :
A =  [
      [-10, -5, -2,  2,  4,  7],
      [ -7, -4, -1,  3,  6,  9],
      [ -2,  3,  5,  7, 11, 14],
      [  3,  6,  8, 11, 14, 17],
      [  7, 11, 12, 15, 19, 20],
      [ 10, 14, 18, 20, 24, 29]
     ]
// from the matrix we can infer that the rows and columns are sorted.

public void SearchValue(int[][] A, int V){

int i =0;            // initialise i with the first row index
int j=A[0].length-1; // initialise j with the last column 
                    // So A[i][j] will point to the top right element in 2D mat


boolean found=false; 

while(i<A.length && j>=0){
  if(A[i][j]==V){
   found=true;
  }
  else if(A[i][j]>V){
    j--;
  }else if(A[i][j]<V){
    i++;
  }
  
}
if(found==true){
  System.out.print("Value found in the Matrix");
}else{
  System.out.print("Value Not found in the Matrix");
}

}

TC : O (N+M)

SC : O(1)

Q 2. Given a binary matrix of 0’s and 1’s of size N x M.All the rows are sorted . Find the smallest row number which contains mas number of 1's.

Eg :

A =  [
      [  0,  0,  0,  0,  1,  1],
      [  0,  0,  0,  1,  1,  1],
      [  0,  0,  0,  1,  1,  1],
      [  0,  0,  0,  0,  0,  1],
      [  0,  1,  1,  1,  1,  1],
      [  0,  0,  1,  1,  1,  1]
     ]
// Ans : Row Index 4 

public void longestRow(int[][] A){

int ans=0;
int i= 0;
int j= A[0].length-1;

while(i>A.length && j>=0){
     
  if(A[i][j]==1){
    j--;
    ans=i;
   }else if(A[i][j]==0){
    i++
   }
}

System.out.print(ans);



}

TC : O (N+M)

SC : O(1)

Q 3. Given a matrix of size N x N ,print the elements in spiral order .

Eg :
A =  [
      [-10, -5, -2,  2,  4],
      [ -7, -4, -1,  3,  6],
      [ -2,  3,  5,  7, 11],
      [  3,  6,  8, 11, 14],
      [  7, 11, 12, 15, 19],
     ]

Ans : -10, -5, -2, 2, 4, 6, 11, 14, 19, 15, 12, 11, 7, 3, -2, -7, -4, -1, 3, 7
      
       11, 8, 6, 3, 5.

public void printBoundryElement(int[][] A){

  int i=0;
  int j=0;
  int N= A.length; 
  
  while(N>1){
 // while loop will help handle situations where N is odd.

 // print the spiral
    for( int k=1,k<N,k++){
        System.out.print(A[i][j]);
        j++;
      }

    for( int k=1,k<N,k++){
        System.out.print(A[i][j]);
        i++;
      }
  
    for( int k=1,k<N,k++){
        System.out.print(A[i][j]);
        j--;
      }

    for( int k=1,k<N,k++){
        System.out.print(A[i][j]);
        i--;
      }

    //Move to the inner spiral
     i++;
     j++;
     N=N-2; 
  }
  // printing the middle element where N is Odd.
  if(N==1){
    System.out.print(A[i][j]);
  }
} 

We will explore more complex problems in part 2.

Data Structures and Algorithms(DSA) Concept- 2D Matrix -Part 2

Hope this was helpful , Please do like and follow.