# 498. Diagonal Traverse
#### Difficulty: Medium
link: https://leetcode.com/problems/diagonal-traverse/

### 1. Simulation
#### $O(MN)$ runtime, $O(1)$ space

這題讓我想到之前解過一題光學折射的題目 [Mirror Reflection](https://leetcode.com/problems/mirror-reflection/)，運用類似的概念，設定兩個 index 分別為 i 和 j 來 traverse matrix，以及他們各自要前進的方向 di 和 dj，當碰到 matrix 的四個邊界時，會對應到不同的反射方式。值得注意的是，需要優先考慮撞到右方或下方邊界的情況。

##### python

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        M = len(matrix)
        if M == 0: return []
        N = len(matrix[0])
        
        ans = []
        i , j = 0, 0
        di, dj = -1, 1
        while True:
            ans.append(matrix[i][j])
            if i == M-1 and j == N-1:
                break
            
            if i+di > M-1:
                di = -di
                dj = -dj
                j += dj
            elif j+dj > N-1:
                di = -di
                dj = -dj
                i += di
            elif i+di < 0:
                j += dj
                di = -di
                dj = -dj
            elif j+dj < 0:
                i += di
                di = -di
                dj = -dj
            else:
                i += di
                j += dj
        
        return ans

<font color="#00AB5F ">Accepted</font>
Runtime: **188 ms**, faster than **80.57%** of Python3 online submissions for Diagonal Traverse.
Memory Usage: **16.8 MB**, less than **37.68%** of Python3 online submissions for Diagonal Traverse.

### 2. Simulation
#### $O(MN)$ runtime, $O(MN)$ space

上面解法的缺點在於程式碼易讀性低，在討論區看到一個比較直觀的寫法。

利用了每個 diagonal 的兩個 index 總和固定的特性，先將每個 diagonal 的元素存在一個 dict 裡面，回傳前再對偶數 digonal 做 reverse。

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        d={}
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if i + j not in d:
                    d[i+j] = []
                d[i+j].append(matrix[i][j])

        ans= []
        for key, value in d.items():
            if key % 2 == 0:
                ans += reversed(value)
            else:
                ans += value
        return ans

<font color="#00AB5F ">Accepted</font>
Runtime: **192 ms**, faster than **68.01%** of Python3 online submissions for Diagonal Traverse.
Memory Usage: **17.2 MB**, less than **18.04%** of Python3 online submissions for Diagonal Traverse.

###### tags: `leetcode`