Give a N * N square matrix A, return all the elements of its anti-diagonals from top to bottom. 
Example 1:
Input: 
N = 2
A = [[1, 2],
     [3, 4]]
Output:
1 2 3 4
Explanation: 
Hence, elements will be returned in the 
order {1, 2, 3, 4}.
Example 2:
Input: 
N = 3 
A = [[1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]]
Output: 
1 2 4 3 5 7 6 8 9
Explanation: 
Hence, elements will be returned in 
the order {1, 2, 4, 3, 5, 7, 6, 8, 9}.
Your Task:
You don't need to read input or print anything. Your task is to complete the function downwardDiagonal() which takes an integer N and a 2D matrix A[ ][ ] as input parameters and returns the list of all elements of its anti-diagonals from top to bottom.
Expected Time Complexity: O(N*N)
Expected Auxillary Space: O(N*N)
Constraints:
1 ≤ N, M ≤ 10^{3}
0 ≤ A[i][j] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Matrices

Data structures

Starter code: #User function Template for python3



def downwardDiagonal(N, A): 

    # code here 

Solutions:
import numpy as np

def downwardDiagonal(N, A):
	fu = []
	x = [[] for i in range(0, 2 * N - 1)]
	for i in range(N):
		for j in range(N):
			x[i + j].append(A[i][j])
	for i in range(len(x)):
		for j in range(len(x[i])):
			fu.append(x[i][j])
	return fu


def downwardDiagonal(N, A):
	diagonal = [[]]
	for (r_ind, row) in enumerate(matrix):
		for (c_ind, num) in enumerate(row):
			if r_ind + c_ind >= len(diagonal):
				diagonal.append([num])
			else:
				diagonal[r_ind + c_ind].append(num)
	answer = []
	for d in diagonal:
		answer.extend(d)
	return answer


def downwardDiagonal(N, A):
	k = 0
	l = list()
	while k < N:
		i = 0
		j = k
		while j >= 0:
			l.append(A[i][j])
			j -= 1
			i += 1
		k += 1
	k = 1
	while k < N:
		i = k
		j = N - 1
		while i < N:
			l.append(A[i][j])
			j -= 1
			i += 1
		k += 1
	return l


def downwardDiagonal(N, A):
	n = len(A)
	m = len(A[0])
	list = [[] for i in range(n + m - 1)]
	for i in range(n):
		for j in range(m):
			sum = i + j
			if sum % 2 == 0:
				list[sum].append(A[i][j])
			else:
				list[sum].append(A[i][j])
	res = []
	for i in list:
		for j in i:
			res.append(j)
	return res


def downwardDiagonal(N, A):
	dic = {}
	for i in range(N):
		for j in range(N):
			tot = i + j
			if tot not in dic:
				dic[tot] = [A[i][j]]
			else:
				dic[tot].append(A[i][j])
	li = []
	for i in dic:
		li += dic[i]
	return li


def downwardDiagonal(N, A):
	fu = []
	temp = [[] for k in range(0, 2 * N - 1)]
	for i in range(N):
		for j in range(N):
			temp[i + j].append(A[i][j])
	for i in range(len(temp)):
		for j in range(len(temp[i])):
			fu.append(temp[i][j])
	return fu


def downwardDiagonal(N, A):
	l = []
	i = j = 0
	while i <= N - 1:
		a = i
		b = j
		while a <= j:
			l.append(A[a][b])
			a += 1
			b -= 1
		if j == N - 1:
			i += 1
			continue
		j += 1
	return l


def downwardDiagonal(N, A):
	li = []
	for i in range(len(A[0])):
		k = 0
		j = i
		while k <= i and j >= 0:
			li.append(A[k][j])
			k += 1
			j -= 1
	for i in range(1, N):
		k = i
		j = N - 1
		while k <= N - 1 and j >= i:
			li.append(A[k][j])
			k += 1
			j -= 1
	return li


def downwardDiagonal(N, A):
	ans = []
	for i in range(N):
		l = 0
		r = i
		res = []
		while l < N and r >= 0:
			res.append(A[l][r])
			l += 1
			r -= 1
		ans.extend(res)
	for i in range(1, N):
		l = i
		r = N - 1
		res = []
		while l < N and r >= 0:
			res.append(A[l][r])
			l += 1
			r -= 1
		ans.extend(res)
	return ans


from collections import defaultdict

def downwardDiagonal(N, A):
	d = defaultdict(list)
	for i in range(N):
		for j in range(N):
			d[i + j].append(A[i][j])
	ans = []
	for i in d:
		for j in d[i]:
			ans.append(j)
	return ans


def downwardDiagonal(N, A):
	l = []
	for i in range(N):
		row = 0
		col = i
		while col >= 0:
			l.append(A[row][col])
			row += 1
			col -= 1
	for j in range(1, N):
		row = j
		col = N - 1
		while row < N:
			l.append(A[row][col])
			row += 1
			col -= 1
	return l


def downwardDiagonal(N, A):
	n = len(A)
	N = 2 * n - 1
	result = []
	l = []
	for i in range(N):
		result.append([])
	for i in range(n):
		for j in range(n):
			result[i + j].append(A[i][j])
	for i in range(len(result)):
		for j in range(len(result[i])):
			l.append(result[i][j])
	return l


def downwardDiagonal(N, A):
	arr = []
	for i in range(2 * (N - 1) + 1):
		for j in range(i + 1):
			if j < N and abs(i - j) < N:
				arr.append(A[j][abs(i - j)])
	return arr


def downwardDiagonal(N, A):
	ans = []
	for g in range(N):
		i = 0
		j = g
		while i < N and j >= 0:
			ans.append(A[i][j])
			i += 1
			j -= 1
	for r in range(1, N):
		i = r
		j = N - 1
		while i < N and j >= 0:
			ans.append(A[i][j])
			i += 1
			j -= 1
	return ans


def downwardDiagonal(N, A):
	li = [[] for i in range(N + N - 1)]
	ans = []
	for i in range(N):
		for j in range(N):
			li[i + j].append(A[i][j])
	for i in range(len(li)):
		for j in range(len(li[i])):
			ans.append(li[i][j])
	return ans


def downwardDiagonal(N, A):
	arr = []
	s = {}
	i = 0
	j = 0
	while i < len(A):
		k = j
		m = i
		while k >= 0 and m < len(A) and ((m, k) not in s):
			arr.append(A[m][k])
			s[m, k] = 'T'
			m = m + 1
			k = k - 1
		if j == len(A) - 1:
			i = i + 1
		else:
			j = j + 1
	return arr


def downwardDiagonal(n, a):
	ans = [0] * n ** 2
	c = 0
	for i in range(n):
		j = 0
		k = i
		while k >= 0 and j < n:
			ans[c] = a[j][k]
			c += 1
			j += 1
			k -= 1
	for j in range(1, n):
		i = n - 1
		k = j
		while i >= 0 and k < n:
			ans[c] = a[k][i]
			c += 1
			k += 1
			i -= 1
	return ans


def downwardDiagonal(N, A):
	l = []
	for j in range(N):
		i = 0
		while j >= 0:
			l.append(A[i][j])
			j -= 1
			i += 1
	for k in range(N - 1):
		i = k + 1
		j = N - 1
		while i < N:
			l.append(A[i][j])
			i += 1
			j -= 1
	return l


def downwardDiagonal(N, A):
	ans = []
	for k in range(N):
		row = 0
		col = k
		while col >= 0:
			ans.append(A[row][col])
			row += 1
			col -= 1
	for j in range(1, N):
		col = N - 1
		row = j
		while row < N:
			ans.append(A[row][col])
			row += 1
			col -= 1
	return ans


def downwardDiagonal(N, A):
	lis = []
	for col in range(N):
		j = col
		i = 0
		while i < N and j >= 0:
			lis.append(A[i][j])
			i += 1
			j -= 1
	for row in range(1, N):
		i = row
		j = N - 1
		while j >= 0 and i < N:
			lis.append(A[i][j])
			i += 1
			j -= 1
	return lis


def downwardDiagonal(N, A):
	output = []
	for j in range(N):
		r = 0
		c = j
		while r < n and c >= 0:
			output.append(A[r][c])
			r += 1
			c -= 1
	for i in range(1, N):
		r = i
		c = n - 1
		while r < n and c >= 0:
			output.append(A[r][c])
			r += 1
			c -= 1
	return output


def downwardDiagonal(N, A):
	X = []
	for line in range(2 * N):
		start_row = max(0, line - N)
		count = min(line, N - start_row, N)
		for j in range(0, count):
			X.append(A[start_row + j][min(N, line) - j - 1])
	return X


def downwardDiagonal(N, mat):
	m = len(mat)
	n = len(mat[0])
	ll = []
	cnt = 1
	for i in range(n):
		x = 0
		y = i
		l = []
		while (x >= 0 and y >= 0) and (x < m and y < n):
			l.append(mat[x][y])
			x += 1
			y -= 1
		ll += l
	for i in range(1, m):
		x = i
		y = n - 1
		l = []
		while (x >= 0 and y >= 0) and (x < m and y < n):
			l.append(mat[x][y])
			x += 1
			y -= 1
		ll += l
	return ll


def downwardDiagonal(N, A):
	res = []
	for i in range(0, N):
		r = 0
		c = i
		while c >= 0:
			res.append(A[r][c])
			r += 1
			c -= 1
	for i in range(1, N):
		r = i
		c = N - 1
		while r < N:
			res.append(A[r][c])
			r += 1
			c -= 1
	return res


def downwardDiagonal(N, A):
	result = []
	for i in range(0, N):
		row = 0
		col = i
		while col >= 0:
			result.append(A[row][col])
			row += 1
			col -= 1
	for i in range(1, N):
		row = i
		col = N - 1
		while row < N:
			result.append(A[row][col])
			col -= 1
			row += 1
	return result


def downwardDiagonal(n, a):
	l = []
	for i in range(1, n + 1):
		for j in range(i):
			l.append(a[j][i - 1 - j])
	for i in range(n, 2 * n - 1):
		for j in range(i - n + 1, n):
			l.append(a[j][i - j])
	return l


def downwardDiagonal(N, A):
	res = []
	i = 0
	for i in range(1, N * 2):
		temp = max(0, i - N)
		c = min(i, N, N - temp)
		for j in range(c):
			res.append(A[temp + j][min(N, i) - j - 1])
	return res


def downwardDiagonal(N, A):
	res = []
	total = len(A) * len(A)
	for i in range(N):
		x = 0
		y = i
		while x < N and y >= 0:
			res.append(A[x][y])
			x += 1
			y -= 1
	i = 1
	while i < N:
		x = i
		y = N - 1
		while x < N and y >= 0:
			res.append(A[x][y])
			x += 1
			y -= 1
		i += 1
	return res


def downwardDiagonal(N, A):
	output = []
	for i in range(N):
		for j in range(i + 1):
			output.append(A[j][i - j])
	for i in range(1, N):
		for j in range(N - i):
			output.append(A[i + j][N - 1 - j])
	return output


def downwardDiagonal(N, A):
	r = len(A)
	c = len(A)
	l = []

	def isvalid(i, j):
		if i < 0 or i >= r or j < 0 or (j >= c):
			return False
		return True
	for k in range(r):
		l.append(A[0][k])
		i = 1
		j = k - 1
		while isvalid(i, j):
			l.append(A[i][j])
			j -= 1
			i += 1
	for k in range(1, r):
		l.append(A[k][c - 1])
		i = k + 1
		j = c - 2
		while isvalid(i, j):
			l.append(A[i][j])
			i += 1
			j -= 1
	return l


def downwardDiagonal(N, A):
	ans = []
	for i in range(0, N):
		for j in range(0, i + 1):
			ans.append(A[j][i - j])
	for i in range(0, N - 1):
		for j in range(i + 1, N):
			ans.append(A[j][i - j])
	return ans


def downwardDiagonal(N, A):
	A1 = [[] for i in range(2 * N - 1)]
	for i in range(N):
		for j in range(N):
			A1[i + j].append(A[i][j])
	return [a for b in A1 for a in b]


def downwardDiagonal(N, A):
	l1 = []
	for i in range(N):
		j = 0
		while j < N and i >= 0:
			l1.append(A[j][i])
			j += 1
			i -= 1
	l2 = []
	for i in range(N - 1, 0, -1):
		j = N - 1
		while j >= 0 and i < N:
			l2.append(A[j][i])
			j -= 1
			i += 1
	return l1 + l2[::-1]


def downwardDiagonal(n, a):
	res = []
	for k in range(n):
		(i, j) = (0, k)
		while j >= 0:
			res.append(a[i][j])
			i += 1
			j -= 1
	for k in range(1, n):
		(i, j) = (k, n - 1)
		while i < n:
			res.append(a[i][j])
			i += 1
			j -= 1
	return res


def downwardDiagonal(n, A):
	result = []
	for i in range(2 * n - 1):
		diag = []
		if i < n:
			row = 0
			col = i
		else:
			row = i - n + 1
			col = n - 1
		while row < n and col >= 0:
			diag.append(A[row][col])
			row += 1
			col -= 1
		result.extend(diag)
	return result


def downwardDiagonal(N, A):
	row = 0
	col = 0
	start_col = 0
	my_list = []
	while row < N and col < N:
		while col >= 0 and row < N:
			my_list.append(A[row][col])
			row = row + 1
			col = col - 1
		start_col = start_col + 1
		if start_col < N:
			row = 0
			col = start_col
		else:
			row = start_col - (N - 1)
			col = N - 1
		if row == N - 1 and col == N - 1:
			if N != 1:
				my_list.append(A[row][col])
			break
	return my_list


def downwardDiagonal(N, A):
	l1 = []
	l2 = []
	for j in range(N):
		x = 0
		y = j
		while x < N and y >= 0:
			l1.append(A[x][y])
			x = x + 1
			y = y - 1
	for j in range(N - 1, 0, -1):
		x = N - 1
		y = j
		while x >= 0 and y < N:
			l2.append(A[x][y])
			x = x - 1
			y = y + 1
	return l1 + l2[::-1]


def downwardDiagonal(N, A):
	matrix = []
	row = 0
	col = 0
	while col < N:
		r = row
		c = col
		while r < N and c >= 0:
			matrix.append(A[r][c])
			r += 1
			c -= 1
		col += 1
	row = 1
	col = N - 1
	while row < N:
		r = row
		c = col
		while r < N and c >= 0:
			matrix.append(A[r][c])
			r += 1
			c -= 1
		row += 1
	return matrix


def downwardDiagonal(N, A):
	matrix = A
	ans = []
	n = len(matrix)
	for i in range(2 * n - 1):
		for j in range(i + 1):
			if i - j < n and j < n:
				ans.append(matrix[j][i - j])
	return ans


def downwardDiagonal(N, A):
	out = []
	for j in range(2 * N):
		for i in range(N):
			if j - i >= 0 and j - i < N:
				out.append(A[i][j - i])
	return out


def downwardDiagonal(N, A):
	ans = []
	for i in range(N):
		row = 0
		col = i
		while row <= i and col <= i:
			ans += [A[row][col]]
			row += 1
			col -= 1
	for i in range(1, N):
		col = N - 1
		row = i
		while col >= i and row < N:
			ans += [A[row][col]]
			row += 1
			col -= 1
	return ans


def downwardDiagonal(n, li):
	ans = []
	j = 0
	for i in range(n):
		x = i
		y = j
		while x >= 0 and y < n:
			ans.append(li[y][x])
			x -= 1
			y += 1
	j = n - 1
	for i in range(1, n):
		x = i
		y = j
		while x < n and y >= 0:
			ans.append(li[x][y])
			x += 1
			y -= 1
	return ans


def downwardDiagonal(N, A):
	output = []
	for i in range(2 * N - 1):
		output.append([])
	for i in range(N):
		for j in range(N):
			sum = i + j
			output[sum].append(A[i][j])
	result = []
	for item in output:
		result += item
	return result


def downwardDiagonal(N, A):
	res = []
	for t in range((N - 1) * 2 + 1):
		for i in range(N):
			if 0 <= t - i < N:
				res.append(A[i][t - i])
	return res


def downwardDigonal(N, A):
	ans = []
	for i in range(N):
		R = 0
		C = i
		while C >= 0:
			ans.append(A[R][C])
			R += 1
			C -= 1
	for i in range(1, N):
		R = i
		C = N - 1
		while R < N:
			ans.append(A[R][C])
			R += 1
			C -= 1
	return ans


def downwardDigonal(N, A):
	result = []
	for i in range(2 * N):
		row_index = 0
		col_index = i
		while row_index < N or col_index >= 0:
			if row_index < N and 0 <= col_index < N:
				result.append(A[row_index][col_index])
			row_index += 1
			col_index -= 1
	return result


def downwardDigonal(N, A):
	b = []
	r = 0
	for i in range(N + N - 1):
		if i <= N - 1:
			C = i
			R = 0
		if i > N - 1:
			C = N - 1
			r = r + 1
			R = r
		while R <= N - 1 and 0 <= C:
			b.append(A[R][C])
			C = C - 1
			R = R + 1
	return b


def downwardDigonal(n, ar):
	res = []
	for i in range(2 * n - 1):
		r = 0 if i < n else i % n + 1
		c = i if i < n else n - 1
		while r < n and c >= 0:
			res.append(ar[r][c])
			r += 1
			c -= 1
	return res


def downwardDigonal(N, A):
	t = []
	for i in range(N):
		for j in range(i + 1):
			t.append(A[j][i - j])
	for i in range(1, N):
		m = N - 1
		for j in range(i, N):
			t.append(A[j][m])
			m = m - 1
	return t


def downwardDigonal(N, A):
	d = {}
	s = set()
	for i in range(N):
		for j in range(N):
			if i + j not in s:
				s.add(i + j)
				l = []
				l.append(A[i][j])
				d[i + j] = l
			else:
				d[i + j].append(A[i][j])
	ans = []
	for i in range(len(s)):
		ans.extend(d[i])
	return ans


def downwardDigonal(N, A):
	b = []
	c = 1
	for i in range(2 * N - 1):
		if i <= N - 1:
			for (j, k) in zip(range(i + 1), range(i, -1, -1)):
				b.append(A[j][k])
		else:
			for (j, k) in zip(range(c, N), range(2 * N - 1 - N, c - 1, -1)):
				b.append(A[j][k])
			c += 1
	return b


from collections import defaultdict as dd

def downwardDigonal(N, A):
	d = dd(list)
	num = 0
	for i in range(N):
		for j in range(N):
			d[i + j].append(A[i][j])
	ans = []
	for i in d:
		for j in d[i]:
			ans.append(j)
	return ans


def downwardDigonal(n, li):
	i = 0
	j = 0
	ans = []
	while i < n and j < n:
		ans.append(li[i][j])
		x = i
		y = j
		while x + 1 < n and y - 1 >= 0:
			ans.append(li[x + 1][y - 1])
			x += 1
			y -= 1
		if j == n - 1:
			i += 1
		else:
			j += 1
	return ans


def downwardDigonal(N, A):
	s = []
	for i in range(N):
		j = i
		k = 0
		while j != -1:
			s.append(A[k][j])
			k = k + 1
			j = j - 1
	for i in range(1, N):
		j = i
		k = N - 1
		while j != N:
			s.append(A[j][k])
			j = j + 1
			k = k - 1
	return s


def downwardDigonal(N, A):
	list_a = []
	max_row = N + N - 2
	for sum in range(max_row + 1):
		for i in range(sum + 1):
			if i < N and sum - i < N:
				list_a.append(A[i][sum - i])
	return list_a


def downwardDigonal(N, A):
	ans = []
	for i in range(0, N):
		if i == 0:
			start = 0
		else:
			start = N - 1
		for j in range(start, N):
			x = i
			y = j
			while i != y + 1:
				ans.append(A[x][y])
				x = x + 1
				y = y - 1
	return ans


from collections import defaultdict

def downwardDigonal(N, A):
	d = defaultdict(list)
	for i in range(N):
		for j in range(N):
			d[i + j].append(A[i][j])
	res = []
	for i in d:
		for j in d[i]:
			res.append(j)
	return res


def downwardDigonal(N, A):
	lst = []
	for k in range(N):
		(i, j) = (0, k)
		while i < N and j >= 0:
			lst.append(A[i][j])
			i += 1
			j -= 1
	for k in range(1, N):
		(i, j) = (k, N - 1)
		while i < N and j >= 0:
			lst.append(A[i][j])
			i += 1
			j -= 1
	return lst


def downwardDigonal(N, A):
	arr = []
	for i in range(2 * N - 1):
		for j in range(max(0, i - N + 1), min(i + 1, N)):
			arr.append(A[j][i - j])
	return arr


def downwardDigonal(N, A):
	arr = []
	for row in range(2 * len(A) - 1):
		j = (row % N + 1) * (row // N)
		i = min(row, N - 1)
		while j >= 0 and i < N and (j < N) and (i >= 0):
			arr.append(A[j][i])
			j += 1
			i -= 1
	return arr


def downwardDigonal(N, A):
	res = []
	for i in range(N):
		row = 0
		col = i
		while col >= 0:
			res.append(A[row][col])
			row += 1
			col -= 1
	for j in range(1, N):
		row = j
		col = N - 1
		while row < N:
			res.append(A[row][col])
			row += 1
			col -= 1
	return res