Given a matrix of odd order mat, the task is to find the farthest distance of a 0 from the center of the matrix. Distance between two elements at locations (i1, j1) and (i2, j2) of the matrix is calculated as |i1- i2| + |j1-j2|. If no 0 occurs in the matrix then print 0 as the result.
Examples:
Input: mat[][] = {{2, 3, 0}, {0, 2, 0}, {0, 1, 1}}
Output: 2Input: mat[][] = {{2, 3, 4, {0, 2, 0}, {6, 1, 1}}
Output: 1
Approach:
The center of any matrix with odd order is at index i = j = floor(n/2). Now for finding the farthest distance of any 0 from the center, calculate the distance of each 0 from the center of the matrix as |i-n/2| + |j-n/2| and update the maximum distance as result. Print the result in the end or if the matrix doesn’t contain any 0 then print 0.
Below is the implementation of the above approach:
C++
// C++ program to find the farthest distance // of a 0 from the center of the matrix #include <bits/stdc++.h> #define n 3 using namespace std; // function to return farthest distance // of zero from center of the matrix int farthestDistance( int matrix[][n]) { int result = 0; // traverse the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (matrix[i][j] == 0) result = max(result , abs (i - n/2) + abs (j - n/2)); } } // return result return result; } // driver program int main() { int matrix[n][n] = { { 1, 2, 3 } , { 0, 1, 1 } , { 0, 0, 0 } }; cout << farthestDistance(matrix); return 0; } |
Java
// Java program to find the farthest distance // of a 0 from the center of the matrix import java.io.*; class GFG { static int n = 3 ; // function to return farthest distance // of zero from center of the matrix static int farthestDistance( int matrix[][]) { int result = 0 ; // traverse the matrix for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { if (matrix[i][j] == 0 ) result = Math.max(result , Math.abs(i - n/ 2 ) + Math.abs(j - n/ 2 )); } } // return result return result; } // driver program public static void main (String[] args) { int matrix[][] = { { 1 , 2 , 3 } , { 0 , 1 , 1 } , { 0 , 0 , 0 } }; System.out.print(farthestDistance(matrix)); } } // This code is contributed by anuj_67.. |
Python3
# Python3 program to find the farthest distance # of a 0 from the center of the matrix n = 3 # function to return farthest distance # of zero from center of the matrix def farthestDistance(matrix): result = 0 # traverse the matrix for i in range ( 0 , n): for j in range ( 0 , n): if (matrix[i][j] = = 0 ): result = max (result, abs (i - n / / 2 ) + abs (j - n / / 2 )) # return result return result # Driver Code matrix = [[ 1 , 2 , 3 ], [ 0 , 1 , 1 ], [ 0 , 0 , 0 ]] print (farthestDistance(matrix)) # This code is contributed by # Archana_kumari |
C#
// C# program to find the farthest distance // of a 0 from the center of the matrix using System; class GFG { static int n = 3; // function to return farthest distance // of zero from center of the matrix static int farthestDistance( int [,]matrix) { int result = 0; // traverse the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (matrix[i,j] == 0) result = Math.Max(result , Math.Abs(i - n / 2) + Math.Abs(j - n / 2)); } } // return result return result; } // Driver Code static public void Main () { int [,]matrix = {{ 1, 2, 3 }, { 0, 1, 1 }, { 0, 0, 0 }}; Console.WriteLine(farthestDistance(matrix)); } } // This code is contributed by Sachin |
PHP
<?php // PHP program to find the farthest distance // of a 0 from the center of the matrix $n = 3; // function to return farthest distance // of zero from center of the matrix function farthestDistance( $matrix ) { global $n ; $result = 0; // traverse the matrix for ( $i = 0; $i < $n ; $i ++) { for ( $j = 0; $j < $n ; $j ++) { if (( $matrix [ $i ][ $j ] == 0) > 0) $result = max( $result , abs ( $i - $n / 2) + abs ( $j - $n / 2)); } } // return result return $result ; } // Driver Code $matrix = array ( array ( 1, 2, 3 ), array ( 0, 1, 1 ), array ( 0, 0, 0 )); echo farthestDistance( $matrix ); // This code is contributed by Sach_code ?> |
Javascript
<script> // Javascript program to find the farthest distance // of a 0 from the center of the matrix var n = 3; // function to return farthest distance // of zero from center of the matrix function farthestDistance(matrix) { var result = 0; // traverse the matrix for ( var i = 0; i < n; i++) { for ( var j = 0; j < n; j++) { if (matrix[i][j] == 0) result = Math.max(result , Math.abs(i - n/2) + Math.abs(j - n/2)); } } // return result return result; } // driver program var matrix = [ [ 1, 2, 3 ] , [ 0, 1, 1 ] , [ 0, 0, 0 ] ]; document.write( farthestDistance(matrix)); </script> |
2
Complexity Analysis:
- Time Complexity: O(N*M), as we are using nested loops to traverse N*M times.
- Auxiliary Space: O(1), as we are not using any extra space for matrix.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!