Suppose you have a Matrix size n*n, and given an integer k and a set of coordinates arr of size k*2. Initially, the matrix contains only 0. You are given k tasks and for each task, you are given two coordinates (r = arr[i][0],c = arr[i][1]) [1 based index r and c]. Where coordinates (r,c) denotes r^{th }row and c^{th }column of the given matrix.
You have to perform each task sequentially in the given order. For each task, You have to put 1 in all cells of r^{th} row  and all cells of c^{th} column.
After each task, You have to calculate the number of 0 present in the matrix and return it.
Example 1:
Input:
n = 3, k= 3
arr =
{{2, 2},
 {2, 3},
 {3, 2}}
Output: 4 2 1
Explanation: 
After 1st Operation, all the 2nd row
and all the 2nd column will be filled by
1. So remaning cell with value 0 will be 4
After 2nd Operation, all the 2nd row and all
the 3rd column will be filled by 1. So 
remaning cell with value 0 will be 2.
After 3rd Operation cells having value 0 will
be 1.
Example 2:
Input:
n = 2, k = 2
arr = 
{{1, 2},
 {1, 1}}
Output: 1 0
Explanation: 
After 1st Operation, all the 1st row and 
all the 2nd column will be filled by 1. 
So remaning cell with value 0 will be 1.
After 2nd Operation, all the 1st row and 
all the 1st column will be filled by 1. 
So remaning cell with value 0 will be 0. 
Your Task:
The task is to complete the function countZero(), which takes parameter n, size of
the matrix, k no of operation and array arr[][], which denotes the position of the cells.
You have to return an array that contains all the results.
Expected Time Complexity: O( k ).
Expected Auxiliary Space: O( n+n+k ).
Constraints:
1 <= n, k <= 10^{5}
1 <= r, c <= n

Source: geeksforgeeks | Difficulty: EASY
Tags: Matrices

Data structures

String algorithms

Starter code: #User function Template for python3



class Solution():

    def countZero(self, n, k ,arr):

        #your code here

Solutions:
class Solution:

	def countZero(self, n, k, arr):
		r = {}
		c = {}
		ans = []
		total = n * n
		nr = 0
		nc = 0
		for i in range(k):
			tim = arr[i]
			if i == 0:
				r[tim[0]] = 1
				c[tim[1]] = 1
				total -= 2 * n - 1
				nr += 1
				nc += 1
				ans.append(total)
			else:
				if tim[0] not in r:
					r[tim[0]] = 1
					total -= n - nc
					nr += 1
				else:
					pass
				if tim[1] not in c:
					c[tim[1]] = 1
					total -= n - nr
					nc += 1
				else:
					pass
				ans.append(total)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		ans = []
		Row_vector = [0] * (n + 1)
		Column_vector = [0] * (n + 1)
		row_count = 0
		column_count = 0
		for i in range(k):
			r = arr[i][0]
			c = arr[i][1]
			if Row_vector[r] == 0:
				row_count += 1
				Row_vector[r] = 1
			if Column_vector[c] == 0:
				column_count += 1
				Column_vector[c] = 1
			ans.append(n * n - row_count * n - column_count * n + row_count * column_count)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		r_set = set()
		c_set = set()
		res = list()
		for (i, j) in arr:
			r_set.add(i)
			c_set.add(j)
			res.append((n - len(r_set)) * (n - len(c_set)))
		return res


class Solution:

	def countZero(self, n, k, arr):
		num_0s = n * n
		rows = set()
		cols = set()
		ans = []
		for (r, c) in arr:
			if r not in rows:
				num_0s -= n - len(cols)
				rows.add(r)
			if c not in cols:
				num_0s -= n - len(rows)
				cols.add(c)
			ans.append(num_0s)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		row = set()
		col = set()
		answer = list()
		for a in arr:
			row.add(a[0])
			col.add(a[1])
			answer.append(pow(n, 2) - (len(row) * n + len(col) * n - len(row) * len(col)))
		return answer


class Solution:

	def countZero(self, n, k, arr):
		rows = set()
		cols = set()
		answer = []
		for (r, c) in arr:
			rows.add(r)
			cols.add(c)
			answer.append((n - len(rows)) * (n - len(cols)))
		return answer


class Solution:

	def countZero(self, n, k, arr):
		zeros = n ** 2
		answer = []
		rows = set()
		cols = set()
		for (r, c) in arr:
			if r not in rows:
				zeros -= n - len(cols)
				rows |= {r}
			if c not in cols:
				zeros -= n - len(rows)
				cols |= {c}
			answer.append(zeros)
		return answer


class Solution:

	def countZero(self, n, k, arr):
		(total, row, col, ans) = (n * n, set(), set(), [])
		for (r, c) in arr:
			row.add(r)
			col.add(c)
			ans.append(total - len(row) * n - len(col) * (n - len(row)))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		filled_rows = set()
		filled_cols = set()
		ans = []
		for (r, c) in arr:
			filled_rows.add(r)
			filled_cols.add(c)
			ans.append((n - len(filled_cols)) * (n - len(filled_rows)))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		(total, visit_row, visit_col, ans) = (n * n, set(), set(), [])
		for (r, c) in arr:
			visit_row.add(r)
			visit_col.add(c)
			ans.append(total - len(visit_row) * n - len(visit_col) * (n - len(visit_row)))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		rowSet = set()
		colSet = set()
		ans = []
		for i in arr:
			rowSet.add(i[0])
			colSet.add(i[1])
			ct1 = n * len(rowSet) + n * len(colSet) - len(rowSet) * len(colSet)
			ans.append(n ** 2 - ct1)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		arr2 = {9}
		arr3 = {9}
		arr2.remove(9)
		arr3.remove(9)
		result = []
		sum2 = sum3 = 0
		arr2.add(arr[0][0])
		arr3.add(arr[0][1])
		sum2 = 1
		sum3 = 1
		countA = n * n
		count = countA - 2 * n + 1
		for i in range(k):
			arr2.add(arr[i][0])
			sum2 = len(arr2)
			arr3.add(arr[i][1])
			sum3 = len(arr3)
			count = countA - sum2 * n - sum3 * n + sum3 * sum2
			result.append(count)
		return result


class Solution:

	def countZero(self, n, k, arr):
		rows = set((i for i in range(1, n + 1)))
		colums = set((i for i in range(1, n + 1)))
		output = []
		for (r, c) in arr:
			rows.discard(r)
			colums.discard(c)
			output.append(len(rows) * len(colums))
		return output


class Solution:

	def countZero(self, n, k, arr):
		rset = set()
		cset = set()
		res = []
		for (a, b) in arr:
			rset.add(a)
			cset.add(b)
			res.append((n - len(rset)) * (n - len(cset)))
		return res


class Solution:

	def countZero(self, n, k, arr):
		zeros = n * n - (2 * n - 1)
		(rows, cols) = ({arr[0][0]: None}, {arr[0][1]: None})
		zero_arr = []
		for i in range(1, len(arr)):
			zero_arr.append(zeros)
			(row, col) = (arr[i][0], arr[i][1])
			if row not in rows:
				zeros -= n - len(cols)
				rows.update({row: None})
			if col not in cols:
				zeros -= n - len(rows)
				cols.update({col: None})
		zero_arr.append(zeros)
		return zero_arr


class Solution:

	def countZero(self, n, k, arr):
		ans = []
		rows = set()
		cols = set()
		for i in range(k):
			temp = arr[i]
			row = temp[0]
			col = temp[1]
			rows.add(row)
			cols.add(col)
			ans.append(n * n - n * (len(cols) + len(rows)) + len(cols) * len(rows))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		tc = n * n
		rows = set()
		cols = set()
		ans = []
		for i in range(k):
			r = arr[i][0] - 1
			c = arr[i][1] - 1
			if r not in rows and c not in cols:
				used = 2 * n - len(cols) - len(rows) - 1
				rem = tc - used
				ans.append(rem)
				tc -= used
				rows.add(r)
				cols.add(c)
			elif r in rows and c in cols:
				ans.append(tc)
			elif r in rows:
				used = n - len(rows)
				rem = tc - used
				ans.append(rem)
				tc -= used
				cols.add(c)
			else:
				used = n - len(cols)
				rem = tc - used
				ans.append(rem)
				tc -= used
				rows.add(r)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		rows = [0 for _ in range(n)]
		cols = [0 for _ in range(n)]
		count = n * n
		cr = 0
		cc = 0
		result = [0 for _ in range(k)]
		for i in range(k):
			(r, c) = (arr[i][0], arr[i][1])
			if not rows[r - 1]:
				count -= n
				rows[r - 1] = 1
				cr += 1
				count += cc
			if not cols[c - 1]:
				count -= n
				cols[c - 1] = 1
				cc += 1
				count += cr
			result[i] = count
		return result


class Solution:

	def countZero(self, n, k, arr):
		z = n * n
		incR = 0
		incC = 0
		dr = {}
		dc = {}
		solve = []
		for x in arr:
			(i, j) = (x[0], x[1])
			if not dr.get(i, False):
				z -= n - incC
				incR += 1
			if not dc.get(j, False):
				z -= n - incR
				incC += 1
			dc[j] = 1
			dr[i] = 1
			solve.append(z)
		return solve


class Solution:

	def countZero(self, n, k, arr):
		updated_rows = set()
		updated_cols = set()
		count = 0
		res = []
		for i in range(k):
			(r, c) = arr[i]
			if r not in updated_rows:
				updated_rows.add(r)
				count += n - len(updated_cols)
			if c not in updated_cols:
				updated_cols.add(c)
				count += n - len(updated_rows)
			res.append(n * n - count)
		return res


class Solution:

	def countZero(self, n, k, arr):
		row = set([i for i in range(n)])
		column = set([i for i in range(n)])
		array = []
		c_diff = n
		r_diff = n
		n = n * n
		for i in range(k):
			r = arr[i][0] - 1
			c = arr[i][1] - 1
			if r in row and c in column:
				n = n - (c_diff + r_diff - 1)
				row.remove(r)
				column.remove(c)
				c_diff -= 1
				r_diff -= 1
			elif r in row:
				n -= r_diff
				row.remove(r)
				c_diff -= 1
			elif c in column:
				n -= c_diff
				column.remove(c)
				r_diff -= 1
			array.append(n)
		return array


class Solution:

	def countZero(self, n, k, arr):
		N = n * n
		rc = set()
		cc = set()
		ans = []
		for (r, c) in arr:
			rc.add(r)
			cc.add(c)
			temp = len(rc) * n
			temp1 = len(cc) * (n - len(rc))
			ans.append(N - temp - temp1)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		ans = []
		rs = set()
		cs = set()
		for (i, j) in arr:
			rs.add(i)
			cs.add(j)
			ans.append((n - len(rs)) * (n - len(cs)))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		m_r = {}
		m_c = {}
		zeroes = n * n
		rows_set = 0
		cols_set = 0
		ans = []
		for item in arr:
			if item[0] not in m_r:
				m_r[item[0]] = 1
				zeroes -= n - cols_set
				rows_set += 1
			if item[1] not in m_c:
				m_c[item[1]] = 1
				zeroes -= n - rows_set
				cols_set += 1
			ans.append(zeroes)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		final_arr = []
		row_set = set()
		col_set = set()
		for (i, j) in arr:
			row_set.add(i)
			col_set.add(j)
			final_arr.append((n - len(row_set)) * (n - len(col_set)))
		return final_arr


class Solution:

	def countZero(self, n, k, arr):
		ro = {}
		co = {}
		ans = []
		for i in range(0, k):
			r = arr[i][0] - 1
			c = arr[i][1] - 1
			ro[r] = 1
			co[c] = 1
			nr = len(ro)
			nc = len(co)
			total = n * n - (n * nr + n * nc - nr * nc)
			ans.append(total)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		t_z = n * n
		r_f = 0
		c_f = 0
		t_o = 0
		rows = {}
		cols = {}
		ans = []
		for i in arr:
			rows[i[0]] = 0
			cols[i[1]] = 0
		for i in arr:
			if rows[i[0]] == 0:
				r_f += 1
				rows[i[0]] = 1
				t_o += n - c_f
			if cols[i[1]] == 0:
				t_o += n - r_f
				c_f += 1
				cols[i[1]] = 1
			t_z = n * n - t_o
			ans.append(t_z)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		rows = {}
		cols = {}
		r = c = 0
		freecells = n * n
		ans = [0] * k
		for i in range(k):
			if arr[i][0] not in rows:
				r += 1
				freecells -= n - c
				rows[arr[i][0]] = True
			if arr[i][1] not in cols:
				c += 1
				freecells -= n - r
				cols[arr[i][1]] = True
			ans[i] = freecells
		return ans


class Solution:

	def countZero(self, n, k, arr):
		row = set()
		col = set()
		(r, c) = (n, n)
		curr_res = n * n
		ans = [0] * k
		for i in range(k):
			x = arr[i][0]
			y = arr[i][1]
			if x not in row and y not in col:
				curr_res = curr_res - r - c + 1
				c -= 1
				r -= 1
			if x in row and y not in col:
				curr_res = curr_res - r
				c -= 1
			if x not in row and y in col:
				curr_res = curr_res - c
				r -= 1
			ans[i] = curr_res
			row.add(x)
			col.add(y)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		output = []
		zeros = n * n
		used_rows = [0] * n
		used_cols = [0] * n
		row_count = 0
		col_count = 0
		for j in range(k):
			r = arr[j][0]
			c = arr[j][1]
			if not used_rows[r - 1]:
				zeros -= n - col_count
				used_rows[r - 1] = 1
				row_count += 1
			if not used_cols[c - 1]:
				zeros -= n - row_count
				used_cols[c - 1] = 1
				col_count += 1
			output.append(zeros)
		return output


class Solution:

	def countZero(self, n, k, arr):
		row = [0] * (n + 1)
		col = [0] * (n + 1)
		result = []
		total = n * n
		rk = 0
		ck = 0
		for coordinate in arr:
			(r, c) = coordinate
			if row[r] == 0 and col[c] == 0:
				total -= n + n - 1 - rk - ck
				result.append(total)
				rk += 1
				ck += 1
				row[r] = 1
				col[c] = 1
			elif row[r] == 1 and col[c] == 1:
				result.append(total)
			elif row[r] == 1:
				total -= n - rk
				result.append(total)
				ck += 1
				col[c] = 1
			elif col[c] == 1:
				total -= n - ck
				result.append(total)
				rk += 1
				row[r] = 1
		return result


class Solution:

	def countZero(self, n, k, arr):
		row = dict()
		col = dict()
		for i in range(n):
			row[i + 1] = 0
			col[i + 1] = 0
		(r, c) = (0, 0)
		a = []
		for i in range(k):
			if row[arr[i][0]] == 0:
				r = r + 1
				row[arr[i][0]] = 1
			if col[arr[i][1]] == 0:
				c = c + 1
				col[arr[i][1]] = 1
			a.append(n ** 2 - r * n - c * n + r * c)
		return a


import math

class Solution:

	def countZero(self, n, k, arr):
		res = []
		r = set((i for i in range(1, 1 + n)))
		c = set((i for i in range(1, 1 + n)))
		for ele in arr:
			(row, col) = (ele[0], ele[1])
			if row in r:
				r.remove(row)
			if col in c:
				c.remove(col)
			res.append(len(r) * len(c))
		return res


class Solution:

	def countZero(self, n, k, arr):
		rowvis = {}
		colvis = {}
		ans = []
		for i in range(0, k):
			currrow = arr[i][0]
			currcol = arr[i][1]
			rowvis[currrow] = True
			colvis[currcol] = True
			visitedrows = len(rowvis)
			visitedcols = len(colvis)
			remain = n * n - visitedrows * n - visitedcols * n + visitedrows * visitedcols
			ans.append(remain)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		rowSet = set()
		colSet = set()
		ones = 0
		total = n * n
		res = [0] * k
		for (i, (row, col)) in enumerate(arr):
			if not rowSet and (not colSet):
				ones += 2 * n - 1
				rowSet.add(row)
				colSet.add(col)
				res[i] = total - ones
				continue
			if row not in rowSet:
				ones += n - len(colSet)
			rowSet.add(row)
			if col not in colSet:
				ones += n - len(rowSet)
			colSet.add(col)
			res[i] = total - ones
		return res


class Solution:

	def countZero(self, n, k, arr):
		res = []
		s = n * n
		r = [0 for _ in range(n)]
		lr = 0
		c = [0 for _ in range(n)]
		lc = 0
		i = 0
		while i < k:
			if lr < n:
				if r[arr[i][0] - 1] == 0:
					r[arr[i][0] - 1] = 1
					lr += 1
					s -= n - lc
			if lc < n:
				if c[arr[i][1] - 1] == 0:
					c[arr[i][1] - 1] = 1
					lc += 1
					s -= n - lr
			res.append(s)
			i += 1
		return res


class Solution:

	def countZero(self, n, k, arr):
		(row, col) = (0, 0)
		ans = []
		(s1, s2) = (set(), set())
		for i in arr:
			if i[0] not in s1:
				s1.add(i[0])
				row += 1
			if i[1] not in s2:
				s2.add(i[1])
				col += 1
			ans.append(n * n - (n * row + n * col - row * col))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		total = n * n
		vr = set()
		vm = set()
		r = []
		for i in range(k):
			vr.add(arr[i][0])
			vm.add(arr[i][1])
			t = len(vr) * n + (n - len(vr)) * len(vm)
			r.append(n ** 2 - t)
		return r


class Solution:

	def countZero(self, n, k, arr):
		(r, c) = (0, 0)
		ans = []
		(s1, s2) = (set(), set())
		for i in arr:
			if i[0] not in s1:
				s1.add(i[0])
				r += 1
			if i[1] not in s2:
				s2.add(i[1])
				c += 1
			ans.append(n * n - (n * r + n * c - r * c))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		vr = set(range(1, n + 1))
		vc = set(range(1, n + 1))
		res = []
		for (r, c) in arr:
			if r in vr:
				vr.remove(r)
			if c in vc:
				vc.remove(c)
			res.append(len(vr) * len(vc))
		return res


class Solution:

	def countZero(self, n, k, arr):
		l1 = [0] * (n + 1)
		l2 = [0] * (n + 1)
		l = []
		r = 0
		a = n * n
		c = 0
		y = 0
		for i in arr:
			for j in i:
				if y == 0:
					if l1[j] == 0:
						l1[j] = j
						a = a - (n - c)
						y += 1
						r += 1
					else:
						y += 1
				elif l2[j] == 0:
					l2[j] = j
					a = a - (n - r)
					y -= 1
					c += 1
				else:
					y -= 1
			l.append(a)
		return l


class Solution:

	def countZero(self, n, k, arr):
		zero = []
		r = n
		c = n
		col = []
		row = []
		zero_number = 0
		p = 0
		col = [0] * n
		row = [0] * n
		for item in arr:
			if p == 0:
				zero_number = n * n - 2 * n + 1
				r = n - 1
				c = n - 1
				zero.append(zero_number)
				row[item[0] - 1] = 1
				col[item[1] - 1] = 1
				p = p + 1
			else:
				if row[item[0] - 1] == 1 and col[item[1] - 1] == 1:
					zero.append(zero_number)
					continue
				if row[item[0] - 1] == 1 and col[item[1] - 1] == 0:
					zero_number = zero_number - c
					zero.append(zero_number)
					r = r - 1
					col[item[1] - 1] = 1
					continue
				if row[item[0] - 1] == 0 and col[item[1] - 1] == 1:
					zero_number = zero_number - r
					zero.append(zero_number)
					c = c - 1
					row[item[0] - 1] = 1
					continue
				if row[item[0] - 1] == 0 and col[item[1] - 1] == 0:
					zero_number = zero_number - r - c + 1
					zero.append(zero_number)
					row[item[0] - 1] = 1
					col[item[1] - 1] = 1
					r = r - 1
					c = c - 1
					continue
		return zero


class Solution:

	def countZero(self, n, k, a):
		rm = [0] * n
		cm = [0] * n
		rc = 0
		cc = 0
		ans = n * n
		b = []
		for i in range(k):
			(r, c) = (a[i][0], a[i][1])
			c1 = 0
			if rm[r - 1] == 0:
				c1 += 1
			if cm[c - 1] == 0:
				c1 += 1
			if c1 == 0:
				ans -= 0
			elif c1 == 1 and rm[r - 1] == 0:
				ans -= n
				ans += cc
			elif c1 == 1 and cm[c - 1] == 0:
				ans -= n
				ans += rc
			else:
				ans -= 2 * n - 1
				ans += rc
				ans += cc
			if rm[r - 1] == 0:
				rc += 1
			if cm[c - 1] == 0:
				cc += 1
			rm[r - 1] = 1
			cm[c - 1] = 1
			b.append(ans)
		return b


class Solution:

	def countZero(self, n, k, arr):
		(l, r) = (set(), set())
		res = []
		for (i, j) in arr:
			l.add(i)
			r.add(j)
			res.append((n - len(l)) * (n - len(r)))
		return res


class Solution:

	def countZero(self, n, k, arr):
		row = [-1] * n
		col = [-1] * n
		total = n * n
		count = 0
		lis = []
		count_row = 0
		count_col = 0
		for i in range(k):
			if row[arr[i][0] - 1] == -1:
				count += n - count_col
				count_row += 1
				row[arr[i][0] - 1] = 0
			if col[arr[i][1] - 1] == -1:
				count += n - count_row
				count_col += 1
				col[arr[i][1] - 1] = 0
			lis.append(total - count)
		return lis


class Solution:

	def countZero(self, n, k, arr):
		dict1 = dict()
		dict2 = dict()
		total = n ** 2
		list1 = []
		rowz = 0
		colz = 0
		for i in arr:
			row = i[0] - 1
			col = i[1] - 1
			if row not in dict1:
				total = total - (n - colz)
				dict1[row] = 1
				rowz += 1
			if col not in dict2:
				dict2[col] = 1
				total = total - (n - rowz)
				colz += 1
			list1.append(total)
		return list1


class Solution:

	def countZero(self, n, k, arr):
		d1 = {}
		d2 = {}
		for i in range(1, n + 1):
			d1[i] = 0
			d2[i] = 0
		c = 0
		r = w = 0
		for i in arr:
			if d1[i[0]] == 0:
				d1[i[0]] = n
				r += 1
				c += n - w
			if d2[i[1]] == 0:
				d2[i[1]] = n
				w += 1
				c += n - r
			print(n * n - c, end=' ')
		return []


class Solution:

	def countZero(self, n, k, arr):
		(r, c) = (n, n)
		r_set = set()
		c_set = set()
		res = list()
		for (i, j) in arr:
			if i not in r_set:
				r_set.add(i)
				r -= 1
			if j not in c_set:
				c_set.add(j)
				c -= 1
			res.append(r * c)
		return res


class Solution:

	def countZero(self, n, k, arr):
		rows = set()
		cols = set()
		res = []
		for i in range(k):
			if arr[i][0] <= n:
				rows.add(arr[i][0])
			if arr[i][1] <= n:
				cols.add(arr[i][1])
			res.append(n * n - (len(rows) * n + len(cols) * n - len(rows) * len(cols)))
		return res


class Solution:

	def countZero(self, n, k, arr):
		freeCell = n * n
		filledRow = 0
		filledCol = 0
		ans = []
		rowMap = dict()
		colMap = dict()
		for i in range(0, k):
			row = arr[i][0] - 1
			col = arr[i][1] - 1
			if col not in colMap:
				colMap[col] = 1
				filledCol += 1
				freeCell = freeCell - n + filledRow
			if row not in rowMap:
				rowMap[row] = 1
				filledRow += 1
				freeCell = freeCell - n + filledCol
			ans.append(freeCell)
		return ans


class Solution:

	def countZero(self, n, k, arr):
		l = []
		r = set()
		c = set()
		t = n * n
		for i in range(k):
			if arr[i][0] not in r:
				t = t - n + len(c)
				r.add(arr[i][0])
			if arr[i][1] not in c:
				t = t - n + len(r)
				c.add(arr[i][1])
			l.append(t)
		return l


class Solution:

	def countZero(self, n, k, arr):
		ind = {i: 1 for i in range(1, 2 * (n + 1))}
		(i, j) = (n, n)
		res = []
		for (l, m) in arr:
			if ind[l]:
				ind[l] = 0
				i -= 1
			if ind[m + n]:
				ind[m + n] = 0
				j -= 1
			res.append(i * j)
		return res


class Solution:

	def countZero(self, n, k, arr):
		already_filled_rows = 0
		already_filled_cols = 0
		zeros = n * n
		rows = {}
		cols = {}
		res = []
		for i in range(k):
			r = arr[i][0]
			c = arr[i][1]
			if rows.get(r) == None:
				rows[r] = True
				total_filled_one_in_row = n - already_filled_cols
				zeros = zeros - total_filled_one_in_row
				already_filled_rows += 1
			if cols.get(c) == None:
				cols[c] = True
				total_filled_one_in_col = n - already_filled_rows
				zeros = zeros - total_filled_one_in_col
				already_filled_cols += 1
			res.append(zeros)
		return res


class Solution:

	def countZero(self, n, k, arr):
		rc = [0] * n
		cc = [0] * n
		ans = [0] * k
		N = n * n
		visitedr = 0
		visitedc = 0
		for i in range(k):
			r = arr[i][0] - 1
			c = arr[i][1] - 1
			if rc[r] == 0:
				N = N - (n - visitedc)
				rc[r] = 1
				visitedr += 1
			if cc[c] == 0:
				N = N - (n - visitedr)
				cc[c] = 1
				visitedc += 1
			ans[i] = N
		return ans


class Solution:

	def countZero(self, n, k, a):
		ans = []
		row = set()
		col = set()
		for i in range(k):
			row.add(a[i][0])
			col.add(a[i][1])
			ans.append(n * n + len(row) * len(col) - n * len(row) - n * len(col))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		res = []
		rows = [False] * n
		cols = [False] * n
		filled_rows = 0
		filled_cols = 0
		for i in range(k):
			(r, c) = arr[i]
			if not rows[r - 1]:
				filled_rows += 1
				rows[r - 1] = True
			if not cols[c - 1]:
				filled_cols += 1
				cols[c - 1] = True
			res.append(n * n - (filled_rows * n + filled_cols * n - filled_rows * filled_cols))
		return res


class Solution:

	def countZero(self, n, k, arr):
		l = len(arr)
		c = r = n
		t = n * n
		dictr = {}
		dictc = {}
		ans = []
		i = 0
		while i < l:
			if arr[i][0] not in dictr and arr[i][1] not in dictc:
				t = t - (c + r - 1)
				ans.append(t)
				r -= 1
				c -= 1
				dictr[arr[i][0]] = 1
				dictc[arr[i][1]] = 1
			elif arr[i][0] not in dictr:
				dictr[arr[i][0]] = 1
				t -= r
				c -= 1
				ans.append(t)
			elif arr[i][1] not in dictc:
				dictc[arr[i][1]] = 1
				t -= c
				r -= 1
				ans.append(t)
			else:
				ans.append(t)
			i += 1
		return ans


class Solution:

	def countZero(self, n, k, arr):
		l = []
		r = {}
		c = {}
		rows = 0
		col = 0
		s = n * n
		for i in arr:
			if i[0] not in r:
				r[i[0]] = 1
				rows += 1
				s = s - (n - col)
			else:
				r[i[0]] += 1
			if i[1] not in c:
				c[i[1]] = 1
				col += 1
				s = s - (n - rows)
			else:
				c[i[1]] += 1
			l.append(s)
		return l


class Solution:

	def countZero(self, n, k, arr):
		matr = set()
		matc = set()
		ans = []
		for el in arr:
			r = el[0]
			c = el[1]
			matr.add(r)
			matc.add(c)
			ans.append((n - len(matr)) * (n - len(matc)))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		(rs, cs) = (set(), set())

		def zeros(rs, cs):
			return n * n - len(rs) * n - len(cs) * n + len(rs) * len(cs)
		ans = []
		for (r, c) in arr:
			rs.add(r)
			cs.add(c)
			ans.append(zeros(rs, cs))
		return ans


class Solution:

	def countZero(self, n, k, arr):
		(r, c) = ([0] * n, [0] * n)
		(ans, rc, cc) = ([], 0, 0)
		total = n * n
		for i in range(len(arr)):
			if r[arr[i][0] - 1] == 0:
				rc += 1
				r[arr[i][0] - 1] = 1
			if c[arr[i][1] - 1] == 0:
				cc += 1
				c[arr[i][1] - 1] = 1
			ans.append(total - cc * n - rc * (n - cc))
		return ans