11-line C++ Easy to Understand Approach with Illustration


  • 0

    The most common way to do this is diagonally walking through the matrix. The tricky part is to make the coordinate correct. I have a fair simple solution, by walking on a bigger matrix and only push valid coordinates, so a simple rule would work.

    If off the board while walking towards top-right, move down 1 unit. 
    If off the board while walking towards bottom-left, move right 1 unit.
    

    For example:

            x     x
       [ 1, 2, 3 ]x
       [ 4, 5, 6 ],
    x->[ 7, 8, 9 ]
         x->x
    
    class Solution {
    public:
        vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
            vector<int> res, yx(2,0);
            int d=1, h=matrix.size(), w=h?matrix[0].size():0; // d is direction
            while(res.size()<h*w) {
                valid(yx,h,w)?res.push_back(matrix[yx[0]][yx[1]]):(void)0; // If in matrix, push back
                d?(yx[0]--,yx[1]++):(yx[0]++,yx[1]--); // move to next
                valid(yx,h,w)?0:((d=!d)?yx[1]++:yx[0]++); // If out of matrix, flip d and adjust accordingly
            }
            return res;
        }
        
        bool valid(vector<int>& yx, int h, int w){
            return (yx[0]>=0&&yx[0]<h&&yx[1]>=0&&yx[1]<w)?true:false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.