Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details.
Example 1:
Input:
N = 2
matrix[][] = {{1,2},
              {3,4}}
Output:
1 2 3 4
Explanation:
Matrix is as below:
1 2
3 4
Printing it in anti-diagonal form will lead
to the output as 1 2 3 4
Example 2:
Input:
N = 3
matrix[][] = {{1,2,3},
              {4,5,6},
              {7,8,9}}
Output:
1 2 4 3 5 7 6 8 9
Explanation: 
Matrix is as below:
1 2 3
4 5 6
7 8 9
Printing it in anti-diagonal form will lead
to the output as 1 2 4 3 5 7 6 8 9 
Your Task:
You dont need to read input or print anything. Complete the function antiDiagonalPattern() that takes matrix as input parameter and returns a list of integers in order of the values visited in the anti-Diagonal pattern. 
Expected Time Complexity: O(N * N)
Expected Auxiliary Space: O(N * N) for the resultant list only.
 
Constraints:
1 <= N <= 100
0 <= mat[i][j] <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def antiDiagonalPattern(self,matrix):

        # Code here

Solutions:
class Solution:

	def antiDiagonalPattern(self, m):
		e = []
		for i in range(len(m[0])):
			a = i
			for j in range(len(m)):
				if a >= 0:
					e += [m[j][a]]
				a -= 1
		for i in range(len(m[0])):
			b = len(m[0]) - 1
			for j in range(i + 1, len(m)):
				if b >= 0:
					e += [m[j][b]]
				b -= 1
		return e


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		ans = []
		for k in range(n):
			for i in range(k + 1):
				ans.append(matrix[i][k - i])
		for k in range(n, 2 * n - 1):
			for i in range(k - n + 1, n):
				ans.append(matrix[i][k - i])
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		for i in range(len(matrix)):
			s = 0
			e = i
			while 0 <= s < n and 0 <= e < n:
				print(matrix[s][e], end=' ')
				s += 1
				e -= 1
		for i in range(1, len(matrix)):
			s = i
			e = n - 1
			while 0 <= s < n and 0 <= e < n:
				print(matrix[s][e], end=' ')
				s += 1
				e -= 1
		return []


class Solution:

	def antiDiagonalPattern(self, matrix):
		l = len(matrix)
		count = 0
		i = j = 0
		ans = []
		while count < 2 * l - 1:
			if count <= (2 * l - 1) // 2:
				j = count
				i = 0
				while j >= 0:
					ans.append(matrix[i][j])
					i += 1
					j -= 1
			else:
				i = count - (2 * l - 1) // 2
				j = (2 * l - 1) // 2
				while i <= (2 * l - 1) // 2:
					ans.append(matrix[i][j])
					i += 1
					j -= 1
			count += 1
		return ans


class Solution:

	def antiDiagonalPattern(self, arr):
		n = len(arr)
		res = []
		for i in range(n):
			row = 0
			col = i
			while row < n and col > -1:
				res.append(arr[row][col])
				row += 1
				col -= 1
		for i in range(1, n):
			row = i
			col = n - 1
			while col > 0 and row < n:
				res.append(arr[row][col])
				row += 1
				col -= 1
		return res


class Solution:

	def antiDiagonalPattern(self, arr):
		n = len(arr)
		ans = []
		for j in range(n):
			i = 0
			while j > -1:
				ans.append(arr[i][j])
				j -= 1
				i += 1
		for i in range(1, n):
			j = n - 1
			while i < n:
				ans.append(arr[i][j])
				j -= 1
				i += 1
		return ans


from collections import OrderedDict

class Solution:

	def antiDiagonalPattern(self, matrix):
		hmap = OrderedDict()
		aux = []
		m = len(matrix)
		n = len(matrix[0])
		sm = 0
		for i in range(n):
			for j in range(m):
				if i + j not in hmap:
					hmap[i + j] = [matrix[i][j]]
				else:
					hmap[i + j].append(matrix[i][j])
		ans = []
		for (key, val) in hmap.items():
			ans += val
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		arr = []
		n = len(matrix)
		for k in range(n):
			i = 0
			j = k
			while i <= k and j >= 0:
				arr.append(matrix[i][j])
				i += 1
				j -= 1
		for k in range(1, n):
			i = k
			j = n - 1
			while i < n and j > 0:
				arr.append(matrix[i][j])
				i += 1
				j -= 1
		return arr


class Solution:

	def antiDiagonalPattern(self, mat):
		n = len(mat)
		row = 0
		col = -1
		res = []
		while row < n:
			if col < n - 1:
				row = 0
				col += 1
			elif col >= n - 1:
				row += 1
				col = n - 1
			i = row
			j = col
			while i < n and j >= 0:
				res.append(mat[i][j])
				i += 1
				j -= 1
		return res


class Solution:

	def antiDiagonalPattern(self, matrix):
		t = []
		c = 0
		while c != 2 * len(matrix) - 1:
			for i in range(len(matrix)):
				for j in range(len(matrix)):
					if i + j == c:
						t.append(matrix[i][j])
			c += 1
		return t


class Solution:

	def antiDiagonalPattern(self, matrix):
		d = {}
		r = len(matrix)
		c = len(matrix)
		for i in range(r):
			for j in range(c):
				sumi = i + j
				if sumi not in d:
					d[sumi] = [matrix[i][j]]
				else:
					d[sumi].append(matrix[i][j])
		ans = []
		for (i, j) in d.items():
			ans += j
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		output = []
		for i in range(n):
			for j in range(i):
				output.append(matrix[j][i - j - 1])
		for i in range(n):
			for j in range(n - i):
				output.append(matrix[i + j][n - j - 1])
		return output


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		arr = []
		for x in range(2 * n):
			gen = [0, x]
			for y in range(n):
				if gen[1] in range(n):
					arr.append(matrix[gen[0]][gen[1]])
				gen[0] += 1
				gen[1] -= 1
		return arr


class Solution:

	def antiDiagonalPattern(self, matrix):
		result = []
		(rows, columns) = (len(matrix), len(matrix[0]))
		for j in range(columns):
			(i, j) = (0, j)
			while i < rows and j >= 0:
				result.append(matrix[i][j])
				i += 1
				j -= 1
		for i in range(1, rows):
			(i, j) = (i, columns - 1)
			while i < rows and j >= 0:
				result.append(matrix[i][j])
				i += 1
				j -= 1
		return result


def antiDiagonalTraversal(mat):
	(r, c) = (len(mat), len(mat[0]))
	i = 0
	result = []
	for j in range(c):
		helper(i, j, r, c, result, mat)
	j = c - 1
	for i in range(1, r):
		helper(i, j, r, c, result, mat)
	return result

def helper(i, j, r, c, result, arr):
	result.append(arr[i][j])
	if isValid(i + 1, j - 1, r, c):
		return helper(i + 1, j - 1, r, c, result, arr)

def isValid(i, j, r, c):
	if i >= 0 and i < r and (j >= 0) and (j < c):
		return True
	return False

class Solution:

	def antiDiagonalPattern(self, matrix):
		return antiDiagonalTraversal(matrix)


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix[0])
		dia = 2 * n - 1
		l = []
		for x in range(1, dia + 1):
			c = x - 1
			c2 = 0
			for y in range(x):
				if c < n and c2 < n:
					l.append(matrix[c2][c])
				c -= 1
				c2 += 1
		return l


class Solution:

	def antiDiagonalPattern(self, mat):
		ans = list()
		n = len(mat)
		for i in range(n):
			temp = i
			for j in range(i + 1):
				ans.append(mat[j][temp])
				temp -= 1
		val = 1
		for i in range(n - 1):
			temp = n - 1
			for j in range(val, n):
				ans.append(mat[j][temp])
				temp -= 1
			val += 1
		return ans


from collections import defaultdict

class Solution:

	def antiDiagonalPattern(self, matrix):
		if not matrix:
			return
		mp = defaultdict(list)
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				mp[i + j].append(matrix[i][j])
		res = []
		for k in sorted(mp.keys()):
			res.extend(mp[k])
		return res


class Solution:

	def antiDiagonalPattern(self, mat):
		r = len(mat)
		c = len(mat[0])
		ans = [-1] * (r * c)
		row = 0
		col = 0
		k = 0
		while row < r:
			i = row
			j = col
			while i < r and j >= 0:
				ans[k] = mat[i][j]
				k += 1
				i += 1
				j -= 1
			col += 1
			if col >= c:
				row += 1
				col = c - 1
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		ans = []
		k = 0
		while k < n:
			(i, j) = (0, k)
			while i < n and j >= 0:
				ans.append(matrix[i][j])
				j -= 1
				i += 1
			k += 1
		k = 1
		while k < n:
			(i, j) = (k, n - 1)
			while i < n and j >= 0:
				ans.append(matrix[i][j])
				j -= 1
				i += 1
			k += 1
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		res = []
		N = len(matrix)
		c = 1
		for k in range(2 * N - 1):
			if k < N:
				for i in range(k + 1):
					j = k - i
					res.append(matrix[i][j])
			else:
				for i in range(c, N):
					j = k - i
					res.append(matrix[i][j])
				c += 1
		return res


class Solution:

	def antiDiagonalPattern(self, matrix):
		arr = []
		n = len(matrix)
		for y in range(n):
			for i in range(y + 1):
				arr.append(matrix[i][y - i])
		for x in range(1, n):
			for i in range(n - x):
				arr.append(matrix[x + i][n - 1 - i])
		return arr


class Solution:

	def antiDiagonalPattern(self, matrix):
		l = [[] for i in range(2 * len(matrix) - 1)]
		for i in range(len(matrix)):
			for j in range(len(matrix)):
				l[i + j].append(matrix[i][j])
		ans = []
		for i in range(len(l)):
			for j in l[i]:
				ans.append(j)
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		if len(matrix) == 1:
			return [matrix[0][0]]

		def diagonal(matrix, x, y, final):
			while y > 0:
				final.append(matrix[x][y])
				x += 1
				y -= 1

		def diagonalnew(matrix, x, y, final):
			while x < len(matrix) - 1:
				final.append(matrix[x][y])
				x += 1
				y -= 1
		(i, j, m, n) = (0, 0, 0, 1)
		flag = True
		final = []
		while m != len(matrix):
			if flag:
				final.append(matrix[i][j])
				diagonal(matrix, m, n, final)
				if n != len(matrix) - 1:
					i += 1
					n += 1
				else:
					i += 1
					m += 1
					flag = False
			else:
				final.append(matrix[i][j])
				diagonalnew(matrix, m, n, final)
				j += 1
				m += 1
		final.append(matrix[-1][-1])
		return final


class Solution:

	def antiDiagonalPattern(self, matrix):
		out = []
		N = len(matrix)
		arr = []
		for i in range(N):
			temp = [0] * i
			temp += matrix[i]
			temp += [0] * (N - 1 - i)
			arr.append(temp)
		for j in range(N):
			for i in range(0, j + 1):
				out.append(arr[i][j])
		for j in range(1, N):
			for i in range(j, N):
				out.append(arr[i][N - 1 + j])
		return out


class Solution:

	def antiDiagonalPattern(self, matrix):
		A = []
		for s in range(0, len(matrix) + len(matrix) + 1):
			for i in range(len(matrix)):
				for j in range(len(matrix)):
					if i + j == s:
						A.append(matrix[i][j])
		return A


class Solution:

	def antiDiagonalPattern(self, matrix):
		ans = []
		for c in range(len(matrix)):
			startc = c
			startr = 0
			while startc >= 0 and startr < len(matrix):
				ans.append(matrix[startr][startc])
				startc -= 1
				startr += 1
		for r in range(1, len(matrix)):
			startr = r
			startc = len(matrix) - 1
			while startr < len(matrix) and startc >= 0:
				ans.append(matrix[startr][startc])
				startc -= 1
				startr += 1
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		N = len(matrix[0])
		l = []
		m = []
		for i in range(N):
			l.append([h for h in range(i + 1)])
		for i in l:
			m.append(i[::-1])
		l2 = []
		m2 = []
		for i in l:
			for j in i:
				l2.append(j)
		for i in m:
			for j in i:
				m2.append(j)
		s = []
		k = 1
		for i in range(1, N):
			s.append([h for h in range(k, N)])
			k += 1
		o = []
		for i in s:
			o.append(i[::-1])
		s2 = []
		o2 = []
		for i in s:
			for j in i:
				s2.append(j)
		for i in o:
			for j in i:
				o2.append(j)
		l2 = l2 + s2
		m2 = m2 + o2
		kundan = []
		for i in range(N * N):
			kundan.append(matrix[l2[i]][m2[i]])
		return kundan


class Solution:

	def antiDiagonalPattern(self, matrix):
		ans = []
		row = len(matrix)
		col = len(matrix[0])
		for c in range(col):
			i = 0
			j = c
			while j >= 0 and i < row:
				ans.append(matrix[i][j])
				j -= 1
				i += 1
		for r in range(1, row):
			i = r
			j = col - 1
			while i < row and j >= 0:
				ans.append(matrix[i][j])
				i += 1
				j -= 1
		return ans


class Solution:

	def antiDiagonalPattern(self, A):
		N = len(matrix)
		ans = []
		for col in range(N):
			startcol = col
			startrow = 0
			while startcol >= 0 and startrow < N:
				ans.append(A[startrow][startcol])
				startcol -= 1
				startrow += 1
		for row in range(1, N):
			startrow = row
			startcol = N - 1
			while startrow < N and startcol >= 0:
				ans.append(A[startrow][startcol])
				startcol -= 1
				startrow += 1
		return ans


class Solution:

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


class Solution:

	def antiDiagonalPattern(self, atrix):
		n = len(matrix)
		ar = []
		i = 0
		j = 0
		fg = 0
		bk = 0
		while 1:
			i = 0
			j = fg
			fg += 1
			while j >= 0:
				if i < n and j < n:
					ar.append(matrix[i][j])
				if i == n - 1 and j == n - 1:
					bk = 1
					break
				i += 1
				j -= 1
			if bk == 1:
				break
		return ar


class Solution:

	def antiDiagonalPattern(self, matrix):
		m = matrix
		arr = [[0] * n] * n
		res = []
		k = 0
		for i in range(n):
			for j in range(n):
				if arr[i][j] == 0:
					res.append(m[i][j])
					k = i
					while k < n - 1 and j <= n - 1 and (j >= 1):
						res.append(m[k + 1][j - 1])
						arr[k + 1][j - 1] = 1
						k += 1
						j -= 1
		return res


class Solution:

	def antiDiagonalPattern(self, matrix):
		N = len(matrix)
		M = N
		row_tracker = 0
		column_tracker = 0
		output = []
		while True:
			row = row_tracker
			column = column_tracker
			while column >= 0:
				number = matrix[row][column]
				output.append(number)
				column -= 1
				if row == M - 1:
					break
				row += 1
			if column_tracker == M - 1 and row_tracker == N - 1:
				break
			if column_tracker == N - 1:
				row_tracker += 1
			if column_tracker < N - 1:
				column_tracker += 1
		return output


class Solution:

	def antiDiagonalPattern(self, matrix):
		ans = []
		N = len(matrix)
		(st, end) = (0, 0)
		for _ in range(2 * N - 1):
			if st == N:
				break
			ans.append(matrix[st][end])
			(i, j) = (st, end)
			while 0 <= i + 1 < N and 0 <= j - 1 < N:
				i += 1
				j -= 1
				ans.append(matrix[i][j])
			if end < N - 1:
				end += 1
			else:
				st += 1
		return ans


class Solution:

	def antiDiagonalPattern(self, mat):
		n = len(mat)
		l = []
		d = {i: [] for i in range(2 * n - 1)}
		for i in range(n):
			for j in range(n):
				d[i + j].append(mat[i][j])
		for i in d.keys():
			l.extend(d[i])
		return l


class Solution:

	def antiDiagonalPattern(self, mat):
		n = len(mat)
		l = []
		for j in range(n):
			c = j
			i = 0
			while c > -1 and i <= j:
				l.append(mat[i][c])
				c = c - 1
				i = i + 1
		i = 0
		h = 0
		while h < n - 1:
			c = n - 1
			i = i + 1
			x = i
			while c >= i and x < n:
				l.append(mat[x][c])
				x = x + 1
				c = c - 1
			h = h + 1
		if len(l) < n * n:
			l.append(mat[n - 1][n - 1])
		return l
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		inp = list(map(int, input().split()))
		matrix = []
		k = 0
		for i in range(n):
			row = []
			for j in range(n):
				row.append(inp[k])
				k += 1
			matrix.append(row)
		ob = Solution()
		ans = ob.antiDiagonalPattern(matrix)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def antiDiagonalPattern(self, matrix):
		ans = []
		s = 2 * len(matrix) - 2
		for i in range(s + 1):
			for j in range(len(matrix)):
				a = j
				b = i - j
				if b < len(matrix) and b >= 0:
					ans.append(matrix[a][b])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		inp = list(map(int, input().split()))
		matrix = []
		k = 0
		for i in range(n):
			row = []
			for j in range(n):
				row.append(inp[k])
				k += 1
			matrix.append(row)
		ob = Solution()
		ans = ob.antiDiagonalPattern(matrix)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def antiDiagonalPattern(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		L = []
		for each in range(m + n - 1):
			xi = 0
			yi = each
			if each >= m:
				xi = each % m + 1
			if xi != 0:
				yi = m - 1
			while xi < m and yi >= 0:
				L.append(matrix[xi][yi])
				xi += 1
				yi -= 1
		return L
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		inp = list(map(int, input().split()))
		matrix = []
		k = 0
		for i in range(n):
			row = []
			for j in range(n):
				row.append(inp[k])
				k += 1
			matrix.append(row)
		ob = Solution()
		ans = ob.antiDiagonalPattern(matrix)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def antiDiagonalPattern(self, matrix):
		a = []
		for j in range(len(matrix[0])):
			k = j
			i = 0
			while k >= 0:
				a.append(matrix[i][k])
				i += 1
				k -= 1
		for i in range(1, len(matrix)):
			j = len(matrix[0]) - 1
			k = i
			while k != len(matrix):
				a.append(matrix[k][j])
				k += 1
				j -= 1
		return a


class Solution:

	def antiDiagonalPattern(self, matrix):
		min_lim = 0
		max_lim = len(matrix)
		final_list = []
		for i in range(max_lim + max_lim - 1):
			if i < max_lim:
				(a, b) = (0, i)
				while a <= i:
					final_list.append(matrix[a][b])
					a += 1
					b -= 1
			else:
				(a, b) = (i - max_lim + 1, max_lim - 1)
				while a <= max_lim - 1:
					final_list.append(matrix[a][b])
					a += 1
					b -= 1
		return final_list


class Solution:

	def antiDiagonalPattern(self, A):
		r = len(A)
		c = len(A[0])
		t = 2 * r - 1
		res = []
		for k in range(t):
			for i in range(r):
				for j in range(c - 1, -1, -1):
					if i + j == k:
						res.append(A[i][j])
		return res


class Solution:

	def antiDiagonalPattern(self, matrix):
		ans = []
		n = len(matrix)

		def isval(x, y):
			return 0 <= x < n and 0 <= y < n
		q = []
		for i in range(n):
			for j in range(n):
				if i == 0 or j == n - 1:
					q.append((i, j))
		for val in q:
			t1 = val[0]
			t2 = val[1]
			while isval(t1, t2):
				ans.append(matrix[t1][t2])
				t1 += 1
				t2 -= 1
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		ans = []
		for i in range(n):
			(a, b) = (0, i)
			while a <= i and b >= 0:
				ans.append(matrix[a][b])
				a += 1
				b -= 1
		for j in range(1, n):
			(a, b) = (j, n - 1)
			while a <= n and b >= j:
				ans.append(matrix[a][b])
				a += 1
				b -= 1
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		d = {}
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				if i + j not in d:
					d[i + j] = [matrix[i][j]]
				else:
					d[i + j].append(matrix[i][j])
		ans = []
		for (k, v) in d.items():
			ans.extend(v)
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		l = []
		n = len(matrix)
		for i in range(n):
			a = 0
			b = i
			while a <= i and b >= 0:
				l.append(matrix[a][b])
				a = a + 1
				b = b - 1
		for k in range(1, n):
			a = k
			b = n - 1
			while a < n and b > 0:
				l.append(matrix[a][b])
				a = a + 1
				b = b - 1
		return l


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		l = [0] * (n + n)
		for i in range(n + n):
			l[i] = []
		for i in range(n):
			for j in range(n):
				s = i + j
				l[s].append(matrix[i][j])
		ans = []
		for i in range(n + n):
			ans = ans + l[i]
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		lst = []
		N = len(matrix)
		M = len(matrix[0])
		for k in range(N):
			i = 0
			j = k
			while i <= k and j >= 0:
				lst.append(matrix[i][j])
				i += 1
				j -= 1
		for k in range(1, N):
			i = k
			j = N - 1
			while i < N and j >= 0:
				lst.append(matrix[i][j])
				i += 1
				j -= 1
		return lst


class Solution:

	def antiDiagonalPattern(self, matrix):
		x = len(matrix)
		final = []
		for i in range(x):
			a = 0
			b = i
			while b != -1 and a != i + 1:
				final.append(matrix[a][b])
				a += 1
				b -= 1
		for i in range(1, x):
			a = i
			b = x - 1
			while a != x:
				final.append(matrix[a][b])
				a += 1
				b -= 1
		return final


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		ans = [[] for i in range(n + m - 1)]
		for i in range(m):
			for j in range(n):
				ans[i + j].append(matrix[i][j])
			ask = []
			for i in range(len(ans)):
				for j in range(len(ans[i])):
					ask.append(ans[i][j])
		return ask


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		ans = []
		res = []
		for _ in range(2 * n - 1):
			ans.append([])
		for i in range(n):
			for j in range(len(matrix[0])):
				ans[i + j].append(matrix[i][j])
		for i in range(2 * n - 1):
			for j in range(len(ans[i])):
				res.append(ans[i][j])
		return res


class Solution:

	def antiDiagonalPattern(self, matrix):
		res = []
		for i in range(len(matrix)):
			index = i
			for j in range(i + 1):
				res.append(matrix[j][index])
				index -= 1
		for i in range(1, len(matrix)):
			index = len(matrix) - 1
			for j in range(i, len(matrix)):
				res.append(matrix[j][index])
				index -= 1
		return res


class Solution:

	def antiDiagonalPattern(self, matrix):
		diagonal = []
		(start, i) = (0, 0)
		while i <= len(matrix):
			if i == len(matrix):
				start += 1
				i -= 1
			row = start
			cl = i
			while row < len(matrix) and cl >= 0:
				diagonal.append(matrix[row][cl])
				row += 1
				cl -= 1
			i += 1
			if i == len(matrix) and start == len(matrix) - 1:
				break
		return diagonal


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		s = [[] for i in range(2 * (n - 1) + 1)]
		for i in range(n):
			for j in range(n):
				s[i + j].append(matrix[i][j])
		res = []
		for i in s:
			res.extend(i)
		return res


class Solution:

	def antiDiagonalPattern(self, matrix):
		res = []
		(i, j) = (0, 0)
		while j < len(matrix):
			(a, b) = (i, j)
			while a >= 0 and a < len(matrix) and (b >= 0) and (b < len(matrix)):
				res.append(matrix[a][b])
				a += 1
				b -= 1
			j += 1
		j -= 1
		i += 1
		while i < len(matrix):
			(a, b) = (i, j)
			while a >= 0 and a < len(matrix) and (b >= 0) and (b < len(matrix)):
				res.append(matrix[a][b])
				a += 1
				b -= 1
			i += 1
		return res


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		result = []
		for x in range(n):
			if x == 0:
				result.append(matrix[x][x])
			else:
				j = x
				for i in range(x + 1):
					result.append(matrix[i][j])
					if j == 0:
						break
					j -= 1
		for x in range(1, n):
			if x == n - 1:
				result.append(matrix[x][x])
				break
			j = 1
			for i in range(x, n):
				result.append(matrix[i][n - j])
				j += 1
		return result


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		arr = []
		for i in range(n):
			for j in range(i + 1):
				arr.append(matrix[j][i - j])
		nj = 1
		for i in range(n, (n - 1) * 2 + 1):
			for j in range(nj, i - nj + 1):
				arr.append(matrix[j][i - j])
			nj += 1
		return arr


class Solution:

	def antiDiagonalPattern(self, matrix):
		m = []
		for k in range(2 * (len(matrix[0]) - 1) + 1):
			m.append([])
		for i in range(len(matrix[0])):
			for j in range(len(matrix[0])):
				m[i + j].append(matrix[i][j])
		ans = []
		for i in range(len(m)):
			ans.extend(m[i])
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		ans = []
		n = len(matrix)
		for l in range(2 * n - 1):
			(b, t) = (min(l, n - 1), max(l + 1 - n, 0))
			for i in range(t, b + 1):
				ans.append(matrix[i][l - i])
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		N = 2 * len(matrix) - 1
		res = []
		for i in range(N):
			res.append([])
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				res[i + j].append(matrix[i][j])
		ans = []
		for i in res:
			ans.extend(i)
		return ans


class Solution:

	def antiDiagonalPattern(self, matrix):
		n = len(matrix)
		result = [0] * n * n
		k = 0
		for j in range(n):
			i = 0
			while j >= 0:
				result[k] = matrix[i][j]
				i += 1
				j -= 1
				k += 1
		for i in range(1, n):
			j = n - 1
			while i < n:
				result[k] = matrix[i][j]
				i += 1
				j -= 1
				k += 1
		return result


from collections import OrderedDict as od

class Solution:

	def antiDiagonalPattern(self, matrix):
		d = od()
		for i in range(0, n):
			for j in range(0, n):
				t = i + j
				if t in d.keys():
					d[t].append(matrix[i][j])
				else:
					d[t] = [matrix[i][j]]
		ans = []
		for (x, y) in d.items():
			ans.extend(y)
		return ans