Given a square matrix of size N x N, find the sum of elements present on both diagonals.
The main diagonal moves from the top-left cell to the bottom-right cell. The anti-diagonal moves from the top-right cell to the bottom-left cell. In an odd-sized matrix, the center cell belongs to both diagonals and must be counted only once.
Example 1
Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: 25
Explanation: Main diagonal sum is 1 + 5 + 9 = 15, anti-diagonal sum is 3 + 5 + 7 = 15, and center value 5 is counted once. Final sum is 25.
Example 2
Input: mat = [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
Output: 8
Explanation: Four main diagonal cells and four anti-diagonal cells contribute to the final answer.
Approach
Both diagonals can be processed using one loop over row index. For each row, the main diagonal element is present at column row, and the anti-diagonal element is present at column n - row - 1.
Algorithm
Initialize
sumas0and determine the matrix sizen, as both diagonal positions depend on the same row index.Traverse each row using a single loop from
0ton - 1, since both diagonals can be accessed directly using the current row index.Add
mat[i][i]tosum, as the row and column indices are the same for every main diagonal element.Add
mat[i][n - i - 1]tosum, as the column indexn - i - 1gives the corresponding position on the secondary diagonal.Check
i != n - i - 1before adding the secondary diagonal element, as this prevents the center element from being counted twice in an odd-sized matrix.Return
sumafter all rows have been processed, as it now represents the combined sum of both diagonals.
Dry Run
sum of both diagonals
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to find the sum of both diagonals int diagonalSum(vector<vector<int>>& mat) { // Store matrix size. int n = mat.size(); // Store the running diagonal sum. int sum = 0; // Traverse every row once. for (int row = 0; row < n; row++) { // Add the main diagonal element. sum += mat[row][row]; // Store anti-diagonal column for the current row. int antiCol = n - row - 1; // Add anti-diagonal element only when not already counted. if (antiCol != row) { sum += mat[row][antiCol]; } } // Return final diagonal sum. return sum; }};// Driver code.int main() { vector<vector<int>> mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; Solution sol; cout << sol.diagonalSum(mat) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N), traversal processes one row at a time and checks at most two diagonal cells per row.
Space Complexity: O(1), only a running sum and loop variables are used.
Interview follow-up Questions
Main diagonal and anti-diagonal are included.
Be the first to add a comment.