LC 59 . Spiral Order Matrix II (Medium)

🔗 https://leetcode.com/problems/spiral-matrix-ii/

Problem Statement

You are given a positive integer N. You need to generate an N X N matrix, in which elements are from 1 to N² in spiral order.

Example 1

Input:

3

Output:

[ [1, 2, 3],

[8, 9, 4],

[7, 6, 5] ]

Example 2

Input:

4

Output:

[ [1, 2, 3, 4],

[12, 13, 14, 5],

[11, 16, 15, 6],

[10, 9, 8, 7] ]

Constraints:

1 <= N <= 10³

This was one of the questions that I solved the other day. As I am not at home today and currently at my relatives' home, I thought of revisiting this question.

I looked at the question, drew the matrix on paper and started observing the pattern. It was moving in a spiral way (well obv it's literally written in the question 😭).

The filling pattern was quite easy to observe:

1. Top Left → Right

2. Right Top → Bottom

3. Bottom Right → Left

4. Bottom Left → Top

And then the same thing repeats again for the inner layer.

This question is actually really easy to crack (trust me, I am saying this as someone who struggles with DSA 😭). It just takes a little bit of observation and practice.

The matrix is given with:

n rows n cols

which means we need to fill:

n * n

elements.

The first thing that came to my mind was that I need some boundaries, because while filling I should know where to stop and when to move towards the inner spiral.

So I created four boundaries:

top = 0; bottom = n - 1; left = 0; right = n - 1;

Why?

top = 0

because indexing starts from 0 and the top row is the first row.

bottom = n - 1

because the last row index is not n, it is n-1.

left = 0

because the first column index is 0.

right = n - 1

because the last column index is n-1.

And since we have to fill numbers from:

1 to n²

we start with:

num = 1;

Now let's focus on the filling part.

We need a loop which keeps running until there is still some area left to fill.

So the condition becomes:

while(top <= bottom && left <= right)

The moment these boundaries cross each other, there is no valid area left inside the matrix.

Let's understand this using:

n = 4

Final matrix:

[ [1, 2, 3, 4],

[12, 13, 14, 5],

[11, 16, 15, 6],

[10, 9, 8, 7] ]

Initially:

top = 0 bottom = 3 left = 0 right = 3

• Fill Top Row

We start from the top row.

Here the row remains fixed:

matrix[top][i]

and only the columns move.

So:

i = left → right

gets filled.

Result:

1 2 3 4

After filling the top row, we don't need to visit it again.

So:

top++;

• Fill Right Column

Now the right column remains fixed:

matrix[i][right]

and rows move from:

top → bottom

Result:

5 6 7

get filled.

Now the right boundary is complete.

So:

right--;

• Fill Bottom Row

Now we move from:

right → left

because we are moving backwards.

Result:

10 9 8

get filled.

The bottom row is now complete.

So:

bottom--;

• Fill Left Column

Now the left column remains fixed:

matrix[i][left]

and rows move:

bottom → top

Result:

11 12

get filled.

Now the left boundary is complete.

So:

left++;

At this point the outer spiral is done.

The matrix looks like:

[ [1, 2, 3, 4],

[12, _, _, 5],

[11, _, _, 6],

[10, 9, 8, 7] ]

Now notice something.

All four boundaries have moved:

top++; bottom--; left++; right--;

which means we are now working only inside:

[ [13, 14],

[16, 15] ]

And the exact same process repeats again.

That is literally the whole question.

One thing that helped me understand this better was thinking that every spiral layer behaves like a rectangle.

Once that rectangle is filled, we shrink the rectangle and move to the next inner rectangle.

This is the code that I wrote:

public class Solution {

public int[][] spiralOrderMatrix(int n) {

    int[][] matrix = new int[n][n];

    int top = 0;
    int bottom = n - 1;
    int left = 0;
    int right = n - 1;

    int num = 1;

    while(top <= bottom && left <= right){

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

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

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

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

    return matrix;
}

 }

The biggest thing I learned from this question was that not every matrix problem needs some crazy logic.

Sometimes drawing the matrix on paper and observing the pattern for 5 minutes is enough to crack the entire question.

Also, this question made me realize how useful boundaries can be in matrix problems. Instead of worrying about every single cell, I only had to keep track of:

top bottom left right

and everything else automatically fell into place.

P.S. Sorry if the formatting feels a little off 😭. I'm currently away from home and writing/uploading this entirely from my phone, so it was a bit difficult to manage everything properly without my laptop.

Also, adding the LeetCode problem link was suggested by one of my friends, and I thought it was a pretty good idea for anyone who wants to try the question first before reading the solution. So thanks to him for that 😄.

Woww, another DSA log added 😭.

Ngl, writing the thought process takes way more effort than writing the code itself lol.

Will definitely try to continue documenting more problems as I learn.

Any suggestions, corrections, or feedback would be appreciated.

Thanks for reading :))