14 2D_Array: Diagonal Traverse

[zwkcoding]

Solution: Tips:

• the maximum diagonal index is simply ((N-1) + (M-1)) = N + M -2;
• the sum of row i and column j is equal to the index of the diagonal index

Notice: Time Complexity is (N+M)^2, Try to analyse. tips: use nested loops, multiply principle

/// O = O((N+M)^2)
vector<int> findDiagonalOrder(vector<vector<int>>& matrix)  {
    if(matrix.empty())  return {};

    const int n = matrix.size();
    const int m = matrix[0].size();

    vector<int> res;
    for(int s = 0; s <= n + m -2;  s++)  {
        int i = 0, j = 0;
        for(int x = 0; x <= s; x++)  {
            i = x;
            j = s - x;
            // when it is even, rever dir
            if(s % 2 == 0)  {
                swap(i, j);
            }
            // touch edge
            if(i >= n || j >= m) continue;
            res.push_back(matrix[i][j]);
        }
    }
    return res;
}