Given a N*N matrix of positive integers. The task is to find the maximum difference between any pair of elements in any column of the matrix.
Examples:
Input : mat[N][N] = {
{ 1, 2, 3, 4, 5 },
{ 5, 3, 5, 4, 0 },
{ 5, 6, 7, 8, 9 },
{ 0, 6, 3, 4, 12 },
{ 9, 7, 12, 4, 3 },
};
Output : Max difference : 12
5th column has the pair with max difference
(0, 12)
Input : mat[N][N] = {
{ 1, 2, 3 },
{ 5, 3, 5 },
{ 9, 6, 7 }
};
Output : Max difference : 8
The idea is to observe that the pair with a maximum difference in any column is the difference between the maximum and minimum element of that column. Now traverse the matrix column-wise. Find the difference between the max and min elements of every column and return the maximum difference.
Below is the implementation of the above approach:
C++
// C++ program to find column with// max difference of any pair of elements#include <bits/stdc++.h>using namespace std;#define N 5 // No of rows and column// Function to find the column with max differenceint colMaxDiff(int mat[N][N]){ int max_diff = INT_MIN; // Traverse matrix column wise for (int i = 0; i < N; i++) { // Insert elements of column to vector int max_val = mat[0][i], min_val = mat[0][i]; for (int j = 1; j < N; j++) { max_val = max(max_val, mat[j][i]); min_val = min(min_val, mat[j][i]); } // calculating difference between maximum and // minimum max_diff = max(max_diff, max_val - min_val); } return max_diff;}// driver codeint main(){ int mat[N][N] = { { 1, 2, 3, 4, 5 }, { 5, 3, 5, 4, 0 }, { 5, 6, 7, 8, 9 }, { 0, 6, 3, 4, 12 }, { 9, 7, 12, 4, 3 }, }; cout << "Max difference : " << colMaxDiff(mat) << endl; return 0;} |
Java
// Java program to find column with // max difference of any pair of elements public class GOC1 { static int N = 5; // No of rows and column // Function to find the column with max difference static int colMaxDiff(int mat[][]) { int max_diff = Integer.MIN_VALUE; // Traverse matrix column wise for (int i = 0; i < N; i++) { // Insert elements of column to vector int max_val = mat[0][i], min_val = mat[0][i]; for (int j = 1; j < N; j++) { max_val = Math.max(max_val, mat[j][i]); min_val = Math.min(min_val, mat[j][i]); } // calculating difference between maximum and // minimum max_diff = Math.max(max_diff, max_val - min_val); } return max_diff; } // Driver Code public static void main(String args[]) { int mat[][] = { { 1, 2, 3, 4, 5 }, { 5, 3, 5, 4, 0 }, { 5, 6, 7, 8, 9 }, { 0, 6, 3, 4, 12 }, { 9, 7, 12, 4, 3 }, }; System.out.println("Max difference : "+colMaxDiff(mat)); }} |
Python3
# Python3 program to find column with# max difference of any pair of elementsN = 5 # No of rows and column# Function to find the column # with max differencedef colMaxDiff(mat): max_diff = 0 # Traverse matrix column wise for i in range (N): # Insert elements of column # to vector max_val = mat[0][i] min_val = mat[0][i] for j in range (1, N) : max_val = max(max_val, mat[j][i]) min_val = min(min_val, mat[j][i]) # calculating difference between # maximum and minimum max_diff = max(max_diff, max_val - min_val) return max_diff# Driver Codeif __name__ == "__main__": mat = [[ 1, 2, 3, 4, 5 ], [5, 3, 5, 4, 0 ], [ 5, 6, 7, 8, 9 ], [ 0, 6, 3, 4, 12 ], [ 9, 7, 12, 4, 3 ]] print ("Max difference :", colMaxDiff(mat))# This code is contributed by ita_c |
C#
// C# program to find column // with max difference of // any pair of elements using System;class GFG {static int N = 5; // No of rows and column // Function to find the column// with max differencestatic int colMaxDiff(int [,]mat) { int max_diff = int.MinValue; // Traverse matrix column wise for (int i = 0; i < N; i++) { // Insert elements of column // to vector int max_val = mat[0, i], min_val = mat[0, i]; for (int j = 1; j < N; j++) { max_val = Math.Max(max_val, mat[j, i]); min_val = Math.Min(min_val, mat[j, i]); } // calculating difference between // maximum and minimum max_diff = Math.Max(max_diff, max_val - min_val); } return max_diff;}// Driver Codepublic static void Main() { int [,]mat = { { 1, 2, 3, 4, 5 }, { 5, 3, 5, 4, 0 }, { 5, 6, 7, 8, 9 }, { 0, 6, 3, 4, 12 }, { 9, 7, 12, 4, 3 }}; Console.WriteLine("Max difference : " + colMaxDiff(mat));}}// This code is contributed// by Subhadeep |
PHP
<?php// PHP program to find column with// max difference of any pair of elements// Function to find the column with max differencefunction colMaxDiff($mat){ $N = 5; $max_diff = PHP_INT_MIN; // Traverse matrix column wise for ($i = 0; $i < $N; $i++) { // Insert elements of column to vector $max_val = $mat[0][$i]; $min_val = $mat[0][$i]; for ($j = 1; $j < $N; $j++) { $max_val = max($max_val, $mat[$j][$i]); $min_val = min($min_val, $mat[$j][$i]); } // calculating difference between maximum and // minimum $max_diff = max($max_diff, $max_val - $min_val); } return $max_diff;}// driver code$mat = array(array( 1, 2, 3, 4, 5 ), array(5, 3, 5, 4, 0 ), array(5, 6, 7, 8, 9 ), array(0, 6, 3, 4, 12 ), array(9, 7, 12, 4, 3 ));echo "Max difference : " . colMaxDiff($mat) . "\n";// This code is contributed// by Akanksha Rai |
Javascript
<script>// Javascript program to find column with // max difference of any pair of elements let N = 5; // No of rows and column // Function to find the column with max difference function colMaxDiff(mat) { let max_diff = Number.MIN_VALUE; // Traverse matrix column wise for (let i = 0; i < N; i++) { // Insert elements of column to vector let max_val = mat[0][i], min_val = mat[0][i]; for (let j = 1; j < N; j++) { max_val = Math.max(max_val, mat[j][i]); min_val = Math.min(min_val, mat[j][i]); } // calculating difference between maximum and // minimum max_diff = Math.max(max_diff, max_val - min_val); } return max_diff; } // Driver Code let mat = [[ 1, 2, 3, 4, 5 ], [5, 3, 5, 4, 0 ], [ 5, 6, 7, 8, 9 ], [ 0, 6, 3, 4, 12 ], [ 9, 7, 12, 4, 3 ]]; document.write("Max difference :"+ colMaxDiff(mat))// This code is contributed by rag2127</script> |
Output
Max difference : 12
Time Complexity: O(n^2)
Auxiliary Space: O(1)
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!
