Java: 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 List<Integer> spiralOrder(int[][] matrix) {
        
        List<Integer> ans = new ArrayList<>();
        int row = matrix.length;
        int col = matrix[0].length;

        int left = 0;
        int right = col-1;
        int top = 0;
        int bottom = row-1;

        // This while condition is good.
        // Easy to forget what condition should we put in while.
        while(ans.size() < row*col){

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

            for(int i=top+1;i<=bottom && ans.size() < row*col;i++)
                ans.add(matrix[i][right]);

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

            for(int i=bottom-1;i>top && ans.size() < row*col;i--)
                ans.add(matrix[i][left]);

            left++;  right--;
            top++;   bottom--;
        }
        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!