Spiral Matrix II: A Comprehensive Guide to Understanding and Implementing the Problem

The Spiral Matrix II problem is a fascinating challenge that requires generating an n x n matrix filled with numbers from 1 to n² in a spiral order. This problem not only tests your understanding of matrix manipulation but also enhances your coding skills. In this blog, we will delve deep into the problem, explore its solution, and provide a detailed Java implementation.

Understanding the Spiral Matrix II Problem

The task is to create an n x n matrix and fill it with values starting from 1 up to n², arranged in a spiral order. Unlike its predecessor, where the matrix was provided, here you are required to generate it from scratch. Let’s break down the requirements:

Input: A positive integer n.
Output: An n x n matrix filled with integers from 1 to n² in a spiral pattern.

Visualizing the Spiral Order

To better understand the spiral order, consider the example of a 3 x 3 matrix:

    1  2  3
    8  9  4
    7  6  5

The numbers fill the matrix starting from the top-left corner, moving right, then down, left, and finally up, continuing inward until the matrix is completely filled. This pattern is crucial for implementing the solution effectively.

Algorithm Overview

The fundamental approach to solving this problem involves defining boundaries for the rows and columns and adjusting these boundaries as the matrix is filled. The key steps are as follows:

Initialize a two-dimensional array for the matrix.
Define four boundaries: r1 (top row), r2 (bottom row), c1 (left column), and c2 (right column).
Use a loop to fill the matrix in layers, adjusting the boundaries after each layer is filled.
Continue until all numbers are placed in the matrix.

Java Implementation

Now that we have a clear understanding of the algorithm, let’s implement it in Java:

    public class SpiralMatrixII {
        public int[][] generateMatrix(int n) {
            int[][] matrix = new int[n][n];
            int r1 = 0, r2 = n - 1, c1 = 0, c2 = n - 1;
            int value = 1;

            while (r1 <= r2 && c1 <= c2) {
                // Fill top row
                for (int c = c1; c <= c2; c++) {
                    matrix[r1][c] = value++;
                }
                r1++;

                // Fill right column
                for (int r = r1; r <= r2; r++) {
                    matrix[r][c2] = value++;
                }
                c2--;

                // Fill bottom row
                if (r1 <= r2) {
                    for (int c = c2; c >= c1; c--) {
                        matrix[r2][c] = value++;
                    }
                    r2--;
                }

                // Fill left column
                if (c1 <= c2) {
                    for (int r = r2; r >= r1; r--) {
                        matrix[r][c1] = value++;
                    }
                    c1++;
                }
            }
            return matrix;
        }

        public static void main(String[] args) {
            SpiralMatrixII sm = new SpiralMatrixII();
            int n = 3;
            int[][] result = sm.generateMatrix(n);
            for (int[] row : result) {
                for (int val : row) {
                    System.out.print(val + " ");
                }
                System.out.println();
            }
        }
    }

This code sets up a class SpiralMatrixII with a method generateMatrix that constructs the spiral matrix. The main method demonstrates how to use this class to generate a 3 x 3 spiral matrix.

Time and Space Complexity

Understanding the efficiency of your solution is crucial. The time complexity of this algorithm is O(n²) because we fill n² elements in the matrix. The space complexity is O(1) if we do not consider the output matrix since we are using a fixed amount of space for variables.

Testing the Implementation

It’s essential to test the implementation with various inputs to ensure its correctness. Here are some test cases:

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

By running these test cases, we can confirm that our implementation works as intended.

Conclusion

The Spiral Matrix II problem is an excellent exercise for understanding matrix manipulation and algorithm design. By following the structured approach outlined in this blog, you can efficiently generate a spiral matrix. For those interested in further challenges, consider checking out some additional resources like the August LeetCoding Challenge 2020 or the problem link on LeetCode.

Thank you for reading, and happy coding!

Spiral Matrix II