Spiral Matrix


Given an m x n matrix, return all elements of the matrix in spiral order.

Example

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

Output: [1,2,3,6,9,8,7,4,5]

 

Approach

We will be using four loops as follows:

  • 1st loop: This will print the elements from left to right.
  • 2nd loop: This will print the elements from top to bottom.
  • 3rd loop: This will print the elements from right to left.
  • 4th loop: This will print the elements from bottom to top.
  • Create and initialize variables
  • top : starting row index
  • bottom : ending row index
  • left : starting column index
  • right : ending column index

 

 

  • In each outer loop traversal print the elements of a square in a clockwise manner.
  • Print the top row, i.e. Print the elements of the top row from column index left to right and increase the count of the top so that it will move to the next row.
  • Print the right column, i.e. Print the rightmost column from row index top to bottom and decrease the count of right.
  • Print the bottom row, i.e. if top <= bottom, then print the elements of a bottom row from column right to left and decrease the count of bottom
  • Print the left column, i.e. if left <= right, then print the elements of the left column from the bottom row to the top row and increase the count of left.
  • Run a loop until all the squares of loops are printed.

 

Complexity

  • Time Complexity:  O(m x n) Since all the elements are being traversed once and there are total n x m elements ( m elements in each row and total n rows) so the time complexity will be O(n x m).
  • Space Complexity:  O(n) Extra Space used for storing traversal in the ans array.

 

Code

# Java Code

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrixPrinter {

    public static List<Integer> printSpiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result; // Return empty list for empty matrix
        }

        int numRows = matrix.length;
        int numCols = matrix[0].length;

        int top = 0, left = 0, bottom = numRows - 1, right = numCols - 1;

        while (top <= bottom && left <= right) {
            // Move left to right
            for (int i = left; i <= right; i++)
                result.add(matrix[top][i]);
            top++;

            // Move top to bottom
            for (int i = top; i <= bottom; i++)
                result.add(matrix[i][right]);
            right--;

            // Move right to left
            if (top <= bottom) {
                for (int i = right; i >= left; i--)
                    result.add(matrix[bottom][i]);
                bottom--;
            }

            // Move bottom to top
            if (left <= right) {
                for (int i = bottom; i >= top; i--)
                    result.add(matrix[i][left]);
                left++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // Example with an irregular matrix
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}};

        List<Integer> result = printSpiralOrder(matrix);

        for (int value : result) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
Output

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10



Thanks for feedback.



Read More....
Find the no of islands in a 2D Array/Matrix
3 Sum
4 Sum - Find four elements that sum to a given target value
Chocolate Distribution Problem
Find the missing number in a sorted array
Best Time to Buy and Sell Stock