Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order. The Spiral Matrix problem takes a 2-Dimensional array of N-rows and M-columns as an input, and prints the elements of this matrix in spiral order. The spiral begins at the top left corner of the input matrix, and prints the elements it encounters, while looping towards the center of this matrix, in a clockwise manner.​

Example

Spiral Matrix
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

How does the spiral matrix algorithm work?

2D Matrix
Spiral Order Traversal of a Matrix
  1. First, four variables containing the indices for the corner points of the array are initialized.
  2. The algorithm starts from the top left corner of the array, and traverses the first row from left to right. Once it traverses the whole row it does not need to revisit it, thus, it increments the top corner index.
  3. Once complete, it traverses the rightmost column top to bottom. Again, once this completes, there is no need to revisit the rightmost column, thus, it decrements the right corner index.
  4. Next, the algorithm traverses the bottommost row and decrements the bottom corner index afterward.
  5. Lastly, the algorithm traverses the leftmost column, incrementing the left corner index once it’s done.

This continues until the left index is greater than the right index, and the top index is greater than the bottom index.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
        List<Integer> result = new ArrayList<>();
        if(matrix == null || matrix.length == 0){
            return result;
        }
        int left = 0, up = 0;
        int right = matrix[0].length - 1;
        int bottom = matrix.length - 1;
        
        while( left <= right && up <= bottom){
            
            for(int i = up ; i <= right ; i++){
                result.add(matrix[up][i]);
            }
            up++;
            
            for(int i = up ; i <= bottom ; i++){
                result.add(matrix[i][right]);
            }
            right--;
            
            for(int i = right ; i >= left && up <= bottom ; i--){
                result.add(matrix[bottom][i]);
            }
            bottom--;
            
             for(int i = bottom ; i >= up && left <= right ; i--){
                result.add(matrix[i][left]);
            }
            left++;
        }
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(N), where N is the total number of elements in the input matrix.
  • Space Complexity: O(1) without considering the output array, since we don’t use any additional data structures for our computations.

Categories: Array

Tagged as: ,

1 reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s