# Find sum of all elements in a matrix except the elements in row and/or column of given cell?

Given a 2D matrix and a set of cell indexes e.g., an array of (i, j) where i indicates row and j column. For every given cell index (i, j), find sums of all matrix elements except the elements present in i’th row and/or j’th column.

Example:

```mat[][]  = { {1, 1, 2}
{3, 4, 6}
{5, 3, 2} }
Array of Cell Indexes: {(0, 0), (1, 1), (0, 1)}
Output:  15, 10, 16
```

We strongly recommend you to minimize your browser and try this yourself first.

A Naive Solution is to one by once consider all given cell indexes. For every cell index (i, j), find the sum of matrix elements that are not present either at i’th row or at j’th column. Below is C++ implementation of the Naive approach.

## C++

 `#include ` `#define R 3 ` `#define C 3 ` `using` `namespace` `std; ` ` `  `// A structure to represent a cell index ` `struct` `Cell ` `{  ` `    ``int` `r; ``// r is row, varies from 0 to R-1 ` `    ``int` `c; ``// c is column, varies from 0 to C-1 ` `}; ` ` `  `// A simple solution to find sums for a given array of cell indexes ` `void` `printSums(``int` `mat[][C], ``struct` `Cell arr[], ``int` `n) ` `{ ` `    ``// Iterate through all cell indexes ` `    ``for` `(``int` `i=0; i

## Python3

 `# Python3 implementation of the approach ` ` `  `# A structure to represent a cell index  ` `class` `Cell:  ` ` `  `    ``def` `__init__(``self``, r, c): ` `        ``self``.r ``=` `r ``# r is row, varies from 0 to R-1 ` `        ``self``.c ``=` `c ``# c is column, varies from 0 to C-1 ` ` `  `# A simple solution to find sums  ` `# for a given array of cell indexes  ` `def` `printSums(mat, arr, n): ` ` `  `    ``# Iterate through all cell indexes  ` `    ``for` `i ``in` `range``(``0``, n):  ` `     `  `        ``Sum` `=` `0``; r ``=` `arr[i].r; c ``=` `arr[i].c  ` ` `  `        ``# Compute sum for current cell index  ` `        ``for` `j ``in` `range``(``0``, R):  ` `            ``for` `k ``in` `range``(``0``, C):  ` `                ``if` `j !``=` `r ``and` `k !``=` `c:  ` `                    ``Sum` `+``=` `mat[j][k]  ` `        ``print``(``Sum``)  ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"``: ` ` `  `    ``mat ``=` `[[``1``, ``1``, ``2``], [``3``, ``4``, ``6``], [``5``, ``3``, ``2``]] ` `    ``R ``=` `C ``=` `3` `    ``arr ``=` `[Cell(``0``, ``0``), Cell(``1``, ``1``), Cell(``0``, ``1``)]  ` `    ``n ``=` `len``(arr) ` `    ``printSums(mat, arr, n)  ` `     `  `# This code is contributed by Rituraj Jain `

Output:

```15
10
16```

Time complexity of the above solution is O(n * R * C) where n is number of given cell indexes and R x C is matrix size.

An Efficient Solution can compute all sums in O(R x C + n) time. The idea is to precompute total sum, row and column sums before processing the given array of indexes. Below are details
1. Calculate sum of matrix, call it sum.
2. Calculate sum of individual rows and columns. (row[] and col[])
3. For a cell index (i, j), the desired sum will be “sum- row[i] – col[j] + arr[i][j]”

Below is the implementation of above idea.

## C++

 `// An efficient C++ program to compute sum for given array of cell indexes ` `#include ` `#define R 3 ` `#define C 3 ` `using` `namespace` `std; ` ` `  `// A structure to represent a cell index ` `struct` `Cell ` `{ ` `    ``int` `r; ``// r is row, varies from 0 to R-1 ` `    ``int` `c; ``// c is column, varies from 0 to C-1 ` `}; ` ` `  `void` `printSums(``int` `mat[][C], ``struct` `Cell arr[], ``int` `n) ` `{ ` `    ``int` `sum = 0; ` `    ``int` `row[R] = {}; ` `    ``int` `col[C] = {}; ` ` `  `    ``// Compute sum of all elements, sum of every row and sum every column ` `    ``for` `(``int` `i=0; i

## Python3

 `# Python3 implementation of the approach ` ` `  `# A structure to represent a cell index ` `class` `Cell: ` ` `  `    ``def` `__init__(``self``, r, c): ` `        ``self``.r ``=` `r ``# r is row, varies from 0 to R-1 ` `        ``self``.c ``=` `c ``# c is column, varies from 0 to C-1 ` ` `  `# A simple solution to find sums  ` `# for a given array of cell indexes ` `def` `printSums(mat, arr, n): ` ` `  `    ``Sum` `=` `0` `    ``row, col ``=` `[``0``] ``*` `R, [``0``] ``*` `C ` ` `  `    ``# Compute sum of all elements, ` `    ``# sum of every row and sum every column ` `    ``for` `i ``in` `range``(``0``, R): ` `        ``for` `j ``in` `range``(``0``, C): ` `            ``Sum` `+``=` `mat[i][j] ` `            ``row[i] ``+``=` `mat[i][j] ` `            ``col[j] ``+``=` `mat[i][j] ` ` `  `    ``# Compute the desired sum  ` `    ``# for all given cell indexes ` `    ``for` `i ``in` `range``(``0``, n): ` `        ``r0, c0 ``=` `arr[i].r, arr[i].c ` `        ``print``(``Sum` `-` `row[r0] ``-` `col[c0] ``+` `mat[r0][c0]) ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"``: ` ` `  `    ``mat ``=` `[[``1``, ``1``, ``2``], [``3``, ``4``, ``6``], [``5``, ``3``, ``2``]] ` `    ``R ``=` `C ``=` `3` `    ``arr ``=` `[Cell(``0``, ``0``), Cell(``1``, ``1``), Cell(``0``, ``1``)] ` `    ``n ``=` `len``(arr) ` `    ``printSums(mat, arr, n) ` ` `  `# This code is contributed by Rituraj Jain `

Output:

```15
10
16```

Time Complexity: O(R x C + n)
Auxiliary Space: O(R + C)

Thanks to Gaurav Ahirwar for suggesting this efficient solution.

Matrix Matrix