Given a matrix with N rows and M columns, print all elements present on the anti-diagonal.
Example 1
Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: 3 5 7
Explanation: Anti-diagonal cells are mat[0][2], mat[1][1], and mat[2][0].
Example 2
Input: mat = [[10, 20], [30, 40], [50, 60]]
Output: 20 30
Explanation: Rectangular matrix anti-diagonal starts at mat[0][1] and stops after mat[1][0] because the next column index becomes invalid.
Approach
The anti-diagonal starts at the top-right corner and moves toward the bottom-left. At each step, the row index increases while the column index decreases. A single loop is enough to visit all anti-diagonal elements until either boundary of the matrix is reached. Every selected cell follows the relation row + col = M - 1 for zero-based indexing.
Algorithm
Find the number of rows and columns in the matrix, as the starting position and traversal boundary depend on its dimensions.
Initialize
row = 0andcol = m - 1, since the anti-diagonal begins at the top-right corner.Traverse while
rowremains within the matrix andcolis non-negative, as these conditions keep the traversal inside the matrix boundaries.Print the element at
mat[row][col], since every position reached this way satisfies the anti-diagonal relationrow + col = m - 1.Increment
rowand decrementcol, as moving one step down and one step left reaches the next anti-diagonal element.Continue until either boundary is reached, ensuring every anti-diagonal element has been visited exactly once.
Dry Run
anti diagonal print
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to print anti-diagonal elements of a matrix. void printAntiDiagonal(vector<vector<int>>& mat) { // Store total number of rows. int n = mat.size(); // Handle an empty matrix. if (n == 0) { cout << "\n"; return; } // Store total number of columns. int m = mat[0].size(); // Start from the top-right cell. int row = 0; int col = m - 1; // Track first printed value for spacing. bool first = true; // Traverse while row and column remain valid. while (row < n && col >= 0) { // Print a space before every value except the first value. if (!first) { cout << " "; } // Print the current anti-diagonal element. cout << mat[row][col]; // Mark first value as printed. first = false; // Move one step down. row++; // Move one step left. col--; } // Move output cursor to the next line after printing finishes. cout << "\n"; }};// Driver code.int main() { vector<vector<int>> mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; Solution sol; sol.printAntiDiagonal(mat); return 0;}Complexity Analysis
Time Complexity: O(min(N, M)), traversal visits one anti-diagonal cell for every valid row-column pair.
Space Complexity: O(1), only loop variables are used apart from output handling.
Interview follow-up Questions
Cells from the top-right to bottom-left direction belong to the anti-diagonal.
Be the first to add a comment.