Given a matrix with N rows and M columns, find the sum of all elements present in the matrix.
Example 1
Input: mat = [[1, 2, 3], [4, 5, 6]]
Output: 21
Explanation: Sum of all cells is 1 + 2 + 3 + 4 + 5 + 6 = 21.
Example 2
Input: mat = [[10, -2], [3, 4], [5, 6]]
Output: 26
Explanation: Sum of all cells is 10 + (-2) + 3 + 4 + 5 + 6 = 26.
Approach
This approach visits every element of the matrix exactly once. As each cell is processed, its value is added to a running sum. After the entire matrix is traversed, the accumulated sum is returned.
Algorithm
Initialize
sumas0, as it serves as the running total of all elements in the matrix.Traverse every row using an outer loop, which allows each row to be processed one by one.
For each row, use an inner loop to traverse all columns, ensuring every element in the matrix is accessed exactly once.
Add the current element to
sum, as each visited value contributes to the total matrix sum.Return the final
sumafter all elements have been processed, since it now represents the sum of every matrix element.
Dry Run
sum of matrix
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to find the sum of all matrix elements. int matrixSum(vector<vector<int>>& mat) { // Store the running sum of visited elements. int sum = 0; // Traverse every row from top to bottom. for (int row = 0; row < (int)mat.size(); row++) { // Traverse every column from left to right. for (int col = 0; col < (int)mat[row].size(); col++) { // Add the current matrix element to the running sum. sum += mat[row][col]; } } // Return the final matrix sum. return sum; }};// Driver code.int main() { vector<vector<int>> mat = {{1, 2, 3}, {4, 5, 6}}; Solution sol; cout << sol.matrixSum(mat) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N × M), traversal visits every matrix cell exactly once.
Space Complexity: O(1), only the accumulator and loop variables are used.
Interview follow-up Questions
Yes. One loop selects each row, and another loop scans each column inside the selected row.
Be the first to add a comment.