Print diagonal elements of a matrix having a positive slope
Given an M × N integer matrix, print all its diagonal elements having a positive slope.
For example,
Output:
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
6 6 6 6
7 7 7
8 8
9
The idea is to start from each cell of the first column of the matrix to print / diagonal for the matrix’s upper-left half. Similarly, after the upper-left half, start from each cell of the last row to print the / diagonal for the matrix’s lower-right half.
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <vector> using namespace std; void printMatrixDiagonally(vector<vector<int>> const &mat) { // base case if (mat.size() == 0) { return; } // `M × N` matrix int M = mat.size(); int N = mat[0].size(); // print `/` diagonal for the upper-left half of the matrix. for (int r = 0; r < M; r++) { // start from each cell of the first column for (int i = r, j = 0; j < N && i >= 0; i--, j++) { cout << mat[i][j] << " "; } cout << endl; } // print `/` diagonal for the lower-right half of the matrix for (int c = 1; c < N; c++) { // start from each cell of the last row for (int i = M - 1, j = c; j < N && i >= 0; i--, j++) { cout << mat[i][j] << " "; } cout << endl; } } int main() { vector<vector<int>> mat = { { 1, 2, 3, 4, 5 }, { 2, 3, 4, 5, 6 }, { 3, 4, 5, 6, 7 }, { 4, 5, 6, 7, 8 }, { 5, 6, 7, 8, 9 } }; printMatrixDiagonally(mat); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
class Main { public static void printMatrixDiagonally(int[][] mat) { // base case if (mat == null || mat.length == 0) { return; } int M = mat.length; int N = mat[0].length; // print `/` diagonal for the upper-left half of the matrix for (int r = 0; r < M; r++) { // start from each cell of the first column for (int i = r, j = 0; j < N && i >= 0; i--, j++) { System.out.print(mat[i][j] + " "); } System.out.print(System.lineSeparator()); } // print `/` diagonal for the lower-right half of the matrix for (int c = 1; c < N; c++) { // start from each cell of the last row for (int i = M - 1, j = c; j < N && i >= 0; i--, j++) { System.out.print(mat[i][j] + " "); } System.out.print(System.lineSeparator()); } } public static void main(String[] args) { int[][] mat = { { 1, 2, 3, 4, 5 }, { 2, 3, 4, 5, 6 }, { 3, 4, 5, 6, 7 }, { 4, 5, 6, 7, 8 }, { 5, 6, 7, 8, 9 } }; printMatrixDiagonally(mat); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
def printMatrixDiagonally(mat): # base case if not mat or not len(mat): return (M, N) = (len(mat), len(mat[0])) # print `/` diagonal for the upper-left half of the matrix for r in range(M): # start from each cell of the first column i = r j = 0 while j < N and i >= 0: print(mat[i][j], end=' ') i = i - 1 j = j + 1 print() # print `/` diagonal for the lower-right half of the matrix for c in range(1, N): # start from each cell of the last row i = M - 1 j = c while j < N and i >= 0: print(mat[i][j], end=' ') i = i - 1 j = j + 1 print() if __name__ == '__main__': mat = [ [1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8], [5, 6, 7, 8, 9] ] printMatrixDiagonally(mat) |
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
6 6 6 6
7 7 7
8 8
9
The time complexity of the proposed solution is O(M × N) for an M × N matrix and doesn’t require any extra space.
Count negative elements present in the sorted matrix in linear time
Change all elements of row `i` and column `j` in a matrix to 0 if cell `(i, j)` is 0
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)