Kth element in a spiral traversal of a special matrix

Question

We are given a square matrix which is filled with numbers from [1,n*n] in a row major form. We have to find the kth element when we traverse it in a spiral order. The only solution I could think was to to do a spiral traversal and maintain a counter for number of elements traversed. When counter value becomes k, we print the number at that instance.

Can this be solved in less than O(n*n)? If yes, then how to solve the same problem when matrix elements with random elements?

Link to the question

The number of elements in each ring differs from the previous ring by 8. — user3386109, Jul 23 '16 at 22:39
You can solve this problem in roughly O(1); you need to find the integer square root of `n*n-k`. Using the Babylonian method, for example, you can solve that in `log log n*n` iterations (which is `O(log log n)`) — rici, Jul 25 '16 at 04:36
There is strict constant time solution for this problem. See here: https://stackoverflow.com/questions/10094745/find-the-position-nth-element-of-a-rectangular-tiled-spiral — Eugene D. Gubenkov, Apr 06 '19 at 07:32

score 2 · Accepted Answer · answered Jul 24 '16 at 00:49

2

The first circle have 4(n - 1) nodes,

the second circle have 4(n - 2) nodes,

...

the last circle have 1 nodes.

step 1: you locate which circle the element you find is. O(n) step 2: use traversed method to determine this element. O(4n)

At last, O(n)

answered Jul 24 '16 at 00:49

kaitian521

548
2
10
25

1

The 2nd circle has 4(n-3) nodes (not 4(n-2)). After the first circle is peeled, you're left with a sub-matrix of (n-2)X(n-2) size. So, the number of elements on this circle will be 4*(n-3) – Bugaboo May 20 '17 at 15:16

Eugene D. Gubenkov · Answer 2 · 2019-04-08T20:55:10.207

Here is O(1) solution. I've tried to leave explanation for each step in the comments.

// takes q as zero based number in spiral traversal on square array n*n
// and returns zero based x, y coordinates in rectangular array with center
// at left top corner
public void SpiralToRect(int n, int q, out int x, out int y)
{
    // partial sum for rings count is 4 * k * (n - k)
    // ring counts go like this: 4 * (n - 1), 4 * (n - 3), ..., 4 * (n - 2k + 1)
    // partial sum is 4 * k * n - 4 * k * k

    // consider equation partial sum on k rings = q
    int k = (int)Math.Floor((n - Math.Sqrt(n * n - q)) / 2);

    // offset of element inside the ring is q - partial sum for k
    int ringOffset = q - 4 * k * (n - k);

    // it's easy to see how len of segments for k-th ring are calculated
    int[] l = new[]
    {
        n - 2 * k, // top
        n - 2 * k - 1, // right
        n - 2 * k - 1, // bottom
        n - 2 * k - 2, // left
    };

    // notice how kth ring starts at (k, k)

    if (ringOffset < l[0]) // top row
    {
        x = k + ringOffset;
        y = k;
    }
    else if (ringOffset < l[0] + l[1]) // right col
    {
        x = k + l[0] - 1;
        y = k + ringOffset - l[0] + 1;
    }
    else if (ringOffset < l[0] + l[1] + l[2]) // bottom row
    {
        x = k + 2 * l[0] + l[1] - ringOffset - 2;
        y = k + l[1];
    }
    else // left column
    {
        x = k;
        y = k + l[0] + 2 * l[1] + l[2] - ringOffset - 1;
    }
}

For the sample array below it returns numbers 1, 2, ..., 35, 36.

void Main()
{
    int[,] spiral = new int[,]
    {
        { 01, 02, 03, 04, 05, 06, },
        { 20, 21, 22, 23, 24, 07, },
        { 19, 32, 33, 34, 25, 08, },
        { 18, 31, 36, 35, 26, 09, },
        { 17, 30, 29, 28, 27, 10, },
        { 16, 15, 14, 13, 12, 11, },
    };

    for (int q = 0; q < 36; q++)
    {
        int x, y;
        SpiralToRect(6, q, out x, out y);

        spiral[y, x].Dump();
    }
}

Kth element in a spiral traversal of a special matrix

2 Answers2