Given a matrix of order n*n, the task is to find the maximum value of |i-j| such that Aij = 0. Given matrix must contain at least one 0.
Examples:
Input: matrix[][] =
{{2, 3, 0},
{0, 2, 0},
{0, 1, 1}}
Output: 2
mat(0, 2) has a value 0 and difference of index is maximum i.e. 2.
Input: matrix[][] =
{{2, 3, 4},
{0, 2, 0},
{6, 1, 1}}
Output: 1
Approach:
For finding the maximum value of |i-j| such that Aij = 0, traverse the whole matrix and for each occurrence of zero calculate the mod of (i-j) and store it corresponding to same position in an auxiliary matrix. At last, find the maximum value from the auxiliary matrix.
Apart from using an auxiliary matrix, the maximum value of |i-j| can be stored in a variable and can be updated while its calculation. this will save the extra use of space.
Below is the implementation of the above approach:
C++
// CPP for maximum |i-j| such that Aij = 0#include <bits/stdc++.h>#define n 4using namespace std;// function to return maximum |i-j| such that Aij = 0int calculateDiff(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 - j)); } } // return result return result;}// driver programint main(){ int matrix[n][n] = { { 2, 3, 0, 1 }, { 0, 2, 0, 1 }, { 0, 1, 1, 3 }, { 1, 2, 3, 3 } }; cout << calculateDiff(matrix); return 0;} |
Java
// Java program for maximum |i-j| such that Aij = 0import java.math.*;class GFG { static int n = 4;// function to return maximum |i-j| such that Aij = 0static int calculateDiff(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 - j)); } } // return result return result;}// driver programpublic static void main(String args[]){ int matrix[][] = new int[][] {{ 2, 3, 0, 1 }, { 0, 2, 0, 1 }, { 0, 1, 1, 3 }, { 1, 2, 3, 3 } }; System.out.println(calculateDiff(matrix));}} |
Python3
# Python3 program for maximum # |i-j| such that Aij = 0# function to return maximum # |i-j| such that Aij = 0def calculateDiff(matrix, n): 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 - j)) return result # Driver codeif __name__=='__main__': matrix = [[2, 3, 0, 1], [0, 2, 0, 1], [0, 1, 1, 3], [1, 2, 3, 3]] n = len(matrix) print(calculateDiff(matrix, n)) # This code is contributed by# Kirti_Mangal |
C#
// C# for maximum |i-j| such that Aij = 0using System;class GFG {static int n = 4;// function to return maximum |i-j|// such that Aij = 0static int calculateDiff(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 - j)); } } // return result return result;}// Driver codestatic void Main(){ int [,]matrix = new int[,] { { 2, 3, 0, 1 }, { 0, 2, 0, 1 }, { 0, 1, 1, 3 }, { 1, 2, 3, 3 } }; Console.WriteLine(calculateDiff(matrix));;}}// This code is contributed by ANKITRAI1 |
PHP
<?php// PHP for maximum |i-j| such that Aij = 0// function to return maximum |i-j| // such that Aij = 0function calculateDiff($matrix){ $n = 4; $result = 0; // traverse the matrix for ($i = 0; $i < $n; $i++) { for ($j = 0; $j < $n; $j++) { if ($matrix[$i][$j] == 0) $result = max($result, abs($i - $j)); } } // return result return $result;}// Driver Code$matrix = array(array( 2, 3, 0, 1 ), array( 0, 2, 0, 1 ), array( 0, 1, 1, 3 ), array( 1, 2, 3, 3 ));echo calculateDiff($matrix);// This code is contributed// by Akanksha Rai |
Javascript
<script>// Javascript for maximum |i-j| such that Aij = 0var n = 4// function to return maximum |i-j| such that Aij = 0function calculateDiff(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 - j)); } } // return result return result;}// driver programvar matrix = [ [ 2, 3, 0, 1 ], [ 0, 2, 0, 1 ], [ 0, 1, 1, 3 ], [ 1, 2, 3, 3 ] ];document.write( calculateDiff(matrix));</script> |
Output
2
Time complexity: O(n^2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
