Print a given matrix in spiral form

 Problem

Given a 2D array, print it in spiral form.

Input:  {{1,    2,   3,   4},

              {5,    6,   7,   8},

             {9,   10,  11,  12},

            {13,  14,  15,  16 }}

Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 

Explanation: The output is a matrix in a spiral format. 

Input: { {1,   2,   3,   4,  5,   6},

           {7,   8,   9,  10,  11,  12},

          {13,  14,  15, 16,  17,  18}}

Expected output:

1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11

Explanation: The output is a matrix in a spiral format.

First, I considered solving this problem by defining the prescriptive rule on which direction to go and how much to go by observing the sample problem. However, I found that the code gets overly complicated if we go that path. 

I decided to think of this problem as the DPS problem where we search through the matrix in a specified direction until we reach the end before switching direction.

This made the problem much easier and I don't have to think about the corner case much.

This can be solved in $O(N * M)$ where N is the width of the matrix and M is the height of the matrix.

UPDATE (2023-03-03): solution in python

	'''
	Given a 2D array, print it in spiral form.
	Input: {{1, 2, 3, 4},
	{5, 6, 7, 8},
	{9, 10, 11, 12},
	{13, 14, 15, 16 }}
	Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
	'''
	dir_sequence = [0, 1, 2, 3] # 0: right, 1: down, left: 2, left : 3
	class Pos:
	def __init__(self, x, y):
	self.x = x
	self.y = y
	def get_next_dir(cur_dir, dir_sequence):
	return cur_dir + 1 if cur_dir + 1 < len(dir_sequence) else 0
	def get_next_pos(cur_pos, dir):
	next_x = cur_pos.x
	next_y = cur_pos.y
	# right
	if dir == 0:
	next_x +=1
	# doown
	elif dir == 1:
	next_y += 1
	# left
	elif dir == 2:
	next_x -= 1
	# up
	elif dir == 3:
	next_y -= 1
	else:
	raise Exception("invaild direction. {}".format(dir))
	return Pos(next_x, next_y)
	def can_move(cur_pos, dir, visited, max_pos):
	next_pos = get_next_pos(cur_pos, dir)
	if 0 <= next_pos.x and next_pos.x <= max_pos.x and 0 <= next_pos.y and next_pos.y <= max_pos.y:
	return visited[next_pos.y][next_pos.x] == False
	return False
	def dfs(cur_pos, max_pos, direction, visited, input):
	# first print out the current pos
	print(input[cur_pos.y][cur_pos.x], end=" ")
	visited[cur_pos.y][cur_pos.x] = True
	next_dir = direction
	if can_move(cur_pos=cur_pos, dir=direction, visited=visited, max_pos=max_pos) != True:
	next_dir = get_next_dir(cur_dir=direction, dir_sequence=dir_sequence)
	if can_move(cur_pos=cur_pos, dir=next_dir, visited=visited, max_pos=max_pos) != True:
	return
	next_pos = get_next_pos(cur_pos=cur_pos, dir=next_dir)
	dfs(cur_pos=next_pos, max_pos=max_pos, direction=next_dir, visited=visited, input=input)
	def print_spiral(width, height, input):
	visited = [[ False for i in range(width)] for j in range(height)]
	initial_pos = Pos(0, 0)
	max_pos = Pos(width - 1, height - 1)
	initial_dir = 0
	dfs(initial_pos, max_pos, initial_dir, visited, input)
	# test cases
	input= [
	[1, 2, 3, 4],
	[5, 6, 7, 8],
	[9, 10, 11, 12],
	[13, 14, 15, 16]
	]
	print_spiral(4, 4, input)
	# expected output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

view raw google_spiral_print.py hosted with ❤ by GitHub

Practice statistics:

15 mins: to come up with the algorithm

28 mins: to write the code and review the code.