Table of contents
1.
Introduction
2.
Problem Statement
3.
Examples
4.
Naive Approach: Using Simulation by Visited Matrix – O(m*n) time and O(m*n) auxiliary space
5.
Space Optimized Approach: Using Boundary Traversal – O(m*n) time and O(1) auxiliary space
6.
Implementation in Java 
7.
Frequently Asked Questions
7.1.
Can a spiral matrix be generated for non-square matrices?
7.2.
How can we determine the number of complete spirals in a given matrix?
7.3.
Can we generate a spiral matrix in reverse order?
8.
Conclusion
Last Updated: Nov 16, 2024
Easy

Spiral Matrix in Java

Author Rinki Deka
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A spiral matrix is a unique way to arrange numbers in a two-dimensional grid. Just imagine filling a square or rectangular grid with numbers, starting from the top-left corner and moving in a spiral pattern until you reach the center. A spiral matrix is a complex structure where data is organized in a spiral format, starting from the outside and working its way to the center. This fascinating arrangement creates an intriguing pattern that has various applications in programming and problem-solving. 

Spiral Matrix in Java

In this article, we'll discuss the unique concept of spiral matrices, understand how to generate them using Java code and look into different approaches to solve problems related to this. 

Problem Statement

The problem at hand is to generate a spiral matrix given its dimensions, typically represented by the number of rows (m) & columns (n). The objective is to fill the matrix with numbers from 1 to m*n in a spiral pattern, starting from the top-left corner and moving clockwise. The spiral pattern follows a specific order:
 

1. Start from the top-left corner & move right until you reach the right boundary.
 

2. Move down along the right boundary until you reach the bottom boundary.
 

3. Move left along the bottom boundary until you reach the left boundary.
 

4. Move up along the left boundary until you reach the top boundary.
 

5. Repeat steps 1-4, spiraling inward until all the cells are filled.
 

The challenge is to develop an algorithm that generates the spiral matrix efficiently and correctly.

Examples

To better understand the problem, let's look at a few examples of spiral matrices.


Example 1:

Input: m = 3, n = 3

Output:

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


Example 2:

Input: m = 4, n = 4

Output:

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


Example 3:

Input: m = 5, n = 6

Output:

[
 [1,  2,  3,  4,  5, 6],
 [18, 19, 20, 21, 22, 7],
 [17, 28, 29, 30, 23, 8],
 [16, 27, 26, 25, 24, 9],
 [15, 14, 13, 12, 11, 10]
]

 

These examples show how the numbers are arranged in a spiral pattern within matrices of different dimensions. The pattern remains consistent, starting from the top-left corner and spiraling inward until all the cells are filled.

Naive Approach: Using Simulation by Visited Matrix – O(m*n) time and O(m*n) auxiliary space

One easy and simple approach to generating a spiral matrix is to simulate the spiral traversal using a visited matrix to keep track of the cells that have been filled. Let’s see how the naive approach works:

1. Create an empty matrix of size m x n to store the spiral matrix.
 

2. Create a visited matrix of the same size to keep track of the cells that have been filled.
 

3. Initialize variables to keep track of the current position (row & column) & the current direction (right, down, left, up).
 

4. Start from the top-left corner & move in the current direction until you reach a cell that is either out of bounds or already visited.
 

5. Fill the current cell with the next number & mark it as visited in the visited matrix.
 

6. If the current cell is out of bounds or already visited, change the direction according to the spiral pattern (right -> down -> left -> up).
 

7. Repeat steps 4-6 until all the cells are filled.
 

Let’s look at the implementation of this approach: 

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int row = 0, col = 0, dirIdx = 0;

        for (int i = 1; i <= n * n; i++) {
            matrix[row][col] = i;
            int nextRow = row + dirs[dirIdx][0];
            int nextCol = col + dirs[dirIdx][1];

            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n || matrix[nextRow][nextCol] != 0) {
                dirIdx = (dirIdx + 1) % 4;
            }

            row += dirs[dirIdx][0];
            col += dirs[dirIdx][1];
        }

        return matrix;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 4; 
        int[][] result = solution.generateMatrix(n);

        for (int[] row : result) {
            for (int num : row) {
                System.out.print(num + "\t");
            }
            System.out.println();
        }
    }
}
You can also try this code with Online Java Compiler
Run Code


Output

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


This approach's time complexity is O(m*n) since we need to fill all the cells of the matrix. Its space complexity is also O(m*n) as we use an additional visited matrix to keep track of the filled cells.

Space Optimized Approach: Using Boundary Traversal – O(m*n) time and O(1) auxiliary space

While the naive approach works, it requires additional space to keep track of the visited cells. We can optimize the space complexity by using a boundary traversal approach. Let’s see how it works:

1. Create an empty matrix of size m x n to store the spiral matrix.
 

2. Initialize variables to keep track of the boundaries (top, bottom, left, right) & the current number.
 

3. Start from the top-left corner & traverse the matrix in a spiral pattern:
 

   - Traverse the top row from left to right & increment the top boundary.
 

   - Traverse the right column from top to bottom & decrement the right boundary.
 

   - Traverse the bottom row from right to left & decrement the bottom boundary.
 

   - Traverse the left column from bottom to top & increment the left boundary.
 

4. Repeat step 3 until all the cells are filled.

Implementation in Java 

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;

        while (num <= n * n) {
            for (int i = left; i <= right && num <= n * n; i++) {
                matrix[top][i] = num++;
            }
            top++;

            for (int i = top; i <= bottom && num <= n * n; i++) {
                matrix[i][right] = num++;
            }
            right--;

            for (int i = right; i >= left && num <= n * n; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;

            for (int i = bottom; i >= top && num <= n * n; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }

        return matrix;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 4;
        int[][] result = solution.generateMatrix(n);

        for (int[] row : result) {
            for (int num : row) {
                System.out.print(num + "\t");
            }
            System.out.println();
        }
    }
}
You can also try this code with Online Java Compiler
Run Code


Output

For n=4

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


The time complexity of this approach remains O(m*n) as we need to fill all the cells of the matrix. However, the space complexity is reduced to O(1) since we don't use any additional data structures & only use a constant amount of extra space for the variables.

Frequently Asked Questions

Can a spiral matrix be generated for non-square matrices?

Yes, a spiral matrix can be generated for non-square matrices as well. The same approach of boundary traversal can be applied to matrices with different numbers of rows & columns. The algorithm will follow the spiral pattern, starting from the top-left corner & filling the cells until all the cells are filled.

How can we determine the number of complete spirals in a given matrix?

The number of complete spirals in a matrix depends on the dimensions of the matrix. In a square matrix of size n x n, the number of complete spirals is floor(n/2). For example, in a 5x5 matrix, there will be 2 complete spirals. In a non-square matrix, the number of complete spirals is determined by the minimum of floor(m/2) & floor(n/2), where m & n are the number of rows & columns, respectively.

Can we generate a spiral matrix in reverse order?

Yes, it is possible to generate a spiral matrix in reverse order. Instead of starting from 1 and incrementing the numbers, we can start from m*n and decrement the numbers while traversing the matrix in a spiral pattern. The boundary traversal approach can be modified to fill the cells with numbers in descending order.

Conclusion

In this article, we have discussed the fascinating concept of spiral matrices and learned how to generate them using Java. We started by understanding the problem statement and looking at examples of spiral matrices. We then discussed two approaches to solving the problem: the naive approach using a visited matrix and the space-optimized approach using boundary traversal. 

You can also check out our other blogs on Code360.

Live masterclass