LeetCode: Spiral Matrix II C#

Question

https://leetcode.com/problems/spiral-matrix-ii/ Please review for performance, how can this code run faster

Given a positive integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

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

using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{

    /// <summary>
    /// https://leetcode.com/problems/spiral-matrix-ii/
    /// </summary>
    [TestClass]
    public class SpiralMatrix2Test
    {
        [TestMethod]
        public void Example3x3Test()
        {
            int size = 3;
            int[][] expected =
            {
                new[]{1,2,3},
                new [] {8,9,4},
                new []{7,6,5}
            };
            int[][] res= SpiralMatrix2.GenerateMatrix(size);
            for (int i = 0; i < size; i++)
            {
                CollectionAssert.AreEqual(expected[i],res[i]);
            }
        }
}

    public class SpiralMatrix2
    {
        public static int[][] GenerateMatrix(int n)
        {

            int startCol = 0;
            int endCol = n - 1;
            int startRow = 0;
            int endRow = n - 1;
            int num = 1;
            int[][] res = new int[n][];
            for (int i = 0; i < n; i++)
            {
                res[i] = new int[n];
            }

            if (n == 0)
            {
                return res;
            }

            while (startCol <= endCol && startRow <= endRow)
            {
                for (int i = startCol; i <= endCol; i++)
                {
                    res[startRow][i] = num++;
                }
                startRow++;// already did this row skip to the next one

                for (int i = startRow; i <= endRow; i++)
                {
                    res[i][endCol] = num++;
                }

                endCol--;// already did the last col move back one col

                for (int i = endCol; i >= startCol; i--)
                {
                    //keep in mind this is a spiral we can be in a line we are not suppose to touch the values
                    //only in the upper half of the matrix we need
                    if (startRow <= endRow)
                    {
                        res[endRow][i] = num++;
                    }
                }
                endRow--;


                for (int i = endRow; i >= startRow; i--)
                {
                    //we need to print the numbers only in the left half of the matrix
                    if (startCol <= endCol)
                    {
                        res[i][startCol] = num++;
                    }
                }

                startCol++;
            }
            return res;

        }
    }
}

Martin R · Accepted Answer · 2019-10-03 11:35:40Z

If n is zero then the loop

while (startCol <= endCol && startRow <= endRow)

does nothing, which means that the test

if (n == 0)

is not necessary.

Here

for (int i = endCol; i >= startCol; i--)
{
    //keep in mind this is a spiral we can be in a line we are not suppose to touch the values
    //only in the upper half of the matrix we need
    if (startRow <= endRow)
    {
        res[endRow][i] = num++;
    }
}

the condition of the if-statement is a loop invariant, so that it can be done outside of the loop:

if (startRow <= endRow)
{
    for (int i = endCol; i >= startCol; i--)
    {
        res[endRow][i] = num++;
    }
}

Even if the C# compiler is smart enough to recognize the loop invariant and reorders the statements, the latter variant would be clearer to the reader of your code. The same applies to the next loop in your function.

Then note that startRow/startCol and endRow/endCol have the same value at the start of the loop body, and the tests

if (startRow <= endRow) ...
if (startCol <= endCol) ...

can fail only in the last iteration. Therefore one can move that case out of the main loop, use only two variables for the first and last row/column, and write the inner loops in a symmetric fashion:

int start = 0;
int end = n - 1;

while (start < end)
{
    for (int i = start; i < end; i++)
    {
        res[start][i] = num++;
    }
    for (int i = start; i < end; i++)
    {
        res[i][end] = num++;
    }
    for (int i = end; i > start; i--)
    {
        res[end][i] = num++;
    }
    for (int i = end; i > start; i--)
    {
        res[i][start] = num++;
    }

    start++;
    end--;
}

if (start <= end)
{
    res[start][start] = num;
}

Kuba hasn't forgotten Monica · Accepted Answer · 2019-10-03 12:02:11Z

Ignoring everything else, you're iterating the array in a very cache-inefficient manner, and that will ultimately limit the performance. You need to iterate in column-major order, i.e. iterate down a column, and only then advance to next column - assuming that the indices mean [row][column].

Technically all you need to provide is a way to quickly generate these numbers on the fly, and provide a double-indexable property on the "matrix" object, and you're done. But whether LeetCode's implementation can deal with a double-indexable object other than int[][] is unknown to me.

That might be the fastest, since there's no memory overhead, and a conversion between the index and the value is quick (I urge you to look the formula up or figure it out yourself). Note that integer multiplications are fast, so doing a couple of them will be still faster than a cache miss.

But once you got that done, filling the array in any order - whether row-major or column-major is trivial, and it can be parallelized, too. And perhaps you can figure a formula that leverages such order and does even less work than a general item-value formula :)

Let's also note that int is a 32-bit signed type, so the largest integer square that will fit into it must be less than 2^31. Thus, the largest input is 0xB504, and the resulting square matrix has 0x7FFEA810 elements. You'd want to check the argument to make sure it's not too large, and throw an ArgumentOutOfRangeException otherwise.

Stack Exchange Network

LeetCode: Spiral Matrix II C#

2 Answers 2

You must log in to answer this question.

Hot Network Questions

LeetCode: Spiral Matrix II C#

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions