✔️ O(n) time complexity | explanation C++
Time complexity: O(n)\nSpace complexity: O(1)\n\nThe following code only iterates through the diagonals with time complexity of O(n) which is needed, instead of
**Time complexity: $$O(n)$$\nSpace complexity: $$O(1)$$**\n\nThe following code only iterates through the diagonals with time complexity of $$O(n)$$ which is needed, instead of going through the whole matrix with time complexities of $$O(n^2)$$. Those solutions go through the whole matrix with 2 $$for$$ loops, which you might have seen in a few other solutions.\n\nThe following code is a good optimization to reduce the time complexity.\n\n``` C++ []\nclass Solution {\npublic:\n    int diagonalSum(vector<vector<int>>& mat) {\n        int n = mat.size(), sumM{0};\n        for (int i=0; i<n; ++i) {\n            sumM+=mat[i][i]+mat[n-i-1][i];\n        }\n\n        // don\'t forget to remove the common element added\n        // reminder: only matrix with odd size would have common elements in the diagnals\n        // n/2 is case of odd n rounds to off the nearest integer below it\n        if (n%2) sumM-=mat[n/2][n/2];\n\n        return sumM;\n    }\n};\n```\n\n## Upvote the solution if it helped you! Happy coding :)\n
['Array', 'Matrix', 'C++']