How to get a quadratic array of squares in a spiral!

1.First of all

Nice to meet everyone! I'm Monabo, who is majoring in software engineering at university.

Before reading, we want our readers to read ideas rather than code.

Suddenly, have you ever been confused by the flow of arrays? I understand that much! You may be confused, but please read a little more.

So, do you know how to move an array of squares in a spiral with a pointer?

I will explain in detail.

Main subject

Suppose you have a quadratic array of squares. Example.)

array_traversal.py

array = [
    [1, 2, 3, 4]
    [12, 13, 14, 5]
    [11, 16, 15, 6]
    [10, 9, 8, 7]
]

Get the primary array by crossing each element in a spiral of this vertical x horizontal quadratic array. (Time complexity is O (n))

Output example

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Way of thinking

First of all, from the way of thinking.

1. Let's change the viewpoint a little

First image:

It may be easier to understand if you look at 1st image. Although it is acquired in a spiral shape, if you try to tackle the problem from a slightly different perspective there It can be divided into an outer square and an inner square.

Looking at it that way, the complexity has disappeared a little. Right?

Next, to bypass this square, think of it as having two pointers (for rows and columns) . Think of the pointer here as simply telling the computer "Do this process here!" To direct the process.

There is one point to consider in order to get these two pointers in a spiral. It is control of double counting .

Supplement: Here, row refers to rows and columns refer to columns. To put it simply, double counting is the same factor in processing.

2. Control of double counting

Please see the following image.

Second:

By doing this, you can create boundaries between each other and prevent double counting , so I think it will be an efficient solution.

• What are SC, EC, SR, ER? ?? SC is the beginning of the column, EC is the end of the column SR is the beginning of row, ER is the end of row It has become.

3. A series of processing flow (outside)

Now, let's explain the flow when we are finally ready.

3.1 Get the top row ([1, 2, 3, 4]) with the pointer for the column

You can do this with the usual for loop method.

Sample code:

python

   for col in range(sc, ec + 1):
       result.append(array[sr][col])

3.2 Get the column pointed to by EC with the pointer for row to ER. (Here, [5, 6, 7].)

Sample code:

python

   for row in range(sr + 1, er + 1):
       result.append(array[row][ec])

3.3 Get the bottom row ([10, 9, 8]) in the opposite direction with the pointer for the column.

Sample code:

python

   for col in reversed(range(sc, ec)):
       result.append(array[er][col])

3.4 Finally, I want to get [12] on the 2nd line and [11] on the 3rd line, so I get them with the pointer for row in the opposite direction in the SR + 1 ~ ER section.

Sample code:

python

   for row in reversed(range(sr + 1, er)):
       result.append(array[row][sr])

With this, I finally got all the elements of the outer square in a spiral shape.

4. A series of processing flow (inside)

Next is the inner square. However, if you continue to process in the same way, it will become hard coding, right?

So, add one SR and SC and move them inward. Also, by adding one EC and one ER and moving them inward, you can reuse the ones made in 1-5! It's ECO ~ lol

#Processing of inner squares
sr += 1 
er -= 1
sc += 1
ec -= 1		

def spiralTraverse(array):
	result = []
	sr, er = 0, len(array) - 1
	sc, ec = 0, len(array[0]) - 1
	
	while sr <= er and sc <= ec:
		for col in range(sc, ec + 1):
			result.append(array[sr][col])
			
		for row in range(sr + 1, er + 1):
			result.append(array[row][ec])
			
		for col in reversed(range(sc, ec)):
			result.append(array[er][col])
			
		for row in reversed(range(sr + 1, er)):
			result.append(array[row][sr])
			
		sr += 1 
		er -= 1
		sc += 1
		ec -= 1
		
	return result