Given a square matrix M[][] of size N x N, the task is to find the maximums & minimums of each of the rows and columns, multiply the corresponding maximums & minimums of each row with those of each column, Finally return the absolute difference of both of these.
Examples:
Input: M[][] = [ [ 3, 2, 5 ], [ 7, 5, 4 ], [ 7, 2, 9 ] ]
Output: 11
Explanation:
Input: M = [ [1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
Output: 40
Naive Approach: The task can be solved by simulating the given operations. Follow the below steps to solve the problem:
- Take 2 arrays max1[ ] and min1[ ] for storing the maximum and minimum of each row or each column.
- First store the maximum of each row in max1[ ] and a minimum of each row in min1[ ].
- Multiple both matrix and return res, store it in R.
- Take transpose of matrix M[ ].
- Then store the maximum of each column in max1[ ] and the minimum of each column in min1[ ].
- Multiply both matrices and return res, store it in C.
- Print absolute difference of R and C.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to find the transpose matrix M[]vector<vector<int>> transpose(vector<vector<int>>M, int N){ for(int i = 0; i < N; i++) { for(int j = 0; j < i + 1; j++) { int temp = M[i][j]; M[i][j] = M[j][i]; M[j][i] = temp; } } return M;}// Function to convert matrix M[][] to size 1 * 1int matOne(vector<vector<int>>M, int N){ // Max1 and min1 to store max and min // of each row pr column vector<int>max1; vector<int>min1; // Loop to store element in max1 and min1 for(int r = 0; r < N; r++) { max1.push_back(*max_element(M[r].begin(), M[r].end())); min1.push_back(*min_element(M[r].begin(), M[r].end())); } // Initialise res to 0 int res = 0; // Multiply and add both array for(int i = 0; i < N; i++){ res += max1[i]*min1[i]; } // Return res return res;}// Driver codeint main(){ // Original matrix vector<vector<int>>M = {{3, 2, 5},{7, 5, 4},{7, 2, 9}}; // N size of matrix int N = M.size(); // Call matOne function for rows int R = matOne(M, N); // Transpose the matrix vector<vector<int>>T = transpose(M, N); // Call matOne function for column int C = matOne(T, N); // Print the absolute difference cout << abs(R - C) << endl;}// This code is contributed by shinjanpatra |
Java
// Java program for the above approachimport java.io.*; import java.util.*; class GFG{ // Function to find the transpose matrix M[] static int[][] transpose(int[][] M, int N) { int transpose[][] = new int[N][N]; // Code to transpose a matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { transpose[i][j] = M[j][i]; } } return transpose; } // Function to convert matrix M[][] to size 1 * 1 static int matOne(int[][] M, int N) { // Max1 and min1 to store max and min // of each row pr column ArrayList<Integer> max1 = new ArrayList<Integer>(); ArrayList<Integer> min1 = new ArrayList<Integer>(); // Loop to calculate res. for (int[] r : M) { max1.add(Arrays.stream(r).max().getAsInt()); min1.add(Arrays.stream(r).min().getAsInt()); } // Initialise res to 0 int res = 0; // Multiply and add both array for(int i = 0; i < N; i++) { res += max1.get(i)*min1.get(i); } // Return res return res; } // Driver code public static void main(String[] args) { // Original matrix int[][] M = { { 3, 2, 5 }, { 7, 5, 4 }, { 7, 2, 9 } }; // N size of matrix int N = M.length; // Call matOne function for rows int R = matOne(M, N); // Transpose the matrix int[][] T = transpose(M, N); // Call matOne function for column int C = matOne(T, N); // Print the absolute difference System.out.println((Math.abs(R - C))); }} // This code is contributed by aditya patil |
Python3
# Python program for the above approach# Function to find the transpose matrix M[]def transpose(M, N): for i in range(N): for j in range(i + 1): M[i][j], M[j][i] = M[j][i], M[i][j] return M# Function to convert matrix M[][] to size 1 * 1def matOne(M, N): # Max1 and min1 to store max and min # of each row pr column max1 = [] min1 = [] # Loop to store element in max1 and min1 for r in M: max1.append(max(r)) min1.append(min(r)) # Initialise res to 0 res = 0 # Multiply and add both array for i in range(N): res += max1[i]*min1[i] # Return res return res# Driver codeif __name__ == "__main__": # Original matrix M = [[3, 2, 5], [7, 5, 4], [7, 2, 9]] # N size of matrix N = len(M) # Call matOne function for rows R = matOne(M, N) # Transpose the matrix T = transpose(M, N) # Call matOne function for column C = matOne(T, N) # Print the absolute difference print(str(abs(R-C))) |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;using System.Linq;public class GFG { // Function to find the transpose matrix []M static int[, ] transpose(int[, ] M, int N) { int[, ] transpose = new int[N, N]; // Code to transpose a matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { transpose[i, j] = M[j, i]; } } return transpose; } // Function to convert matrix M[][] to size 1 * 1 static int matOne(int[, ] M, int N) { // Max1 and min1 to store max and min // of each row pr column ArrayList max1 = new ArrayList(); ArrayList min1 = new ArrayList(); // Loop to calculate res. for (int r = 0; r < N; r++) { int[] t = new int[N]; for (int j = 0; j < N; j++) { t[j] = M[r, j]; } min1.Add(t.Min()); max1.Add(t.Max()); } // Initialise res to 0 int res = 0; // Multiply and add both array for (int i = 0; i < N; i++) { res += (int)max1[i] * (int)min1[i]; } // Return res return res; } static public void Main() { // Code // Original matrix int[, ] M = { { 3, 2, 5 }, { 7, 5, 4 }, { 7, 2, 9 } }; // N size of matrix int N = M.GetLength(0); // Call matOne function for rows int R = matOne(M, N); // Transpose the matrix int[, ] T = transpose(M, N); // Call matOne function for column int C = matOne(T, N); // Print the absolute difference Console.WriteLine((Math.Abs(R - C))); }}// This code is contributed by lokeshmvs21. |
Javascript
<script>// Javascript program for the above approach// Function to find the transpose matrix M[]function transpose(M) { return M[0].map((col, i) => M.map(row => row[i]));}// Function to convert matrix M[][] to size 1 * 1function matOne(M, N) { // Max1 and min1 to store max and min // of each row pr column let max1 = [] let min1 = [] // Loop to store element in max1 and min1 for (r of M){ max1.push([...r].sort((a, b) => b - a)[0]) min1.push([...r].sort((a, b) => a - b)[0]) } // Initialise res to 0 let res = 0 // Multiply and add both array for (let i = 0; i < N; i++) res += max1[i] * min1[i] // Return res return res}// Driver code// Original matrixlet M = [[3, 2, 5], [7, 5, 4], [7, 2, 9]];// N size of matrixlet N = M.length;// Call matOne function for rowslet R = matOne(M, N)// Transpose the matrixlet T = transpose(M)// Call matOne function for columnlet C = matOne(T, N)// Print the absolute differencedocument.write(Math.abs(R - C))// This code is contributed by saurabh_jaiswal.</script> |
Output
11
Time Complexity: O(N2)
Auxiliary Space: O(N)
Space Optimized Approach: This approach is similar to approach 1, but in this, the auxiliary space will be optimized by not using max1 and min1 arrays. In this, direct multiple and add the element and return it.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to find the transpose matrix M[]vector<vector<int>> transpose(vector<vector<int>>M, int N){for(int i = 0; i < N; i++){ for(int j = 0; j < i + 1; j++) { int temp = M[i][j]; M[i][j] = M[j][i]; M[j][i] = temp; }}return M;}// Function to convert matrix M[][] to size 1 * 1int matOne(vector<vector<int>>M, int N){// Max1 and min1 to store max and min// of each row pr column vector<int>arr; int res = 0; for (int r =0;r< N;r++){ arr.clear(); for(int j =0;j<N;j++){ arr.push_back(M[r][j]); } sort(arr.begin(),arr.end()); res += arr[arr.size()-1] * arr[0]; } // Return res return res;}// Driver codeint main(){// Original matrixvector<vector<int>>M = {{3, 2, 5},{7, 5, 4},{7, 2, 9}};// N size of matrixint N = M.size();// Call matOne function for rowsint R = matOne(M, N);// Transpose the matrixvector<vector<int>>T = transpose(M, N);// Call matOne function for columnint C = matOne(T, N);// Print the absolute differencecout << abs(R - C) << endl;}// This code is contributed by akshitsaxenaa09. |
Java
import java.util.Arrays;// Java program for the above approachclass GFG { // Function to find the transpose matrix M[] static int[][] transpose(int[][] M, int N) { int transpose[][] = new int[N][N]; // Code to transpose a matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { transpose[i][j] = M[j][i]; } } return transpose; } // Function to convert matrix M[][] to size 1 * 1 static int matOne(int[][] M, int N) { // Loop to calculate res. int res = 0; for (int[] r : M) res += Arrays.stream(r).max().getAsInt() * Arrays.stream(r).min().getAsInt(); // Return res return res; } // Driver code public static void main(String[] args) { // Original matrix int[][] M = { { 3, 2, 5 }, { 7, 5, 4 }, { 7, 2, 9 } }; // N size of matrix int N = M.length; // Call matOne function for rows int R = matOne(M, N); // Transpose the matrix int[][] T = transpose(M, N); // Call matOne function for column int C = matOne(T, N); // Print the absolute difference System.out.println((Math.abs(R - C))); }}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to find the transpose matrix M[]def transpose(M, N): for i in range(N): for j in range(i + 1): M[i][j], M[j][i] = M[j][i], M[i][j] return M# Function to convert matrix M[][] to size 1 * 1def matOne(M, N): # Loop to calculate res. res = 0 for r in M: res += max(r)*min(r) # Return res return res# Driver codeif __name__ == "__main__": # Original matrix M = [[3, 2, 5], [7, 5, 4], [7, 2, 9]] # N size of matrix N = len(M) # Call matOne function for rows R = matOne(M, N) # Transpose the matrix T = transpose(M, N) # Call matOne function for column C = matOne(T, N) # Print the absolute difference print(str(abs(R-C))) |
C#
// C# program for the above approachusing System;using System.Linq;public class GFG { // Function to find the transpose matrix []M static int[,] transpose(int[,] M, int N) { int [,]transpose = new int[N,N]; // Code to transpose a matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { transpose[i,j] = M[j,i]; } } return transpose; } // Function to convert matrix [,]M to size 1 * 1 static int matOne(int[,] M, int N) { // Loop to calculate res. int res = 0; for (int r =0;r< N;r++){ int[] t = new int[N]; for(int j =0;j<N;j++){ t[j] = M[r,j]; } res += t.Max() * t.Min(); } // Return res return res; } // Driver code public static void Main(String[] args) { // Original matrix int[,] M = { { 3, 2, 5 }, { 7, 5, 4 }, { 7, 2, 9 } }; // N size of matrix int N = M.GetLength(0); // Call matOne function for rows int R = matOne(M, N); // Transpose the matrix int[,] T = transpose(M, N); // Call matOne function for column int C = matOne(T, N); // Print the absolute difference Console.WriteLine((Math.Abs(R - C))); }}// This code is contributed by umadevi9616 |
Javascript
<script> // JavaScript code for the above approach // Function to find the transpose matrix M[] function transpose(M, N) { // This function stores transpose // of A in B let B = Array(M).fill(0); for (let i = 0; i < N; i++) { B[i] = new Array(N); } var i, j; for (i = 0; i < N; i++) for (j = 0; j < N; j++) B[i][j] = M[j][i]; return B } // Function to convert matrix M[][] to size 1 * 1 function matOne(M, N) { // Max1 and min1 to store max and min // of each row pr column max1 = [] min1 = [] // Loop to store element in max1 and min1 for (let i = 0; i < M.length; i++) { r = M[i] max1.push(Math.max(...r)) min1.push(Math.min(...r)) } // Initialise res to 0 res = 0 // Multiply and add both array for (let i = 0; i < N; i++) res += (max1[i] * min1[i]) // Return res return res } // Driver code // Original matrix let M = [[3, 2, 5], [7, 5, 4], [7, 2, 9]] // N size of matrix let N = M.length // Call matOne function for rows let R = matOne(M, N) // Transpose the matrix T = transpose(M, N) // Call matOne function for column C = matOne(T, N) // Print the absolute difference document.write(Math.abs(R - C)) // This code is contributed by Potta Lokesh </script> |
Output:
11
Time Complexity: O(N2log(N))
Auxiliary Space: O(N) because using extra space for array
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!
