Minimum Operations required to make each Column and Row of the Matrix Equals

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²).

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 in-depth about Multi-dimensional 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:

1. Shortest Path In Binary Matrix
2. Set Matrix Zero.
3. Rotate Matrix
4. Maximum Path Sum in the Matrix 
5. Matrix Median
6. 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!!