2. a) Search in a row wise and column wise sorted matrix

2. a) Search in a row wise and column wise sorted matrix

Problem link :- click here

//geeks for geeks
package progams;

import java.util.Scanner;

public class Matrix__2__a
{

	/*
        10  20  30  40
         15  25  35  45
        27  29  37  48
        32  33  39  50

        There is a easy trick to search an element in matrix which is sorted row-wise and column-wise
        
        Start checking from right top element because 
        if the 'key' < element 
        		you have to go to left to get element less than what you are pointing 
        if key > element 
        		you have to go down
        if equal I don't have to tell about 
        */
        
        
        static void searchMatrixSortedRowAndColumnWise(int mat[][], int r, int c, int key)
        {
                int i, j;
                i = 0;      //row
                j = c-1;   //column
                
                int flag = 0;    //this is to know whether the element is found or not
                
                /*
                condition : we should not go out of the matrix 
                			1) as we are moving downwards we should not go down then the last row
                			2) as we are also moving to left we should not go further left than first column
                */
                while(i<r   &&   j>=0)
                {
                        if(mat[i][j] == key)
                        {
                        	flag = 1;
                        	System.out.println("\n\nElement is found at position ("+ i + ", " + j + ")" );
                        	return;
                        }
                        else if(key < mat[i][j])
                        {
                        	//here we should go to left     that is we should go to previous column
                        	j--;
                        }
                        else if(key > mat[i][j])
                        {
                        	//here we should go down       that is we should go to next row
                        	i++;
                        }
                }
                if(flag == 0)
                	System.out.println("\n\nElement not found");
        }
	
	public static void main(String[] args)
	{
		int i, j, r, c;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the number of rows : ");
		r = s.nextInt();
		System.out.print("Enter the numvber of columns : ");
		c = s.nextInt();
		int matrix[][] = new int[r][c];
		System.out.println("Enter the elements of the matrix : ");
		for(i=0; i<r; i++)
		{
			for(j=0; j<c; j++)
				matrix[i][j] = s.nextInt();
		}
		System.out.print("Enter the target to search : ");
		int target = s.nextInt();
		
		System.out.println("Given matrix :");
		printMatrix(matrix, r, c);
		searchMatrixSortedRowAndColumnWise(matrix, r, c, target);
	}

	static void printMatrix(int mat[][], int r, int c)
	{
		for(int i=0; i<r; i++)
		{
			for(int j=0; j<c; j++)
				System.out.print(mat[i][j] + "  ");
			System.out.println();
		}
	}
}

Time complexity :- O(r+c)
Space complexity :- O(1)