Given a matrix with N rows and M columns, find the sum of elements for every column.
Each column contributes one value to the answer. The value for a column equals the addition of all elements present in the column from top to bottom.
Example 1
Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [12, 15, 18]
Explanation: Column sums are 1 + 4 + 7 = 12, 2 + 5 + 8 = 15, and 3 + 6 + 9 = 18.
Example 2
Input: mat = [[1, 2], [10, 2], [3, 3]]
Output: [14, 7]
Explanation: First column sum is 1 + 10 + 3 = 14, and second column sum is 2 + 2 + 3 = 7.
Approach
This approach processes the matrix one column at a time. For each column, a running sum is maintained by adding all its elements from top to bottom. Once the column is fully traversed, the computed sum is stored in the result array.
Algorithm
Initialize an empty result array to store the sum of each column.
Traverse every column using an outer loop.
Initialize the sum as
0for the current column.Traverse all rows of the current column and add each element to the sum.
Store the column sum in the result array and return the result after all columns are processed.
Dry Run
column wise sum
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to find the sum of every matrix column. vector<int> columnWiseSum(vector<vector<int>>& mat) { // Store one sum for every column. vector<int> result; // Handle an empty matrix. if (mat.empty()) { return result; } // Store total number of rows. int n = mat.size(); // Store total number of columns. int m = mat[0].size(); // Traverse every column from left to right. for (int col = 0; col < m; col++) { // Store the running sum of the current column. int sum = 0; // Traverse every row from top to bottom. for (int row = 0; row < n; row++) { // Add the current column element to the running sum. sum += mat[row][col]; } // Store the final sum of the current column. result.push_back(sum); } // Return all column sums. return result; }};// Driver code.int main() { vector<vector<int>> mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; Solution sol; vector<int> ans = sol.columnWiseSum(mat); for (int index = 0; index < (int)ans.size(); index++) { if (index > 0) { cout << " "; } cout << ans[index]; } cout << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N × M), traversal visits every matrix cell exactly once.
Space Complexity: O(M), result array stores one sum for every column.
Interview follow-up Questions
Yes. You can traverse the matrix row by row instead. For every element mat[i][j], add its value to result[j]. This computes all column sums in a single row-wise traversal while producing the same result.
Be the first to add a comment.