Leetcode - Sort the Matrix Diagonally (Python)

January 2021 Leetcode Challenge
Leetcode - Sort the Matrix Diagonally #1329

[janmichaelaustria]

In the December challenge they wen through a similar problem and it was there I picked up the trick that all elements in the same diagonal have the same (i-j) index, so i just hashed everything to that key, sorted, and rebuilt. But I agree, for this problem it is a really good exercise to try 'walking the diagonals' and rebuilding from that. Nice video Time. Here'a another way:

rows = len(mat)
cols = len(mat[0])
diags = []

#walk the diags start at the first col, stop at fiirst row
for i in range(1, rows):
curr_row, curr_col = rows - i, 0
temp = []
while curr_row < rows and curr_col < cols:

curr_row += 1
curr_col += 1


#now walk the diags start staying at the first row but moving through all the cols
for i in range(cols):
curr_row, curr_col = 0, i
#down right until i cannot
temp = []
while curr_row < rows and curr_col < cols:

curr_row += 1
curr_col += 1


#now build the new matrix, just replace mat[i][j]
#which was just walking the diags again
#traverse our diags and take first element

#reverse diags
diags = diags[::-1]

#repeat for rows
for i in range(1, rows):
curr_row, curr_col = rows - i, 0
#get elemenets
candidates = diags.pop()
while curr_row < rows and curr_col < cols and candidates:
mat[curr_row][curr_col] = candidates.pop()
curr_row += 1
curr_col += 1

#repeat for cols
for i in range(cols):
curr_row, curr_col = 0, i
#down right until i cannot
#get elemenets
candidates = diags.pop()
while curr_row < rows and curr_col < cols and candidates:
mat[curr_row][curr_col] = candidates.pop()
curr_row += 1
curr_col += 1
return mat