Note:
The total number of elements of the given matrix will not exceed 10,000.
Complexity: O(n) time and O(1) space
classSolution:deffindDiagonalOrder(self,matrix):""" :type matrix: List[List[int]] :rtype: List[int] """ifnot matrix:return [] n_rows =len(matrix) n_cols =len(matrix[0]) L = []for i inrange(0, n_rows): L.append((i, 0))for j inrange(1, n_cols): L.append((n_rows -1, j))defdiagonal_along(r,c,reverse): diagonal = []while r >=0and c <len(matrix[0]): diagonal.append(matrix[r][c]) r -=1 c +=1if reverse:returnlist(reversed(diagonal))return diagonal sol = [] reverse =Falsefor x, y in L: sol +=diagonal_along(x, y, reverse) reverse =not reversereturn sol
The Idea: First grab the elements that make the 'L' as shown below. Then take the diagonal of each element. Reverse the diagonal as you go for each alternative diagonal.