Leetcode: Diagonal Traverse

Diagonal Traverse



Similar Problems:


Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]

Note:
The total number of elements of the given matrix will not exceed 10,000.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/diagonal-traverse
#!/usr/bin/env python
## Basic Ideas:
##      Don't get confused with 2 things:
##        1. For coordinate in math, move one step down from (0, 0), we will get (0, -1)
##           Move one step down from matrix[i][j], we shall get matrix[i+1][j].
##           It's neither matrix[i][j+1] nor matrix[i][j-1]
##
##        2. In matrix[i][j], i indicates row_index, and j indicates col_index.
##           In (x, y), x indicates col_index, y indicates row_index
##
##        Starts with (0, 0)
##                 Sequence                 Move to next               When to stop              How to update starting position
##              +: (0, 0)                   m[i][j] -> m[i-1][j+1]    first row or last column   next node in clockwise position
##              -: (1, 0) (0, 1)            m[i][j] -> m[i+1][j-1]    first column or last row    next node in counter clockwise position
##              +: (0, 2) (1, 1) (2, 0)     m[i][j] -> m[i-1][j+1]
##              -: (2, 1) (1, 2)            m[i][j] -> m[i+1][j-1]
##              +: (2, 2)                   
##
## Complexity: Time O(n*n), Space O(1)
class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        row_count = len(matrix)
        if row_count == 0:
            return []
        col_count = len(matrix[0])
        res = [None] * (row_count * col_count)

        i, j, is_up = 0, 0, True
        for k in xrange(row_count * col_count):
            res[k] = matrix[i][j]
            if is_up:
                if i == 0 or j == col_count-1:
                    is_up = not is_up
                    if j != col_count - 1:
                        j = j+1
                    else:
                        i = i+1
                else:
                    i, j = i-1, j+1
            else:
                if j == 0 or i == row_count-1:
                    is_up = not is_up
                    if i != row_count -1:
                        i = i+1
                    else:
                        j = j+1
                else:
                    i,j = i+1, j-1
        return res

# s = Solution()
# print s.findDiagonalOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) #[1,2,4,7,5,3,6,8,9]
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.