C++ 88ms "non-walking" solution + explanation


  • 0
    N

    I noticed nearly every solution involved walking up the diagonal, moving across to the next, walking down, etc. etc.
    I decided, lets do a solution that isn't just walking through the whole thing.

    So the first thing to do is consider this: The numbers in each diagonal have the same Manhattan Distance, and that distance is the number of layers encountered.

    At diagonal #0, each element has a 0-distance from (0,0)
    At diagonal #3, each element has a 3-distance from (0,0)

    distance

    So now the problem isn't so much which way to walk, its instead selecting all items at a certain distance from (0,0), in a certain order.
    The first thing I then did was loop through each distance. The maximum distance should be M+N-1.

    for(int layerCount=0;layerCount<m+n-1;layerCount++)
    

    Now we need to consider each diagonal individually.
    What I did was basically walk from the minimum X position of a diagonal to the maximum X position, while doing the same in reverse for Y.
    since we know distance MUST equal layerCount, the maximum value must either be the end of the array or the layerCount.
    To account for the "walk direction" swapping each row, we can just check if the layerCount is divisible by 2, and if it is, we can add the element to the result in reverse order.

            vector<int> ret;
            int n = matrix.size();
            if(n == 0)
                return ret;
            int m = matrix[0].size();
            if(m==0)
                return ret;
            for(int layerCount=0;layerCount<m+n-1;layerCount++)
            {
                int maxX = min(layerCount,m-1);
                int maxY = min(layerCount,n-1);
                int minX = max(0,layerCount-maxY);
                int minY = max(0,layerCount-maxX);
        
                for(int i=0;minX+i<=maxX && minY+i<=maxY;i++)
                {
                    int xPos = minX+i;
                    int yPos = maxY-i;
                    if(layerCount%2)
                    {
                        xPos = minX+maxX-xPos;
                        yPos = minY+maxY-yPos;
                    }
                    ret.push_back(matrix[yPos][xPos]);
                }
            }
            return ret;
    

Log in to reply
 

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