Simulate the zigzag walk. Track direction, flip when you hit a boundary, and adjust coordinates.
Here's the solution:
function findDiagonalOrder(mat):
m = rows, n = cols
result = []
row = 0, col = 0
goingUp = true
for i in range(m * n):
result.append(mat[row][col])
if goingUp:
if col == n - 1:
row += 1
goingUp = false
else if row == 0:
col += 1
goingUp = false
else:
row -= 1
col += 1
else:
if row == m - 1:
col += 1
goingUp = true
else if col == 0:
row += 1
goingUp = true
else:
row += 1
col -= 1
return result
time, space (excluding output).