# Traverse Matrix in Reverse Diagonal strips

I thought this problem had a trivial solution, couple of for loops and some fancy counters, but apparently it is rather more complicated.

So my question is, how would you write (in C) a function traversal of a square matrix in diagonal strips.

Example:

1 2 3
4 5 6
7 8 9


Would have to be traversed in the following order:

,[2,6],[1,5,9],[4,8],

• Questions about C are off-topic here. – Yuval Filmus Aug 3 '17 at 8:29
• @YuvalFilmus I worked as you said but it is not working for me here is the code link you can check out my implementation. ideone.com/NG9ieN – Abhishek Tripathi Aug 3 '17 at 9:41
• Unfortunately this site is not for code review. I more-or-less spelled out the algorithm, and anything beyond that is bug-squashing. – Yuval Filmus Aug 3 '17 at 10:06

I hope that the following example will inspire you: $$(2,0) \\ (1,0),(2,1) \\ (0,0),(1,1),(2,2) \\ (0,1),(1,2) \\ (0,2)$$ This is the same as the order you were describing. Notice that line $i$ (counting from zero) consists of $(x,y)$ such that $y-x = i-2$, arranged in order of increasing $y$ (or decreasing $x$). Furthermore, $y$ runs from $\max(i-2,0)$ to $\min(i,2)$.

In the general $n\times n$ case, just replace all occurrences of $2$ with $n-1$, and let $i$ run from $0$ to $2n-1$.

Straight lines are defined by linear equations. Assuming arrays indexed from zero, as in C, you want the lines $x-y=c$ for $c=2,\,1,\,0,\,-1,\,-2$. This gives something like

for c := 2 to -2 step -1
for x := 0 to 2
y := x-c
if 0<=y<=2
print A[x,y]


Here's the Python version:

def reverse_diagonal_traversal(matrix):
side = len(matrix) + 1
iterations = side - 1
for i in range(1, side):
for j in range(i):
yield matrix[j][iterations + j - i]
for i in range(side - 2, 0, -1):
for j in range(i):
yield matrix[iterations + j - i][j]

def test(side):
matrix = [range(i * side, side + i * side) for i in range(side)]
print matrix
for i in reverse_diagonal_traversal(matrix):
print i


Writing this in C would require too much code dealing with memory (de)allocation / printing, which isn't really part of this problem. I'd imagine that porting the above to C won't be a problem.

The idea behind the code is that you need to produce iterations of 1..N length until you reach the main diagonal, and then N-1..1. In the first half, you'd have to select the row at N at the first step of the iteration, and then N-i for each value of i in the iteration. You'd select the column starting at nth iteration - length of iteration, and then for each iteration step you'd increment that by one.

Finally, I'm not sure this is the most "elegant" solution (maybe you can do it in just half the code), but I couldn't find a good way to do that.

• Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. And, most importantly: be nice. – Raphael Sep 3 '17 at 14:00