How to perform spiral order traversalin one dimensional array?

Question

Possible Duplicates:
Looping in a spiral
Writing a string in a spiral
Print two-dimensional array in spiral order
2d Array in Spiral Order

We have a data in the form of matrix

which is stored in a 1d array in this fashion

[0 0 0 0 0 0 1 2 3 0 0 4 5 6 0 0 7 8 9 0 0 0 0 0 0]

This is a zero padded 3x3 array transformed into 5x5. We know the start index and end index.

As we see, we can perform 25 operations and print all values, but instead if we go in spiral order we should ideally do this in only 9 operations.

Does anyone know how to do this?

We know the number of rows and number of columns. Here it would be rows=5 cols=5.

Hence start index would be rows+1 and end index would be rows*cols-6

I'm visualizing it as a spiral order traversal.

what do you mean go in spiral order? You have a 1d array do you not? — Woot4Moo, Jan 11 '13 at 19:15
What are the start index and end index? Walk us through the current example. — Srinivas, Jan 11 '13 at 19:16
It is a 1d array, visualizing the solution as spiral order and the start index would be 6 and end index would be 18. — gizgok, Jan 11 '13 at 19:19
Are the array always odd numbered? If so, it's pretty straight forward math to get the indices of 1,4 and 7 in the particular case. — Srinivas, Jan 11 '13 at 19:19
But what about the example where you bigger matrix is of size 4X4 and the smaller one is 3X3? — Srinivas, Jan 11 '13 at 19:23
the 3x3 is zero padded same I can take 2x3 and zero pad it to get 4x5 — gizgok, Jan 11 '13 at 19:28
If you want to print 25 numbers, I think that's 25 "operations" no matter what order you do it in (plus a few for the formatting...). It might help if we knew what it meant to "do this"... — twalberg, Jan 11 '13 at 19:28
What is your desired output? For "Spiral", I'd assume `123698745`. But you say the end index is 18... Do you want `123654789`? — AShelly, Jan 11 '13 at 19:37
I meant the index which has the last element in the input array. The traversal would be the output and hence your first assumption is accurate. — gizgok, Jan 11 '13 at 19:39

score 0 · Answer 1 · answered Jan 11 '13 at 19:29

Given your 5x5 matrix assuming a zero index base you know the row indices are:
0,1,2,3,4
5,6,7,8,9
10,11,12,13,14
15,16,17,18,19
20,21,22,23,24

you know your first index is 6 and the last is 18. So as a starting point you know you can eliminate the following pieces of the matrix:

0,1,2,3,4
and
19,20,21,22,23,24,25

this counts as 2 operations.

you also know that since you are starting at index 6 and it was a 3x3 you only need to go to index 8, this is one operation.

you then need to add 5 to your previous index of 6 this yields 11 and proceed again (2 operations in total) current operation count is 5)

do this again with 11 and you get 16 one operation. Get 2 more operations and you end up with 18. This is now 8 operations in total.

score 0 · Answer 2 · answered Jan 11 '13 at 19:57

I'd do something like this:

   POINT ul = (start_idx/width, start_idx%width);
   POINT br = (end_idx/width, end_idx%width);
   POINT p = ul
   dir = RIGHT;
   while (ul != br)
     visit(ARRAY[p.x+p.y*WIDTH])
     case dir
        when RIGHT:   
           p.x+=1
           if (p.x==br.x) 
             dir = DOWN
             ul.y++;
         when DOWN
           p.y+=1
           if (p.y==br.y) 
             dir = LEFT
             br.x--;
         when LEFT: 
            //like RIGHT but -1 and adjust br.y upwards when done
         when UP:
            //like DOWN but -1 and adjust ul.x rightward when done
    endwhile

The idea is to keep track of the virtual x and y to visit. Move the point to visit along the sides of the box defined by the start and end points. And adjust the sides inwards as you complete the visits.

How to perform spiral order traversalin one dimensional array?

2 Answers2