Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Problem: Printing a 2D array in spiral like shape

array printing

  • Please log in to reply
1 reply to this topic

#1 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 417 posts

Posted 19 June 2011 - 01:38 AM

Given a 2D array, print all elements in spiral order.

This is a simple, famous, coding interview problem which is hard to get right in code.

A similar problem has been asked in the forums earlier which can be solved by making a slight change to this code.
http://forum.codecal...ike-spiral.html

To begin with, we need to be clear on requirements. If the 2D array is as follows

1, 2, 3
4, 5, 6
7, 8, 9

Then we would want to print it like 1 2 3 6 9 8 7 4 5. This is going first towards right in the array, then to bottom, then left and finally upwards. This procedure is repeated until all elements are visited. Although spiral can be chosen in multiple ways i.e. it can go down first, then right and so on OR it can start from the center of the array and grow outwards. However, the one chosen above is most intuitive since generally we read arrays row wise starting from 0,0 index.

So we are basically starting from the outer most spiral or rectangle and move towards the center. To achieve this we would need one loop running from outer most spiral to the inner most one. We call it level (level would start from 0 and would go on increasing once each iteration (rectangle) is completed.

And of course the solution should be generic and applicable to NXN sized array.

Inside the level loop, we will need one loop for each direction which keeps incrementing a variable for each direction.

I have tested it on 3X3, 4X4 and 5X5 arrays. Code follows:

#include<iostream>
using namespace std;

#define ROWS 5//3
#define COLS 5//3

int main()
{
    int arr[ROWS][COLS] = /*{{1,2,3},
                           {4,5,6},
                           {7,8,9}};*/

                           {{ 1, 2, 3, 4, 17},
                            { 5, 6, 7, 8, 18},
                            { 9,10,11,12, 19},
                            {13,14,15,16, 20},
                            {21,22,23,24, 25}};

    // Four direction counters of current movement
    // Horizontal right, vertical bottom, horizontal left and vertical top respectively
    int hr, vb, hl, vt;

    // levl indicates current depth of our imaginary rectangle into array. Starting value is zero
    // since we are looping on the boundaries and ending value is the inner most rectangle
    int levl;
    for (levl=0; levl < COLS-levl; levl++)
    {
        for(hr=levl; hr < COLS-levl; hr++)   // go right
            cout << arr[levl][hr] << " ";

        for(vb=levl+1; vb < COLS-levl; vb++) // go down
            cout << arr[vb][hr-1] << " ";

        for(hl=vb-1; hl-1 >= levl; hl--)  // go left
            cout << arr[vb-1][hl-1] << " ";

        for(vt=vb-1; vt-1 > levl; vt--)  // go up
            cout << arr[vt-1][hl] << " ";
    }

    cout << endl;
    return 0;
}

And here is the output on a 5X5 run.
ArrayinSpiral.jpg

Since we go through each element of the array exactly once so it’s running time complexity is exactly n^2 or rows X columns.
  • 0
Today is the first day of the rest of my life

#2 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 417 posts

Posted 14 July 2011 - 10:45 AM

Here is a follow up slight modification of the above problem

http://forum.codecal...ard-center.html
  • 0
Today is the first day of the rest of my life





Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download