Sample Examples
Example 1:
Input
2 5
4 3
Output
2
3 5
5 3
Explanation
1. Add 1 to the value of cell (0, 0).
2. Add 1 to the value of cell(1, 0)
As a result, a total of 2 operations are necessary.
Example 2:
Input
2 3
4 5
Output
4
5 4
4 5
Explanation
1. Add 3 to the value of cell (0, 0).
2. Add 1 to the value of cell(0, 1)
As a result, a total of 4 operations are necessary.
Example 3:
Input
1 2 3
4 2 3
3 2 1
Output
6
2 4 3
4 2 3
3 3 3
Explanation
1. Add 1 to the value of cell (0, 0).
2. Add 2 to the value of cell(0, 1).
3. Add 1 to the value of cell(2, 1).
4. Add 2 to the value of cell(2, 2).
As a result, a total of 6 operations are necessary.
Approach
Let's start with a basic approach: maxSum is the largest sum of all rows and columns. We only need to increase the value of a few cells so that the sum of any row or column equals 'maxSum.'
Let's take Xi as the total number of operations required to equalise the sum on row I and Yj as the total number of operations required to equalise the sum on column 'j'. Because Xi = Yj, we can work on any of them depending on the situation.
To minimise Xi, we must choose the largest from rowSumi and colSumj, as this will almost certainly result in the smallest operation. Then, depending on the condition satisfied after increment, increment I or 'j'.
The implementation of all of these approaches is shown below.
Algorithm
 Because we may only add or subtract K from any element, we can readily deduce that all elements with K should have the same mod. If it isn't, return 1.
 Find the median of the sorted elements by sorting all of the matrix's members in ascending order.
 The shortest number of steps would be achieved if all of the items were converted to the median value.
Implementation
Here is the implementation of the algorithm in C++ and Java.
Code(C++)
#include <bits/stdc++.h>
#define ll long long
#define vll vector<long long int>
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define endl "\n"
#define vpi vector<pair<ll,ll>>
#define fi first
#define se second
#define pqi priority_queue<ll,vll,greater<ll>>
#define all(x) x.begin(),x.end()
#define py cout << "YES\n"
#define pn cout << "NO\n"
using namespace std;
// To get the smallest operation required to
// make a sum of each row and column equal, use this function.
int MinOperations(ll mat[][2], ll n)
{
// Initialize the sumR[] and sumC[] array to 0
ll sumR[n], sumC[n];
memset(sumR, 0, sizeof(sumR));
memset(sumC, 0, sizeof(sumC));
// Calculate sumR[] and sumC[] array
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
sumR[i] += mat[i][j];
sumC[j] += mat[i][j];
}
// Find maximum sum value in either row or in column
ll maxSum = 0;
for (int i = 0; i < n; ++i) {
maxSum = max(maxSum, sumR[i]);
maxSum = max(maxSum, sumC[i]);
}
ll cnt = 0;
for (int i = 0, j = 0; i < n && j < n;) {
// In either a row or a column,
// find the smallest increase required.
ll diff = min(maxSum  sumR[i], maxSum  sumC[j]);
// Add difference in corresponding cell, sumR[]
// and sumC[] array
mat[i][j] += diff;
sumR[i] += diff;
sumC[j] += diff;
// Update the cnt variable
cnt += diff;
// If the ith row is satisfied,
// the ith value is incremented for the next iteration.
if (sumR[i] == maxSum)
++i;
// If the jth column is satisfied,
// the jth value is incremented for the next iteration.
if (sumC[j] == maxSum)
++j;
}
return cnt;
}
// Function to print matrix
void printmat(ll mat[][2], ll n)
{
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cout << mat[i][j] << " ";
cout << endl;
}
}
// main code
int main()
{
ll mat[][2] = { { 2 , 3}, { 4, 5} };
cout << MinOperations(mat, 2) << endl;
printmat(mat, 2);
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
Output
Code(Java)
import java.io.*;
class Coding_Ninjas {
// find minimum operation required
static int MinOpeartion(int matrix[][], int n)
{
// Initialize the sum of row(sumR[]) and sum of column(SumC[]) array to 0
int[] sumR = new int[n];
int[] sumC = new int[n];
// Calculate sumR[] and sumC[] array
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
sumR[i] += matrix[i][j];
sumC[j] += matrix[i][j];
}
// Find maximum sum value
int maxSum = 0;
for (int i = 0; i < n; ++i) {
maxSum = Math.max(maxSum, sumR[i]);
maxSum = Math.max(maxSum, sumC[i]);
}
int count = 0;
for (int i = 0, j = 0; i < n && j < n;) {
// Finding the minimum increment required in either row
// or column
int diff = Math.min(maxSum  sumR[i], maxSum  sumC[j]);
matrix[i][j] += diff;
sumR[i] += diff;
sumC[j] += diff;
// the count variable
count += diff;
// If the ith row satisfied, increment the ith value for next iteration
if (sumR[i] == maxSum)
++i;
// If the jth column satisfied, increment the jth value for next iteration
if (sumC[j] == maxSum)
++j;
}
return count;
}
// function to print matrix
static void printtheMatrix(int matrix[][], int n)
{
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
System.out.print(matrix[i][j] + " ");
System.out.println();
}
}
//Driver Code
public static void main(String[] args)
{
int matrix[][] = { { 1, 2 }, { 3, 4 } };
System.out.println(MinOpeartion(matrix, 2));
printtheMatrix(matrix, 2);
}
}
You can also try this code with Online Java Compiler
Run Code
Output
Time Complexity
As the solution takes a double path from the bottom to the top corner and the left corner to the right corner of the matrix, the time complexity is O(n^{2}).
Space Complexity
The program's auxiliary space is O(n) because one data structure(Priority Queue) is involved to store the values. So, the space complexity is O(n).
Frequently Asked Questions
What is the time complexity for traversing a matrix?
It takes O (N * M) time to traverse a 2D array, where N is the number of rows and M is the number of columns.
What comes first in a matrix, rows or columns?
Rows are always listed first, followed by columns. As a result, we may state that the above matrix's dimension (or order) is 3 x 4, implying that it has 3 rows and 4 columns. The numbers that appear in the rows and columns of a matrix are referred to as matrix elements.
What command do you use to find the maximum and minimum numbers in a column row or matrix?
We utilised the max() function to discover the most significant element in an object. This object could be a Vector, a list, a matrix, a data frame, or something else. The "which()" method returns the index or position of the value that meets the specified criteria.
Conclusion
In this blog, we have extensively discussed the Problem of Minimum operations required to make each row and column of the matrix equals and its time and space complexities. We hope that this article has provided you with additional information about the Data Structures and algorithms. And to learn indepth about Multidimensional Arrays, check out the course on our Arrays on the Coding Ninjas website.
You can also visit our curated sections of Data Structure, Arrays, Graph, Trie, Dynamic programming, and many more.
Here are some of the widespread Matrix problems for your coding practice:
 Shortest Path In Binary Matrix
 Set Matrix Zero.
 Rotate Matrix
 Maximum Path Sum in the Matrix
 Matrix Median

Matrix chain Multiplication and many more at Coding Ninjas Studio.
Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations, and much more!!
We wish you Good Luck! Keep coding and keep reading Ninja!!