Traverse Matrix in Diagonal strips

user_183789 0
Viewed 52117

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:

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

Each strip above is enclosed by square brackets. One of the requirements is being able to distinguish between strips. Meaning that you know when you're starting a new strip. This because there is another function that I must call for each item in a strip and then before the beginning of a new strip. Thus a solution without code duplication is ideal.

traversal matrix c algorithm
17 Answers

A simple python solution

from collections import defaultdict

def getDiagonals(matrix):
    n, m = len(matrix), len(matrix[0])
    diagonals = defaultdict(list)

    for i in range(n):
        for j in range(m):
            diagonals[i+j].append(matrix[i][j])

    return list(diagonals.values())

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

assert getDiagonals(matrix) == [[1], [2, 4], [3, 5, 7], [6, 8], [9]]
user_58725370
Related