0

Suppose I have the following matrix with values 1-25 as input to my program.

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

The inward spiral should give me the output 13 18 17 12 7 8 9 14 19 24 23 22 21 16 11 6 1 2 3 4 5 10 15 20 25. What could be the logic behind such a program? I tried to start off with the center of the matrix and then increasing the row and column to be traversed at every iteration, but I am kinda stuck here.

1
  • This is actually an interview question I've been asked... I believe a part of the trick is in recognizing the screen as concentric rectangles where the circumference has a measurable change per rectangle, so you can easily pick apart the array into those rectangles after divining the circumference change, then fitting an array to x,y coords for a single rectangle is easier. All programming can be solved by divide and conquor: Recursively break things down into smaller and smaller problems until the only things left are obvious and easy to solve. Mar 6, 2015 at 2:51

1 Answer 1

4

The part that is being repeated is this "square loop" pattern (read this from a to p):

h i j k l
g       m
f       n
e       o
d c b a p

(Here I've shown a square loop of width 5.)

The core of the solution lies in figuring out how to describe this pattern programmatically. This itself is composed of 4 strips that differ in the starting point and increment: a to d, e to h, i to l, and m to p. In this example, the a to d strip has starting point (4, 5) and increment (-1, 0). The other strips are analogous.

The completely solution involves repeating this pattern with increasing size until the entire square is covered. You start with the center piece, followed by a square loop of width 3, followed by another square loop of width 5, etc.

Depending on what coordinate system you use, you may have to deal with some offset that depends on the size of the full grid.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.