CODEWITHSUNDEEP
algorithmmatrix
Shivam Mitra
Shivam Mitra

Reputation: 1052

Kth element in a spiral traversal of a special matrix

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

Upvotes: 2

Views: 1902

Answers (2)

Eugene D. Gubenkov
Eugene D. Gubenkov

Reputation: 5357

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

topology

// 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();
    }
}

Upvotes: 0

kaitian521
kaitian521

Reputation: 578

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)

Upvotes: 2

Related Questions