Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is a matrix in coding?
4.2.
Is learning coding hard?
4.3.
What is time complexity and its types?
5.
Conclusion
Last Updated: Mar 27, 2024

Find Sum of all Elements in a Matrix except the Elements in Row and/or Column of Given Cell

Author Harsh
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

If you want to be good in competitive programming or in DSA. Then you need to have knowledge of various programming questions. In this blog, we will discuss a programming question related to the matrix or 2d array where we have to find the sum of all the elements in the matrix except some elements which will be given by the user and then print the result.

Also Read, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

We have a two-dimensional matrix and a set of cell indexes. Cell indices are written as (i, j), where i is row and j is column. For any given cell index (i, j), we must calculate the sums of all matrix elements that do not appear in the ith row or jth column.

Sample Examples

Example 1

Input

Output

Explanation

Excluding the 0th row and 0th column, we get 16 as our answer. The same goes for other cell indices.

Example 2

Input

Output

Explanation

Excluding the 0th row and 0th column, we get 26 as our answer. The same goes for other cell indices.

Brute Force Approach

Consider all cell indexes. Find the sum of matrix elements that are not present in either the i'th row or the j'th column for each cell index (i, j).

Algorithm

  1. Start Traversing the matrix.
     
  2. If the ith row and jth column is available in our Cell indexes. Then skip that iteration.
     
  3. Else add the summation to a variable.
     
  4. Print the sum.
     
  5. Exit
     

Implementation in C++

#include<bits/stdc++.h>
using namespace std;


void findSum(vector<vector<int>> mat, pair<int, int> *cell, int n) {
    // row size
    int ROW = mat.size();


    //column size;
    int COL = mat[0].size();


// Iterating through whole matrix
for (int i=0; i<n; i++)
{
        // saving result and getting the ith row and jth column
int result = 0, r = cell[i].first, c = cell[i].second;


// Computing the sum for current cell index
for (int j=0; j<ROW; j++)
for (int k=0; k<COL; k++)
if (j != r && k != c)
result += mat[j][k];


        // printing the result
cout << result << endl;
}
}


// Driver program to test above
int main()
{
    // getting row size from user
    cout << "Enter Row Size: ";
    int rowSize;
    cin >> rowSize;


    // getting column size from user
    cout << "Enter Column Size: ";
    int colSize;
    cin >> colSize;


    // main matrix
    vector<vector<int>> mat(rowSize, vector<int>(colSize));


    // getting matrix element from user
    for(int i = 0; i < rowSize; i++){
        for(int j = 0; j < colSize; j++){
            cin >> mat[i][j];
        }
    }



    // Size of our cell array
int n = 3;


    // cell indexes that needs to be skipped
    pair<int, int> cell[] = {{0, 0}, {1, 1}, {0, 1}};


    // Calling our method
findSum(mat, cell, n);


return 0;
}

 

Input

Enter Row Size: 3
Enter Column Size: 3
1 2 3
4 5 6
9 8 7

 

Output

26
20
26

Time Complexity

The Time Complexity of the above program is O(n * rowSize * colSize), where n represent the size of our cell indexes that needs to be skipped and rowSize, colSize represents the size of our matrix.

Space Complexity

No extra space is used so the space complexity will be O(1).

Read More - Time Complexity of Sorting Algorithms

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

The problem with the above approach is that some computations are repeating, for example, Imagine there are some cell indices repeating in our array. So to compute the result we have to do some computations again and again which will increase the time complexity of our program. So in order to tackle this problem and to reduce the time complexity We can precompute sum of every row, sum every column in our matrix. Before processing the given array of indexes.

Algorithm

  1. Declare two arrays to store the pre-computed values. One array will be used to store the sum of every row and the other one will be used to store the sum of every column.
     
  2. Start traversing the input matrix, calculate and store the sum of every row and every column inside the above declared arrays.
     
  3. Process each of the cell indices and subtract the row and column from the final result.
     
  4. Print the result.
     

Implementation in C++

#include<bits/stdc++.h>
using namespace std;


void findSum(vector<vector<int>> mat, pair<int, int> *cell, int n) {   
    // row size
    int ROW = mat.size();


    // column size
    int COL = mat[0].size();


    // storing result
    int result = 0;


    // To store the pre computed values
    vector<int> row(ROW);
    vector<int> col(COL);
 
    // Pre-Computing sum of every row and every column
    for (int i=0; i<ROW; i++) {
      for (int j=0; j<COL; j++) {
             result += mat[i][j];
             col[j] += mat[i][j];
             row[i] += mat[i][j];
       }
    }
 
    // Computing and printing the desired sum
    for (int i=0; i<n; i++) {
        int ro = cell[i].first, co = cell[i].second;
        cout << result - row[ro] - col[co] + mat[ro][co] << endl;
    }
}


// Driver program to test above
int main()
{


    // getting row size from user
    cout << "Enter Row Size: ";
    int rowSize;
    cin >> rowSize;


    // getting column size from user
    cout << "Enter Column Size: ";
    int colSize;
    cin >> colSize;


    // main matrix
    vector<vector<int>> mat(rowSize, vector<int>(colSize));


    // getting matrix element from user
    for(int i = 0; i < rowSize; i++){
        for(int j = 0; j < colSize; j++){
            cin >> mat[i][j];
        }
    }


    // Size of our cell array
int n = 3;


    // cell indexes that needs to be skipped
    pair<int, int> cell[] = {{0, 0}, {1, 1}, {0, 1}};


    // Calling our method
findSum(mat, cell, n);


return 0;
}

 

Input

Enter Row Size: 3
Enter Column Size: 3
1 2 3
4 5 6
9 8 7

 

Output

26
20
26

Time Complexity

The Time Complexity of the above program is O(rowSize x colSize + n), where rowSize and colSize represent the size of our matrix and n represents the size of our cell index which needs to be skipped.

Space Complexity

We are using new arrays to store the precomputed sum and the size of this new array depends upon the size of row and column of our input matrix. So, the space complexity is O(rowSize + colSize) where rowSize and colSize represent the size of our input matrix.

Frequently Asked Questions

What is a matrix in coding?

A matrix is made up of two dimensions of numbers: rows and columns. It's similar to a data table made up entirely of numbers.
 

Is learning coding hard?

No, coding is not difficult to learn. However, like with everything new, it's not easy to get started, and how difficult it is to learn to code depends on a variety of things. You can also refer to our website if you want to get started.
 

What is time complexity and its types?

Time complexity is a computer science term that deals with quantifying the amount of time it takes a piece of code or algorithm to process or run as a function of the amount of input.

Conclusion

In this article, we have extensively discussed a coding problem related to the matrix. We hope that this blog has helped you enhance your knowledge about the above question and if you would like to learn more. Checkout more of our blogs & problems related to coding Sum Of Two ArraysFirst non-repeating character in a streamHow to efficiently implement k Queues in a single arraySorting of Queue, and many more on our Website.

You can also check Interview Experiences and Interview Preparation Resources if you are interested in cracking the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc.

Upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and more with our Coding Ninjas Studio Guided Path.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass