Given a matrix of size N x M. You have to find the K^{th} element which will obtain while traversing the matrix spirally starting from the top-left corner of the matrix.
Example 1:
Input: 
N = 3, M = 3, K = 4
A[] = {{1, 2, 3}, 
       {4, 5, 6}, 
       {7, 8, 9}}
Output: 
6
Explanation: Spiral traversal of matrix: 
{1, 2, 3, 6, 9, 8, 7, 4, 5}. Fourth element
is 6.
Example 2:
Input: 
N = 2, M = 2, K = 2 
A[] = {{1, 2},
       {3, 4}} 
Output: 
2
Explanation: Spiral traversal of matrix: 
{1, 2, 4, 3}. Second element is 2.
Your Task:  
You don't need to read input or print anything. Complete the function findK() which takes the matrix A[ ][ ], number of rows N, number of columns M, and integer K as input parameters and returns the K^{th} element in the spiral traversal of the matrix.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ K ≤ N*M ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Constructive algorithms

Starter code: #User function Template for python3

# You are required to complete this fucntion
# Function should return an integer
class Solution:
    def findK(self, a, n, m, k):
        # Your code goes here


Solutions:
class Solution:

	def findK(self, a, n, m, k):
		left = 0
		top = 0
		right = m - 1
		bottom = n - 1
		while left <= right and top <= bottom:
			for i in range(left, right + 1):
				k -= 1
				if k == 0:
					return a[top][i]
			top += 1
			for i in range(top, bottom + 1):
				k -= 1
				if k == 0:
					return a[i][right]
			right -= 1
			for i in range(right, left - 1, -1):
				k -= 1
				if k == 0:
					return a[bottom][i]
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				k -= 1
				if k == 0:
					return a[i][left]
			left += 1
		return 0


class Solution:

	def findK(self, a, n, m, k):
		l = []
		left = 0
		top = 0
		right = len(a[0])
		bottom = len(a)
		while left < right and top < bottom:
			for i in range(left, right):
				l.append(a[top][i])
			top += 1
			for i in range(top, bottom):
				l.append(a[i][right - 1])
			right -= 1
			if not (left < right and top < bottom):
				break
			for i in range(right - 1, left - 1, -1):
				l.append(a[bottom - 1][i])
			bottom -= 1
			for i in range(bottom - 1, top - 1, -1):
				l.append(a[i][left])
			left += 1
		return l[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		left = 0
		bottom = n - 1
		up = 0
		right = m - 1
		answer = []
		while left <= right and up <= bottom:
			for i in range(left, right + 1):
				answer.append(a[up][i])
			up += 1
			for i in range(up, bottom + 1):
				answer.append(a[i][right])
			right -= 1
			for i in range(right, left - 1, -1):
				answer.append(a[bottom][i])
			bottom -= 1
			for i in range(bottom, up - 1, -1):
				answer.append(a[i][left])
			left += 1
		return answer[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		(top, bottom, right, left) = (0, n - 1, m - 1, 0)
		res = []
		c = 0
		while len(res) < m * n:
			for i in range(left, right + 1):
				res.append(a[top][i])
				c += 1
				if c == k:
					return res[-1]
			top += 1
			for i in range(top, bottom + 1):
				res.append(a[i][right])
				c += 1
				if c == k:
					return res[-1]
			right -= 1
			if top <= bottom:
				for i in range(right, left - 1, -1):
					res.append(a[bottom][i])
					c += 1
					if c == k:
						return res[-1]
				bottom -= 1
			if left <= right:
				for i in range(bottom, top - 1, -1):
					res.append(a[i][left])
					c += 1
					if c == k:
						return res[-1]
				left += 1
		return res[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		matrix = a
		(top, bottom) = (0, n - 1)
		(left, right) = (0, m - 1)
		ans = []
		while top <= bottom and left <= right:
			if len(ans) < n * m:
				for i in range(left, right + 1):
					ans.append(matrix[top][i])
				top += 1
			if len(ans) < n * m:
				for i in range(top, bottom + 1):
					ans.append(matrix[i][right])
				right -= 1
			if len(ans) < n * m:
				for i in reversed(range(left, right + 1)):
					ans.append(matrix[bottom][i])
				bottom -= 1
			if len(ans) < n * m:
				for i in reversed(range(top, bottom + 1)):
					ans.append(matrix[i][left])
				left += 1
		return ans[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		m = len(matrix[0])
		n = len(matrix)
		left = 0
		right = m - 1
		top = 0
		bottom = n - 1
		d = 0
		new = []
		while top <= bottom and left <= right:
			if d == 0:
				for i in range(left, right + 1):
					new.append(matrix[top][i])
				top += 1
				d = 1
			elif d == 1:
				for i in range(top, bottom + 1):
					new.append(matrix[i][right])
				right -= 1
				d = 2
			elif d == 2:
				for i in range(right, left - 1, -1):
					new.append(matrix[bottom][i])
				bottom -= 1
				d = 3
			elif d == 3:
				for i in range(bottom, top - 1, -1):
					new.append(matrix[i][left])
				left += 1
				d = 0
		return new[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		t = 0
		b = n - 1
		l = 0
		r = m - 1
		k -= 1
		while t <= b and l <= r:
			for _ in range(l, r + 1):
				if k == 0:
					return a[t][_]
				k -= 1
			t += 1
			for _ in range(t, b + 1):
				if k == 0:
					return a[_][r]
				k -= 1
			r -= 1
			if l <= r:
				for _ in range(r, l - 1, -1):
					if k == 0:
						return a[b][_]
					k -= 1
				b -= 1
			if t <= b:
				for _ in range(b, t - 1, -1):
					if k == 0:
						return a[_][l]
					k -= 1
				l += 1


class Solution:

	def findK(self, a, n, m, k):
		val = 1
		(left, right) = (0, len(a[0]) - 1)
		(top, bottom) = (0, len(a) - 1)
		while left <= right and top <= bottom:
			for c in range(left, right + 1):
				if val == k:
					return a[top][c]
				val += 1
			top += 1
			for r in range(top, bottom + 1):
				if val == k:
					return a[r][right]
				val += 1
			right -= 1
			for c in range(right, left - 1, -1):
				if val == k:
					return a[bottom][c]
				val += 1
			bottom -= 1
			for r in range(bottom, top - 1, -1):
				if val == k:
					return a[r][left]
				val += 1
			left += 1


class Solution:

	def findK(self, a, n, m, k):
		start_row = 0
		start_col = 0
		end_row = n - 1
		end_col = m - 1
		t = 1
		while start_row <= end_row and start_col <= end_col:
			for i in range(start_col, end_col + 1):
				if t == k:
					return a[start_row][i]
				t += 1
			start_row += 1
			for i in range(start_row, end_row + 1):
				if t == k:
					return a[i][end_col]
				t += 1
			end_col -= 1
			if start_col <= end_col:
				for i in range(end_col, start_col - 1, -1):
					if t == k:
						return a[end_row][i]
					t += 1
				end_row -= 1
			if start_row <= end_row:
				for i in range(end_row, start_row - 1, -1):
					if t == k:
						return a[i][start_col]
					t += 1
				start_col += 1


class Solution:

	def findK(self, a, n, m, k):
		result = []
		r = n
		c = m
		row_min = 0
		col_min = 0
		row_max = r - 1
		col_max = c - 1
		i = 0
		j = 0
		while True:
			for j in range(col_min, col_max + 1):
				result.append(matrix[i][j])
			if len(result) == r * c:
				break
			for i in range(row_min + 1, row_max + 1):
				result.append(matrix[i][j])
			if len(result) == r * c:
				break
			for j in range(col_max - 1, col_min - 1, -1):
				result.append(matrix[i][j])
			if len(result) == r * c:
				break
			for i in range(row_max - 1, row_min, -1):
				result.append(matrix[i][j])
			if len(result) == r * c:
				break
			row_max -= 1
			col_max -= 1
			row_min += 1
			col_min += 1
		return result[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		ans = []

		def printdata(arr, i, j, m, n):
			if i >= m or j >= n:
				return
			for p in range(i, n):
				ans.append(arr[i][p])
			for p in range(i + 1, m):
				ans.append(arr[p][n - 1])
			if m - 1 != i:
				for p in range(n - 2, j - 1, -1):
					ans.append(arr[m - 1][p])
			if n - 1 != j:
				for p in range(m - 2, i, -1):
					ans.append(arr[p][j])
			printdata(arr, i + 1, j + 1, m - 1, n - 1)
		printdata(a, 0, 0, n, m)
		return ans[k - 1]


class Solution(object):

	def findK(self, matrix, n, m, k):
		(rows, cols) = (len(matrix), len(matrix[0]))
		(top, bottom) = (0, rows - 1)
		(left, right) = (0, cols - 1)
		count = 0
		while top <= bottom and left <= right:
			for col in range(left, right + 1):
				count += 1
				if count == k:
					return matrix[top][col]
			for row in range(top + 1, bottom + 1):
				count += 1
				if count == k:
					return matrix[row][right]
			if top <= bottom:
				for col in range(right - 1, left - 1, -1):
					count += 1
					if count == k:
						return matrix[bottom][col]
			if left <= right:
				for row in range(bottom - 1, top, -1):
					count += 1
					if count == k:
						return matrix[row][left]
			left += 1
			right -= 1
			top += 1
			bottom -= 1


class Solution:

	def findK(self, mat, n, m, k):
		ans = []
		top = 0
		left = 0
		bottom = n - 1
		right = m - 1
		while top <= bottom and left <= right:
			for i in range(left, right + 1):
				ans.append(mat[top][i])
			top += 1
			for i in range(top, bottom + 1):
				ans.append(mat[i][right])
			right -= 1
			if top <= bottom:
				for i in range(right, left - 1, -1):
					ans.append(mat[bottom][i])
				bottom -= 1
			if left <= right:
				for i in range(bottom, top - 1, -1):
					ans.append(mat[i][left])
				left += 1
		return ans[k - 1]


class Solution:

	def findK(self, nums, n, m, k):
		(top, down, left, right) = (0, len(matrix) - 1, 0, len(matrix[0]) - 1)
		(direc, arr) = (0, [])
		while top <= down and left <= right:
			if direc == 0:
				for i in range(left, right + 1):
					arr.append(matrix[top][i])
				top += 1
			elif direc == 1:
				for i in range(top, down + 1):
					arr.append(matrix[i][right])
				right -= 1
			elif direc == 2:
				for i in range(right, left - 1, -1):
					arr.append(matrix[down][i])
				down -= 1
			else:
				for i in range(down, top - 1, -1):
					arr.append(matrix[i][left])
				left += 1
			direc = (direc + 1) % 4
		return arr[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		left = 0
		right = m - 1
		top = 0
		bottom = n - 1
		li = []
		count = 0
		while count <= k and left <= right and (top <= bottom):
			for i in range(left, right + 1):
				li.append(a[top][i])
				count += 1
			top += 1
			for i in range(top, bottom + 1):
				li.append(a[i][right])
				count += 1
			right -= 1
			for i in range(right, left - 1, -1):
				li.append(a[bottom][i])
				count += 1
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				li.append(a[i][left])
				count += 1
			left += 1
		return li[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		(row_s, row_e) = (0, n)
		(col_s, col_e) = (0, m)
		count = 1
		while row_s < row_e and col_s < col_e:
			for col in range(col_s, col_e):
				if count == k:
					return a[row_s][col]
				count += 1
			row_s += 1
			for row in range(row_s, row_e):
				if count == k:
					return a[row][col_e - 1]
				count += 1
			col_e -= 1
			if row_s < row_e:
				for col in range(col_e - 1, col_s - 1, -1):
					if count == k:
						return a[row_e - 1][col]
					count += 1
				row_e -= 1
			if col_s < col_e:
				for row in range(row_e - 1, row_s - 1, -1):
					if count == k:
						return a[row][col_s]
					count += 1
				col_s += 1


class Solution:

	def findK(self, mat, n, m, k):
		row_start = 0
		row_end = len(matrix) - 1
		col_start = 0
		col_end = len(matrix[0]) - 1
		while row_start <= row_end and col_start <= col_end:
			for i in range(col_start, col_end + 1):
				k -= 1
				if k == 0:
					return matrix[row_start][i]
			row_start += 1
			for i in range(row_start, row_end + 1):
				k -= 1
				if k == 0:
					return matrix[i][col_end]
			col_end -= 1
			for i in range(col_end, col_start - 1, -1):
				k -= 1
				if k == 0:
					return matrix[row_end][i]
			row_end -= 1
			for i in range(row_end, row_start - 1, -1):
				k -= 1
				if k == 0:
					return matrix[i][col_start]
			col_start += 1
		return None


class Solution:

	def findK(self, a, n, m, k):
		top = 0
		arr = []
		bottom = n - 1
		left = 0
		right = m - 1
		count = 1
		while left <= right and top <= bottom:
			for i in range(left, right + 1):
				if count == k:
					return matrix[top][i]
				count += 1
			top += 1
			for i in range(top, bottom + 1):
				if count == k:
					return matrix[i][right]
				count += 1
			right -= 1
			if top <= bottom:
				for i in range(right, left - 1, -1):
					if count == k:
						return matrix[bottom][i]
					count += 1
				bottom -= 1
			else:
				break
			if left <= right:
				for i in range(bottom, top - 1, -1):
					if count == k:
						return matrix[i][left]
					count += 1
				left += 1
			else:
				break
		return -1


class Solution:

	def findK(self, a, n, m, k):
		i = 0
		j = 0
		n1 = 0
		m1 = 0
		l = 1
		while l <= k:
			i = n1
			j = m1
			while j < m:
				if l == k:
					return a[i][j]
					print(i, j)
				l = l + 1
				j += 1
			n1 += 1
			i += 1
			while i < n:
				if l == k:
					return a[i][m - 1]
				l += 1
				i += 1
			m -= 1
			j = m - 1
			while j >= m1:
				if l == k:
					return a[n - 1][j]
				j -= 1
				l += 1
			n -= 1
			i = n - 1
			while i >= n1:
				if l == k:
					return a[i][m1]
				i -= 1
				l += 1
			m1 += 1


class Solution:

	def findK(self, arr, n, m, k):
		row_start = 0
		row_end = n - 1
		col_start = 0
		col_end = m - 1
		count = 0
		ans = 0
		while count < n * m:
			i = col_start
			while i <= col_end and k > 0:
				ans = arr[row_start][i]
				k -= 1
				i += 1
				count += 1
			row_start += 1
			i = row_start
			while i <= row_end and k > 0:
				ans = arr[i][col_end]
				k -= 1
				i += 1
				count += 1
			col_end -= 1
			i = col_end
			while i >= col_start and k > 0:
				ans = arr[row_end][i]
				k -= 1
				i -= 1
				count += 1
			row_end -= 1
			i = row_end
			while i >= row_start and k > 0:
				ans = arr[i][col_start]
				k -= 1
				i -= 1
				count += 1
			col_start += 1
			if k == 0:
				break
		return ans


class Solution:

	def findK(self, matrix, n, m, k):
		l = 0
		r = m - 1
		u = 0
		d = n - 1
		i = 0
		res = []
		k -= 1
		while l <= r and u <= d:
			for i in range(l, r + 1):
				if k == 0:
					return matrix[u][i]
				k -= 1
			u += 1
			for i in range(u, d + 1):
				if k == 0:
					return matrix[i][r]
				k -= 1
			r -= 1
			for i in range(r, l - 1, -1):
				if k == 0:
					return matrix[d][i]
				k -= 1
			d -= 1
			for i in range(d, u - 1, -1):
				if k == 0:
					return matrix[i][l]
				k -= 1
			l += 1
		return -1


class Solution:

	def findK(self, a, n, m, k):
		i = 0
		j = 0
		ele = -1
		top = 1
		left = 0
		bottom = n - 1
		right = m - 1
		while True:
			flag = 0
			while j <= right:
				k -= 1
				flag = 1
				if k == 0:
					return a[i][j]
				j += 1
			j -= 1
			i += 1
			right -= 1
			while i <= bottom:
				k -= 1
				flag = 1
				if k == 0:
					return a[i][j]
				i += 1
			i -= 1
			j -= 1
			bottom -= 1
			while j >= left:
				k -= 1
				flag = 1
				if k == 0:
					return a[i][j]
				j -= 1
			j += 1
			i -= 1
			left += 1
			while i >= top:
				k -= 1
				flag = 1
				if k == 0:
					return a[i][j]
				i -= 1
			i += 1
			j += 1
			top += 1
			if flag == 0:
				break
		return -1


class Solution:

	def findK(self, a, n, m, k):
		(top, down, left, right) = (0, n - 1, 0, m - 1)
		direc = 0
		result = []
		while top <= down and left <= right:
			if direc == 0:
				for i in range(left, right + 1):
					result.append(a[top][i])
				top += 1
			elif direc == 1:
				for i in range(top, down + 1):
					result.append(a[i][right])
				right -= 1
			elif direc == 2:
				for i in range(right, left - 1, -1):
					result.append(a[down][i])
				down -= 1
			elif direc == 3:
				for i in range(down, top - 1, -1):
					result.append(a[i][left])
				left += 1
			direc = (direc + 1) % 4
		return result[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		top = left = 0
		down = len(a) - 1
		right = len(a[0]) - 1
		d = 0
		lst = []
		index = 0
		while left <= right and top <= down:
			if d == 0:
				for i in range(left, right + 1):
					index += 1
					if index == k:
						return a[top][i]
				top += 1
			elif d == 1:
				for i in range(top, down + 1):
					index += 1
					if index == k:
						return a[i][right]
				right -= 1
			elif d == 2:
				for i in range(right, left - 1, -1):
					index += 1
					if index == k:
						return a[down][i]
				down -= 1
			elif d == 3:
				for i in range(down, top - 1, -1):
					index += 1
					if index == k:
						return a[i][left]
				left += 1
			d = (d + 1) % 4


class Solution:

	def findK(self, a, n, m, k):
		(x, y) = (0, 0)
		dx = [0, 1, 0, -1]
		dy = [1, 0, -1, 0]
		dr = 0
		(min_c, max_c) = (0, m - 1)
		(min_r, max_r) = (0, n - 1)
		while k > 0:
			k -= 1
			if k == 0:
				return a[x][y]
			if x + dx[dr] > max_r:
				dr = (dr + 1) % 4
				max_c -= 1
			elif x + dx[dr] < min_r:
				dr = (dr + 1) % 4
				min_c += 1
			elif y + dy[dr] > max_c:
				dr = (dr + 1) % 4
				min_r += 1
			elif y + dy[dr] < min_c:
				dr = (dr + 1) % 4
				max_r -= 1
			x += dx[dr]
			y += dy[dr]
		return -1


class Solution:

	def findK(self, a, n, m, k):
		i = 0
		j = 0
		left = 0
		right = m - 1
		top = 0
		bottom = n - 1
		arr = []
		dir = 0
		while left <= right and top <= bottom:
			if dir == 0:
				for i in range(left, right + 1):
					arr.append(a[top][i])
				top += 1
			if dir == 1:
				for i in range(top, bottom + 1):
					arr.append(a[i][right])
				right -= 1
			if dir == 2:
				for i in range(right, left - 1, -1):
					arr.append(a[bottom][i])
				bottom -= 1
			if dir == 3:
				for i in range(bottom, top - 1, -1):
					arr.append(a[i][left])
				left += 1
			dir = (dir + 1) % 4
		return arr[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		res = []
		l = 0
		r = m - 1
		t = 0
		b = n - 1
		while l <= r and t <= b:
			for i in range(l, r + 1):
				res.append(a[t][i])
			t += 1
			for i in range(t, b + 1):
				res.append(a[i][r])
			r -= 1
			if not (t <= b and l <= r):
				break
			for i in range(r, l - 1, -1):
				res.append(a[b][i])
			b -= 1
			for i in range(b, t - 1, -1):
				res.append(a[i][l])
			l += 1
		return res[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		temp = []
		(left, top) = (0, 0)
		(right, bottom) = (m - 1, n - 1)
		while top <= bottom and left <= right:
			for i in range(left, right + 1):
				temp.append(a[top][i])
			top += 1
			for j in range(top, bottom + 1):
				temp.append(a[j][right])
			right -= 1
			if top <= bottom:
				for x in range(right, left - 1, -1):
					temp.append(a[bottom][x])
				bottom -= 1
			if left <= right:
				for y in range(bottom, top - 1, -1):
					temp.append(a[y][left])
				left += 1
		return temp[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		count = 0
		up = 0
		down = n - 1
		left = 0
		right = m - 1
		list = []
		direction = 0
		while up <= down and left <= right:
			if direction == 0:
				for i in range(left, right + 1):
					count += 1
					if count == k:
						return a[up][i]
				up += 1
			if direction == 1:
				for i in range(up, down + 1):
					count += 1
					if count == k:
						return a[i][right]
				right -= 1
			if direction == 2:
				for i in range(right, left - 1, -1):
					count += 1
					if count == k:
						return a[down][i]
				down -= 1
			if direction == 3:
				for i in range(down, up - 1, -1):
					count += 1
					if count == k:
						return a[i][left]
				left += 1
			direction = (direction + 1) % 4
		return -1


class Solution:

	def findK(self, a, n, m, k):
		rows = len(a)
		cols = len(a[0])
		left = 0
		right = cols - 1
		top = 0
		bottom = rows - 1
		count = 0
		totalItem = rows * cols
		res = []
		while count < totalItem:
			for i in range(left, right + 1):
				res.append(a[left][i])
				count += 1
			top += 1
			if count < totalItem:
				for i in range(top, bottom + 1):
					res.append(a[i][right])
					count += 1
				right -= 1
			if count < totalItem:
				for i in range(right, left - 1, -1):
					res.append(a[bottom][i])
					count += 1
				bottom -= 1
			if count < totalItem:
				for i in range(bottom, top - 1, -1):
					res.append(a[i][left])
					count += 1
				left += 1
		return res[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		up = 0
		left = 0
		right = m - 1
		down = n - 1
		lis = []
		while len(lis) < n * m:
			for i in range(left, right + 1):
				lis.append(a[up][i])
			if len(lis) < n * m:
				up += 1
				for i in range(up, down + 1):
					lis.append(a[i][right])
			if len(lis) < n * m:
				right -= 1
				for i in range(right, left - 1, -1):
					lis.append(a[down][i])
			if len(lis) < n * m:
				down -= 1
				for i in range(down, up - 1, -1):
					lis.append(a[i][left])
			left += 1
		ans = lis[k - 1]
		return ans


class Solution:

	def findK(self, a, n, m, k):
		left = 0
		right = m - 1
		top = 0
		bottom = n - 1
		dire = 0
		res = []
		while left <= right and top <= bottom:
			if dire == 0:
				for i in range(left, right + 1):
					res.append(a[top][i])
				top = top + 1
				dire = dire + 1
			elif dire == 1:
				for i in range(top, bottom + 1):
					res.append(a[i][right])
				right = right - 1
				dire = dire + 1
			elif dire == 2:
				for i in range(right, left - 1, -1):
					res.append(a[bottom][i])
				bottom = bottom - 1
				dire = dire + 1
			elif dire == 3:
				for i in range(bottom, top - 1, -1):
					res.append(a[i][left])
				left = left + 1
				dire = dire + 1
			if dire == 4:
				dire = 0
		return res[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		traverse = []
		l = 0
		r = m - 1
		u = 0
		d = n - 1
		while l <= r and u <= d:
			for i in range(l, r + 1):
				traverse.append(matrix[u][i])
			u += 1
			for i in range(u, d + 1):
				traverse.append(matrix[i][r])
			r -= 1
			for i in range(r, l - 1, -1):
				traverse.append(matrix[d][i])
			d -= 1
			for i in range(d, u - 1, -1):
				traverse.append(matrix[i][l])
			l += 1
		return traverse[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		top = 0
		left = 0
		down = n - 1
		right = m - 1
		count = 0
		while top <= down or left <= right:
			x = top
			y = left
			while y <= right:
				count += 1
				if count == k:
					return a[x][y]
				y += 1
			top += 1
			x = top
			y = right
			while x <= down:
				count += 1
				if count == k:
					return a[x][y]
				x += 1
			right -= 1
			y = right
			x = down
			while y >= left:
				count += 1
				if count == k:
					return a[x][y]
				y -= 1
			down -= 1
			x = down
			y = left
			while x >= top:
				count += 1
				if count == k:
					return a[x][y]
				x -= 1
			left += 1
		return -1


class Solution:

	def findK(self, a, n, m, k):
		r = 0
		c = 0
		ans = []
		while r < n and c < m:
			for i in range(c, m):
				ans.append(a[r][i])
			r += 1
			for i in range(r, n):
				ans.append(a[i][m - 1])
			m -= 1
			if r < n:
				for i in range(m - 1, c - 1, -1):
					ans.append(a[n - 1][i])
				n -= 1
			if c < m:
				for i in range(n - 1, r - 1, -1):
					ans.append(a[i][c])
				c += 1
		return ans[k - 1]


class Solution:

	def findK(self, matrix, n, m, k):
		(m, ml) = (len(matrix) - 1, 0)
		(n, nl) = (len(matrix[0]) - 1, 0)
		while m >= ml and n >= nl:
			for col in range(nl, n + 1):
				k -= 1
				if not k:
					return matrix[ml][col]
			for row in range(ml + 1, m + 1):
				k -= 1
				if not k:
					return matrix[row][n]
			if m != ml:
				for col in range(n - 1, nl - 1, -1):
					k -= 1
					if not k:
						return matrix[m][col]
			if n != nl:
				for row in range(m - 1, ml, -1):
					k -= 1
					if not k:
						return matrix[row][nl]
			m -= 1
			n -= 1
			ml += 1
			nl += 1


class Solution:

	def findK(self, a, n, m, k):
		top = 0
		down = n - 1
		left = 0
		right = m - 1
		l = 0
		while True:
			for i in range(left, right + 1):
				l = l + 1
				if l == k:
					return a[top][i]
			top = top + 1
			for i in range(top, down + 1):
				l = l + 1
				if l == k:
					return a[i][right]
			right = right - 1
			for i in range(right, left - 1, -1):
				l = l + 1
				if l == k:
					return a[down][i]
			down = down - 1
			for i in range(down, top - 1, -1):
				l = l + 1
				if l == k:
					return a[i][left]
			left = left + 1


class Solution:

	def findK(self, a, n, m, k):
		top = 0
		down = n - 1
		left = 0
		right = m - 1
		rele = 0
		l = 0
		while l < k:
			if rele == 0:
				for i in range(left, right + 1):
					l = l + 1
					if l == k:
						return a[top][i]
				top = top + 1
			elif rele == 1:
				for i in range(top, down + 1):
					l = l + 1
					if l == k:
						return a[i][right]
				right = right - 1
			elif rele == 2:
				for i in range(right, left - 1, -1):
					l = l + 1
					if l == k:
						return a[down][i]
				down = down - 1
			elif rele == 3:
				for i in range(down, top - 1, -1):
					l = l + 1
					if l == k:
						return a[i][left]
				left = left + 1
			rele = (rele + 1) % 4


class Solution:

	def findK(self, matrix, n, m, k):
		res = []
		if len(matrix) == 0:
			return res
		row_begin = 0
		col_begin = 0
		row_end = len(matrix) - 1
		col_end = len(matrix[0]) - 1
		while row_begin <= row_end and col_begin <= col_end:
			for i in range(col_begin, col_end + 1):
				res.append(matrix[row_begin][i])
			row_begin += 1
			for i in range(row_begin, row_end + 1):
				res.append(matrix[i][col_end])
			col_end -= 1
			if row_begin <= row_end:
				for i in range(col_end, col_begin - 1, -1):
					res.append(matrix[row_end][i])
				row_end -= 1
			if col_begin <= col_end:
				for i in range(row_end, row_begin - 1, -1):
					res.append(matrix[i][col_begin])
				col_begin += 1
		return res[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		r = 0
		c = 0
		count = 0
		sr = 0
		sc = 0
		er = n - 1
		ec = m - 1
		while sr <= er and sc <= ec:
			while c < ec:
				count += 1
				if count == k:
					return a[r][c]
				c += 1
			sr += 1
			while r < er:
				count += 1
				if count == k:
					return a[r][c]
				r += 1
			ec -= 1
			while c > sc:
				count += 1
				if count == k:
					return a[r][c]
				c -= 1
			er -= 1
			while r > sr:
				count += 1
				if count == k:
					return a[r][c]
				r -= 1
			sc += 1
		return -1


class Solution:

	def findK(self, a, n, m, k):
		t = []
		top = 0
		bot = n - 1
		l = 0
		r = m - 1
		while top <= bot and l <= r:
			for i in range(l, r + 1):
				t.append(a[top][i])
			top += 1
			for i in range(top, bot + 1):
				t.append(a[i][r])
			r -= 1
			if top <= bot:
				for i in range(r, l - 1, -1):
					t.append(a[bot][i])
				bot -= 1
			if l <= r:
				for i in range(bot, top - 1, -1):
					t.append(a[i][l])
				l += 1
		return t[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		c = 0
		for i in range(n // 2 + 1):
			for r in range(i, m - i):
				c += 1
				if c == k:
					return a[i][r]
			for d in range(i + 1, n - i):
				c += 1
				if c == k:
					return a[d][r]
			for l in range(m - i - 2, i - 1, -1):
				c += 1
				if c == k:
					return a[d][l]
			for u in range(i + 1, n - i - 1):
				c += 1
				if c == k:
					return a[n - u - 1][i]
		if n % 2 == 1:
			c += 1
			if c == k:
				return a[n // 2][n // 2]


class Solution:

	def findK(self, a, n, m, k):
		res = []
		(top, left) = (0, 0)
		(down, right) = (n - 1, m - 1)
		while top <= down and left <= right:
			for i in range(left, right + 1):
				res.append(a[top][i])
			top += 1
			for i in range(top, down + 1):
				res.append(a[i][right])
			right -= 1
			if top <= down:
				for i in range(right, left - 1, -1):
					res.append(a[down][i])
				down -= 1
			if right >= left:
				for i in range(down, top - 1, -1):
					res.append(a[i][left])
				left += 1
		return res[k - 1]


class Solution:

	def findK(self, a, n, m, K):
		k = []
		c = 1
		ll = 0
		r = len(matrix[0]) - 1
		t = 1
		d = len(matrix) - 1
		ele = 0
		while ele < len(matrix) * len(matrix[0]):
			if c == 5:
				c = 1
			if c == 1:
				i = ll
				j = ll
				while j <= r:
					k.append(matrix[i][j])
					ele += 1
					j += 1
				c += 1
			elif c == 2:
				i = ll + 1
				j = r
				while i <= d:
					k.append(matrix[i][j])
					ele += 1
					i += 1
				c += 1
			elif c == 3:
				i = d
				j = r - 1
				while j >= ll:
					k.append(matrix[i][j])
					ele += 1
					j -= 1
				c += 1
			elif c == 4:
				i = d - 1
				j = ll
				while i >= t:
					k.append(matrix[i][j])
					ele += 1
					i -= 1
				c += 1
				r -= 1
				ll += 1
				d -= 1
				t += 1
		return k[K - 1]


class Solution:

	def findK(self, arr, n, m, K):
		top = 0
		bottom = n - 1
		left = 0
		right = m - 1
		count = 0
		while top <= bottom and left <= right:
			for i in range(left, right + 1):
				count += 1
				if count == K:
					return arr[top][i]
			top += 1
			for j in range(top, bottom + 1):
				count += 1
				if count == K:
					return arr[j][right]
			right -= 1
			for k in range(right, left - 1, -1):
				count += 1
				if count == K:
					return arr[bottom][k]
			bottom -= 1
			for l in range(bottom, top - 1, -1):
				count += 1
				if count == K:
					return arr[l][left]
			left += 1
		return -1


class Solution:

	def findK(self, a, n, m, k):
		strow = 0
		stcol = 0
		enrow = n - 1
		encol = m - 1
		cnt = 0
		while cnt <= k:
			for i in range(stcol, encol + 1):
				ans = a[strow][i]
				cnt += 1
				if cnt == k:
					return ans
			strow += 1
			for i in range(strow, enrow + 1):
				ans = a[i][encol]
				cnt += 1
				if cnt == k:
					return ans
			encol -= 1
			for i in range(encol, stcol - 1, -1):
				ans = a[enrow][i]
				cnt += 1
				if cnt == k:
					return ans
			enrow -= 1
			for i in range(enrow, strow - 1, -1):
				ans = a[i][stcol]
				cnt += 1
				if cnt == k:
					return ans
			stcol += 1


class Solution:

	def findK(self, a, n, m, k):
		ans = []
		l = 0
		r = m - 1
		up = 0
		down = n - 1
		c = 0
		while len(ans) < n * m:
			for i in range(l, r + 1):
				c += 1
				ans.append(a[up][i])
				if c == k:
					return ans[c - 1]
			for j in range(up + 1, down + 1):
				c += 1
				ans.append(a[j][r])
				if c == k:
					return ans[c - 1]
			if up != down:
				for i in range(r - 1, l - 1, -1):
					c += 1
					ans.append(a[down][i])
					if c == k:
						return ans[c - 1]
			if l != r:
				for i in range(down - 1, up, -1):
					c += 1
					ans.append(a[i][l])
					if c == k:
						return ans[c - 1]
			up += 1
			r -= 1
			down -= 1
			l += 1
		return ans[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		sp = []
		j = 0
		while len(sp) < k:
			for i in range(j, m - j):
				sp.append(a[j][i])
			for i in range(1 + j, n - j - 1):
				sp.append(a[i][-j - 1])
			for i in range(j, m - j):
				sp.append(a[-j - 1][-i - 1])
			for i in range(1 + j, n - j - 1):
				sp.append(a[-i - 1][j])
			j += 1
		return sp[k - 1]


class Solution:

	def findK(self, A, N, M, K):
		(top, bottom, left, right) = (0, N - 1, 0, M - 1)
		result = None
		while True:
			for j in range(left, right + 1):
				result = A[top][j]
				K -= 1
				if K == 0:
					return result
			top += 1
			for i in range(top, bottom + 1):
				result = A[i][right]
				K -= 1
				if K == 0:
					return result
			right -= 1
			for j in range(right, left - 1, -1):
				result = A[bottom][j]
				K -= 1
				if K == 0:
					return result
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				result = A[i][left]
				K -= 1
				if K == 0:
					return result
			left += 1
			if K == 0:
				return result


class Solution:

	def findK(self, matrix, r, c, k):
		top = 0
		bottom = r - 1
		left = 0
		right = c - 1
		dir = 0
		l = []
		while top <= bottom and left <= right:
			if dir == 0:
				for i in range(left, right + 1):
					l.append(matrix[top][i])
				top += 1
			elif dir == 1:
				for i in range(top, bottom + 1):
					l.append(matrix[i][right])
				right -= 1
			elif dir == 2:
				for i in range(right, left - 1, -1):
					l.append(matrix[bottom][i])
				bottom -= 1
			elif dir == 3:
				for i in range(bottom, top - 1, -1):
					l.append(matrix[i][left])
				left += 1
			dir = (dir + 1) % 4
		return l[k - 1]


class Solution:

	def findK(self, a, n, m, k):
		d = 1
		c = 0
		i = 0
		j = 0
		while j < m:
			c += 1
			if c == k:
				return a[i][j]
			j += 1
		j -= 1
		i += 1
		while i < n:
			c += 1
			if c == k:
				return a[i][j]
			i += 1
		i -= 1
		j -= 1
		while j > -1:
			c += 1
			if c == k:
				return a[i][j]
			j -= 1
		j += 1
		i -= 1
		while c < k:
			while i >= d:
				c += 1
				if c == k:
					return a[i][j]
				i -= 1
			i += 1
			j += 1
			while j < m - d:
				c += 1
				if c == k:
					return a[i][j]
				j += 1
			j -= 1
			i += 1
			while i < n - d:
				c += 1
				if c == k:
					return a[i][j]
				i += 1
			i -= 1
			j -= 1
			while j >= d:
				c += 1
				if c == k:
					return a[i][j]
				j -= 1
			j += 1
			i -= 1
			d += 1