C++: Spiral Matrix

Thought Process

The problem requires traversing a 2D matrix in a spiral order. We use a layer-by-layer approach to solve this. We define four boundaries: left, right, up, and down. We traverse the matrix in four directions: left to right, top to bottom, right to left, and bottom to top. After traversing each layer, we adjust the boundaries to move inward and repeat the process until all elements are visited. This ensures we cover the entire matrix in a spiral manner. 

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        
        int row = matrix.size();
        int col = matrix[0].size();

        int left  = 0;
        int right = matrix[0].size()-1;
        int up = 0;
        int down = matrix.size()-1;

        vector<int> ans;

        // Iterate till we got all elements. Total elements = row*col
        while(ans.size() < row*col){

            for(int i=left;i<=right && ans.size()<row*col;i++)
                ans.push_back(matrix[up][i]);

            for(int i=up+1;i<=down && ans.size()<row*col;i++)
                ans.push_back(matrix[i][right]);

            for(int i=right-1;i>=left && ans.size()<row*col;i--)
                ans.push_back(matrix[down][i]);

            for(int i=down-1;i>up && ans.size()<row*col;i--)
                ans.push_back(matrix[i][left]);

            left++;
            right--;
            up++;
            down--;
        }
        return ans;
    }
};

Code Complexity

Time Complexity: O(m * n)

The algorithm visits each element of the matrix exactly once, resulting in a time complexity of O(m * n), where m is the number of rows and n is the number of columns.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, excluding the space required for the output.

Code copied!