Maximum difference of indices (i, j) such that A[i][j] = 0 in the given matrix

0 0 4 minutes read

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 4
using namespace std;
 
// function to return maximum |i-j| such that Aij = 0
int 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 program
int 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 = 0
import java.math.*;
class GFG {
     
static int n = 4;
 
// function to return maximum |i-j| such that Aij = 0
static 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 program
public 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 = 0
def 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 code
if __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 = 0
using System;
 
class GFG 
{
static int n = 4;
 
// function to return maximum |i-j|
// such that Aij = 0
static 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 code
static 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 = 0
function 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 = 0
var n = 4
 
// function to return maximum |i-j| such that Aij = 0
function 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 program
var matrix = [ [ 2, 3, 0, 1 ],
                     [ 0, 2, 0, 1 ],
                     [ 0, 1, 1, 3 ],
                     [ 1, 2, 3, 3 ] ];
document.write( calculateDiff(matrix));
 
</script>

Output

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 zambiatek!