0ms easy c++ solution


  • 2
    A

    Approach #1 [Accepted]

    Algorithm

    Initialize rowStart as 0 , rowEnd as m-1 , colStart as a 0 and colEnd as a n-1 , where m is no of rows and n is no of column.

    For traversing the matrix in the spiral order follow following order.

    1. Right traverse top-most row and increment rowStart
    2. Down traverse right-most column and decrement colEnd
    3. Left traverse bottom-most row and decrement rowEnd
    4. Up traverse left-most column and increment colStart
      until rowEnd>=rowStart and colEnd>=colStart.

    After step 2 we have to check whether row and column exists to avoid any duplication.

    C++

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            int rowStart=0;
            int rowEnd=matrix.size()-1;
            vector<int> ans;
            if(rowEnd<0)
            {
                return ans;
            }
            int colStart=0;
            int colEnd=matrix[0].size()-1;
            while(rowStart<=rowEnd && colStart<=colEnd)
            {
                for(int i=colStart;i<=colEnd;i++)
                {
                    ans.push_back(matrix[rowStart][i]);
                }
                rowStart++;
                for(int i=rowStart;i<=rowEnd;i++)
                {
                    ans.push_back(matrix[i][colEnd]);
                }
                colEnd--;
                if(rowStart>rowEnd || colStart>colEnd)
                {
                    break;
                }
                for(int i=colEnd;i>=colStart;i--)
                {
                    ans.push_back(matrix[rowEnd][i]);
                }
                rowEnd--;
                for(int i=rowEnd;i>=rowStart;i--)
                {
                    ans.push_back(matrix[i][colStart]);
                }
                colStart++;
            }
            return ans;
        }
    };
    

    Complexity Analysis

    • Time complexity = O(m*n) , where m is the no of rows and n is the no of columns.

    • space complexity = O(m*n).


Log in to reply
 

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