You live in Geek land. Geek land can be seen as a grid of shape N x M.There are K enemy at K positions. Each enemy blocks the row and column to which it belongs. You have to find the largest continuous area that is not blocked.No two enemies share the same row or the same column.
Example 1:
Input:
N = 2
M = 2
K = 1
enemy[]={{2,2}}
Output:
1
Explanation:
Since only (1,1) cell is free from the enemy hence answer is 1.
 
Example 2:
Input:
N = 3
M = 3
K = 1
enemy[]={{3,3}}
Output:
4
Explanation:
The cells (1,1),(1,2) ,(2,1) and (2,2) are free hence answer =4.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function largestArea() which takes the size of geek land n,m and a 2-D matrix enemy of size k denoting the coordinates of the enemy's and need to return the largest area that is free.
Expected Time Complexity: O(KlogK)
Expected Auxiliary Space: O(K)
Constraints:
1 <= N,M <= 10^{4}
0<=K<=min(N,M)
1<=X_{i}<=N
1<=Y_{i}<=M

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Greedy algorithms

Starter code: from typing import List





from typing import List





class Solution:

    def largestArea(self,n:int,m:int,k:int, enemy : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		rows = []
		cols = []
		rows.append(0)
		cols.append(0)
		for i in enemy:
			rows.append(i[0])
			cols.append(i[1])
		rows.append(n + 1)
		cols.append(m + 1)
		rows.sort()
		cols.sort()
		maxRow = 0
		maxCol = 0
		for i in range(1, len(rows)):
			prev = rows[i - 1]
			curr = rows[i]
			maxRow = max(maxRow, curr - prev - 1)
		for j in range(1, len(cols)):
			prev = cols[j - 1]
			curr = cols[j]
			maxCol = max(maxCol, curr - prev - 1)
		return maxCol * maxRow


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		rows = []
		cols = []
		if k == 0:
			return n * m
		for i in e:
			rows.append(i[0])
			cols.append(i[1])
		rows.sort()
		cols.sort()
		le = max(rows[0] - 1, n - rows[k - 1])
		wid = max(cols[0] - 1, m - cols[k - 1])
		for i in range(1, k):
			le = max(le, rows[i] - rows[i - 1] - 1)
		for i in range(1, k):
			wid = max(wid, cols[i] - cols[i - 1] - 1)
		return le * wid


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		r = float('-inf')
		c = float('-inf')
		(resr, resc) = ([0, n + 1], [0, m + 1])
		for i in enemy:
			resr.append(i[0])
			resc.append(i[1])
		resr.sort()
		resc.sort()
		su = 0
		ma = 0
		for i in range(1, len(resr)):
			r = max(r, resr[i] - resr[i - 1] - 1)
		for i in range(1, len(resc)):
			c = max(c, resc[i] - resc[i - 1] - 1)
		return r * c


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		(row, col) = ([0, n + 1], [0, m + 1])
		for (r, c) in enemy:
			row.append(r)
			col.append(c)
		row.sort()
		col.sort()
		(rmax, cmax) = (float('-inf'), float('-inf'))
		for i in range(1, len(row)):
			rmax = max(rmax, row[i] - row[i - 1] - 1)
		for i in range(1, len(col)):
			cmax = max(cmax, col[i] - col[i - 1] - 1)
		return rmax * cmax


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return m * n
		rows = [0] * n
		col = [0] * m
		for i in range(0, len(enemy)):
			rows[enemy[i][0] - 1] = -1
			col[enemy[i][1] - 1] = -1
		maxrow = 0
		cntrow = 0
		for i in range(0, n):
			if rows[i] != -1:
				cntrow += 1
			else:
				cntrow = 0
			maxrow = max(maxrow, cntrow)
		maxcol = 0
		cntcol = 0
		for j in range(0, m):
			if col[j] != -1:
				cntcol += 1
			else:
				cntcol = 0
			maxcol = max(maxcol, cntcol)
		return maxrow * maxcol


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		enemx = enemy.copy()
		enemy.sort()
		enemx.sort(key=lambda x: x[1])
		maxy = 0
		i = 1
		for item in enemy:
			maxy = max(maxy, item[0] - i)
			i = item[0] + 1
		maxy = max(maxy, n - i + 1)
		maxx = 0
		i = 1
		for item in enemx:
			maxx = max(maxx, item[1] - i)
			i = item[1] + 1
		maxx = max(maxx, m - i + 1)
		return maxy * maxx


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return n * m
		enemy.sort(key=lambda x: x[0])
		a = max(enemy[0][0], n + 1 - enemy[-1][0])
		for i in range(k - 1):
			a = max(a, enemy[i + 1][0] - enemy[i][0])
		enemy.sort(key=lambda x: x[1])
		b = max(enemy[0][1], m + 1 - enemy[-1][1])
		for i in range(k - 1):
			b = max(b, enemy[i + 1][1] - enemy[i][1])
		return (a - 1) * (b - 1)


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		rows = [0] * n
		cols = [0] * m
		for i in range(len(enemy)):
			rows[enemy[i][0] - 1] += 1
			cols[enemy[i][1] - 1] += 1
		max_gap_row = 0
		max_gap_col = 0
		gap = 0
		for i in range(n):
			if rows[i] == 0:
				gap += 1
				max_gap_row = max(max_gap_row, gap)
			else:
				gap = 0
		gap = 0
		for i in range(m):
			if cols[i] == 0:
				gap += 1
				max_gap_col = max(max_gap_col, gap)
			else:
				gap = 0
		return max_gap_col * max_gap_row


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		(r, c) = ({}, {})
		for i in enemy:
			r[i[0]] = 1
			c[i[1]] = 1
		r[0] = 1
		c[0] = 1
		r[n + 1] = 1
		c[m + 1] = 1
		r = list(r.keys())
		c = list(c.keys())
		r.sort()
		c.sort()
		rm = []
		cm = []
		for i in range(1, len(r)):
			rm.append(r[i] - r[i - 1] - 1)
		for i in range(1, len(c)):
			cm.append(c[i] - c[i - 1] - 1)
		return max(cm) * max(rm)


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		x = []
		y = []
		for j in enemy:
			x.append(j[0])
		for j in enemy:
			y.append(j[1])
		x.append(0)
		x.append(n + 1)
		y.append(0)
		y.append(m + 1)
		x.sort()
		y.sort()
		maxx = 0
		maxy = 0
		for i in range(1, len(x)):
			maxx = max(maxx, x[i] - x[i - 1] - 1)
		for i in range(1, len(y)):
			maxy = max(maxy, y[i] - y[i - 1] - 1)
		return maxx * maxy


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		r = []
		c = []
		for i in range(len(enemy)):
			r.append(enemy[i][0])
			c.append(enemy[i][1])
		r.append(0)
		r.append(n + 1)
		c.append(0)
		c.append(m + 1)
		r.sort()
		c.sort()
		x = 0
		y = 0
		for i in range(1, len(r)):
			x = max(x, r[i] - r[i - 1] - 1)
			y = max(y, c[i] - c[i - 1] - 1)
		return x * y


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		a = []
		b = []
		for i in enemy:
			a.append(i[0])
			b.append(i[1])
		a.append(0)
		b.append(0)
		a.append(n + 1)
		b.append(m + 1)
		maxx = 0
		maxy = 0
		a.sort()
		b.sort()
		for i in range(1, len(a)):
			maxx = max(maxx, a[i] - a[i - 1] - 1)
		for i in range(1, len(b)):
			maxy = max(maxy, b[i] - b[i - 1] - 1)
		return maxx * maxy


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		tot = n * m
		if k == 0:
			return tot
		row = []
		col = []
		road = []
		coad = []
		for (i, j) in enemy:
			row.append(i)
			col.append(j)
		row = sorted(row)
		col = sorted(col)
		row.insert(0, 0)
		col.insert(0, 0)
		if row[-1] == n:
			row.append(row[-1] + 1)
		else:
			row.append(n + 1)
		if col[-1] == m:
			col.append(col[-1] + 1)
		else:
			col.append(m + 1)
		for k in range(len(row) - 1):
			road.append(row[k + 1] - row[k] - 1)
		for l in range(len(col) - 1):
			coad.append(col[l + 1] - col[l] - 1)
		return max(road) * max(coad)


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		a = [0 for i in range(n)]
		b = [0 for j in range(m)]
		for val in enemy:
			a[val[0] - 1] = -1
			b[val[1] - 1] = -1
		maxR = -1
		maxC = -1
		c1 = 0
		c2 = 0
		for i in a:
			if i == 0:
				c1 += 1
			else:
				c1 = 0
			maxR = max(maxR, c1)
		for i in b:
			if i == 0:
				c2 += 1
			else:
				c2 = 0
			maxC = max(maxC, c2)
		return maxR * maxC


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return n * m
		Nlst = [n + 1]
		Mlst = [m + 1]
		for ene in enemy:
			Nlst.append(ene[0])
			Mlst.append(ene[1])
		Nlst.sort()
		Mlst.sort()
		newNlst = [Nlst[0] - 1]
		newMlst = [Mlst[0] - 1]
		for i in range(1, len(Nlst)):
			newNlst.append(Nlst[i] - Nlst[i - 1] - 1)
			newMlst.append(Mlst[i] - Mlst[i - 1] - 1)
		newNlst.sort()
		newMlst.sort()
		return newNlst[-1] * newMlst[-1]


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		occupiedRows = []
		occupiedColumns = []
		for i in enemy:
			occupiedRows.append(i[0])
			occupiedColumns.append(i[1])
		occupiedRows.sort()
		occupiedColumns.sort()
		largeXDiff = 0
		lastX = 0
		for i in occupiedRows:
			diff = i - lastX - 1
			if diff > largeXDiff:
				largeXDiff = diff
			lastX = i
		diff = n - lastX
		if diff > largeXDiff:
			largeXDiff = diff
		largeYDiff = 0
		lastY = 0
		for i in occupiedColumns:
			diff = i - lastY - 1
			if diff > largeYDiff:
				largeYDiff = diff
			lastY = i
		diff = m - lastY
		if diff > largeYDiff:
			largeYDiff = diff
		return largeXDiff * largeYDiff


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		rows = [0, n + 1]
		cols = [0, m + 1]
		for x in range(0, len(enemy)):
			rows.append(enemy[x][0])
			cols.append(enemy[x][1])
		rows.sort(reverse=True)
		cols.sort(reverse=True)
		maxRow = 0
		maxCol = 0
		for x in range(0, len(rows) - 1):
			if rows[x] - rows[x + 1] > maxRow:
				maxRow = rows[x] - rows[x + 1]
			if cols[x] - cols[x + 1] > maxCol:
				maxCol = cols[x] - cols[x + 1]
		return (maxRow - 1) * (maxCol - 1)


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		r = []
		c = []
		max_r = 0
		max_c = 0
		r.append(0)
		c.append(0)
		for (row, col) in enemy:
			r.append(row)
			c.append(col)
		r.sort()
		c.sort()
		r.append(n + 1)
		c.append(m + 1)
		for i in range(1, len(r)):
			max_r = max(max_r, r[i] - r[i - 1] - 1)
		for i in range(1, len(c)):
			max_c = max(max_c, c[i] - c[i - 1] - 1)
		return max_r * max_c


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		rmax = 0
		cmax = 0
		if k == 0:
			return n * m
		enemy.sort(key=lambda x: x[0])
		i = 0
		for (r, c) in enemy:
			rmax = max(rmax, r - i - 1)
			i = r
		rmax = max(rmax, n - i)
		enemy.sort(key=lambda x: x[1])
		j = 0
		for (r, c) in enemy:
			cmax = max(cmax, c - j - 1)
			j = c
		cmax = max(cmax, m - j)
		return cmax * rmax


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		import heapq
		rows = set()
		columns = set()
		for e in enemy:
			if e[0] - 1 not in rows:
				rows.add(e[0] - 1)
			if e[1] - 1 not in columns:
				columns.add(e[1] - 1)
		row2 = []
		col2 = []
		count = 0
		for i in range(n):
			if i not in rows:
				count += 1
			else:
				heapq.heappush(row2, -count)
				count = 0
		heapq.heappush(row2, -count)
		count = 0
		for j in range(m):
			if j not in columns:
				count += 1
			else:
				heapq.heappush(col2, -count)
				count = 0
		heapq.heappush(col2, -count)
		return heapq.heappop(row2) * heapq.heappop(col2)


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		e_row = [False for _ in range(n)]
		e_col = [False for _ in range(m)]
		for i in range(k):
			e_row[enemy[i][0] - 1] = True
			e_col[enemy[i][1] - 1] = True
		maxRow = 0
		cntRow = 0
		for i in range(n):
			if not e_row[i]:
				cntRow = cntRow + 1
			else:
				cntRow = 0
			maxRow = max(maxRow, cntRow)
		maxCol = 0
		cntCol = 0
		for i in range(m):
			if not e_col[i]:
				cntCol = cntCol + 1
			else:
				cntCol = 0
			maxCol = max(maxCol, cntCol)
		return maxRow * maxCol


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemies: List[List[int]]) -> int:
		ex = []
		ey = []
		for enemy in enemies:
			ex.append(enemy[0])
			ey.append(enemy[1])
		ex.sort()
		ey.sort()
		sx = 0
		maxx = 0
		for x in ex:
			cx = x - sx
			if maxx < cx:
				maxx = cx
			sx = x
		cx = n + 1 - sx
		if maxx < cx:
			maxx = cx
		sy = 0
		maxy = 0
		for y in ey:
			cy = y - sy
			if maxy < cy:
				maxy = cy
			sy = y
		cy = m + 1 - sy
		if maxy < cy:
			maxy = cy
		return (maxx - 1) * (maxy - 1)


class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy) -> int:
		t = len(enemy)
		arr1 = []
		arr2 = []
		for i in range(t):
			arr1.append(enemy[i][0])
			arr2.append(enemy[i][1])
		arr1.append(0)
		arr1.append(n + 1)
		arr2.append(0)
		arr2.append(m + 1)
		arr1.sort()
		arr2.sort()
		l_max = -float('inf')
		b_max = -float('inf')
		for i in range(1, len(arr1)):
			l_max = max(l_max, arr1[i] - arr1[i - 1] - 1)
			b_max = max(b_max, arr2[i] - arr2[i - 1] - 1)
		return l_max * b_max


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		row = [0 for i in range(k + 2)]
		col = [0 for i in range(k + 2)]
		row[k + 1] = k + 1
		col[k + 1] = k + 1
		for i in range(k):
			row[i + 1] = enemy[i][0]
			col[i + 1] = enemy[i][1]
		row[k + 1] = n + 1
		col[k + 1] = m + 1
		row.sort()
		col.sort()
		max_row_len = 0
		max_col_len = 0
		for i in range(k + 1):
			max_row_len = max(max_row_len, row[i + 1] - row[i] - 1)
			max_col_len = max(max_col_len, col[i + 1] - col[i] - 1)
		return max_row_len * max_col_len


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		r = [0, n + 1]
		c = [0, m + 1]
		for (i, j) in enemy:
			r.append(i)
			c.append(j)
		r.sort()
		c.sort()
		ro = 0
		co = 0
		for i in range(1, len(r)):
			ro = max(ro, r[i] - r[i - 1] - 1)
		for i in range(1, len(c)):
			co = max(co, c[i] - c[i - 1] - 1)
		return co * ro


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return n * m
		rows = [0] * n
		col = [0] * m
		for i in range(k):
			rows[enemy[i][0] - 1] = -1
			col[enemy[i][1] - 1] = -1
		rm = 0
		i = 0
		j = 0
		cm = 0
		for s in range(n):
			if rows[s] != -1:
				i += 1
			else:
				i = 0
			if i > rm:
				rm = i
		for s in range(m):
			if col[s] != -1:
				j += 1
			else:
				j = 0
			if j > cm:
				cm = j
		return cm * rm


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		xs = sorted((e[0] - 1 for e in enemy))
		ys = sorted((e[1] - 1 for e in enemy))
		xs = xs + [n]
		ys = ys + [m]
		x_gap = xs[0]
		y_gap = ys[0]
		for i in range(len(xs) - 1):
			x_gap = max(x_gap, xs[i + 1] - xs[i] - 1)
		for j in range(len(ys) - 1):
			y_gap = max(y_gap, ys[j + 1] - ys[j] - 1)
		return x_gap * y_gap


class Solution:

	def largestArea(self, N, M, K, enemy):
		if K == 0:
			return N * M
		(rows, cols) = map(list, zip(*enemy))
		rows.sort()
		cols.sort()
		rows = [0] + rows + [N + 1]
		cols = [0] + cols + [M + 1]
		(mxr, mxc) = (0, 0)
		for i in range(1, K + 2):
			mxr = max(mxr, rows[i] - rows[i - 1] - 1)
			mxc = max(mxc, cols[i] - cols[i - 1] - 1)
		return mxr * mxc


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		cols = [0]
		rows = [0]
		for (i, j) in enemy:
			cols.append(j)
			rows.append(i)
		rows.append(n + 1)
		cols.append(m + 1)
		rows.sort()
		cols.sort()
		row_max = 0
		col_max = 0
		for i in range(1, len(rows)):
			row_max = max(rows[i] - rows[i - 1] - 1, row_max)
		for i in range(1, len(cols)):
			col_max = max(cols[i] - cols[i - 1] - 1, col_max)
		return row_max * col_max


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, emy: List[List[int]]) -> int:
		r = [0] * (k + 2)
		c = [0] * (k + 2)
		r[-1] = n + 1
		c[-1] = m + 1
		for i in range(1, k + 1):
			r[i] = emy[i - 1][0]
			c[i] = emy[i - 1][1]
		r.sort()
		c.sort()
		(mxr, mxc) = (0, 0)
		for i in range(1, k + 2):
			mxr = max(mxr, r[i] - r[i - 1] - 1)
			mxc = max(mxc, c[i] - c[i - 1] - 1)
		return mxr * mxc


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		a = [0, n + 1]
		b = [0, m + 1]
		ans = 0
		if k > 0:
			for i in enemy:
				a.append(i[0])
				b.append(i[1])
			a = sorted(list(set(a)))
			b = sorted(list(set(b)))
			x = 1
			y = 1
			if len(a) < len(b):
				for i in range(1, len(a)):
					if a[i] - a[i - 1] > x:
						x = a[i] - a[i - 1]
				for j in range(1, len(b)):
					if b[j] - b[j - 1] > y:
						y = b[j] - b[j - 1]
			else:
				for i in range(1, len(b)):
					if b[i] - b[i - 1] > x:
						x = b[i] - b[i - 1]
				for j in range(1, len(a)):
					if a[j] - a[j - 1] > y:
						y = a[j] - a[j - 1]
			ans = (x - 1) * (y - 1)
		else:
			ans = n * m
		return ans


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		row = [True] * n
		col = [True] * m
		for i in range(0, k):
			if row[enemy[i][0] - 1] == True:
				row[enemy[i][0] - 1] = False
			if col[enemy[i][1] - 1] == True:
				col[enemy[i][1] - 1] = False
		counti = 0
		countj = 0
		count = 0
		for i in range(0, n):
			if row[i] == True:
				count += 1
				if count > counti:
					counti = count
			else:
				count = 0
		count = 0
		for i in range(0, m):
			if col[i] == True:
				count += 1
				if count > countj:
					countj = count
			else:
				count = 0
		return counti * countj


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return n * m
		row = [0]
		col = [0]
		for (i, j) in enemy:
			row.append(i)
			col.append(j)
		row.append(n + 1)
		col.append(m + 1)
		row.sort()
		col.sort()
		mr = mc = 0
		for i in range(1, len(row)):
			mr = max(mr, row[i] - row[i - 1] - 1)
			mc = max(mc, col[i] - col[i - 1] - 1)
		return mr * mc


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		a = [0]
		b = [0]
		if k == 0:
			return n * m
		maxa = float('-inf')
		maxb = float('-inf')
		for i in range(k):
			a.append(enemy[i][0])
			b.append(enemy[i][1])
		a.append(n + 1)
		a.sort()
		b.append(m + 1)
		b.sort()
		for i in range(len(a) - 1):
			maxa = max(maxa, a[i + 1] - a[i] - 1)
			maxb = max(maxb, b[i + 1] - b[i] - 1)
		return maxa * maxb


from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		occ_row = list()
		occ_col = list()
		for i in enemy:
			occ_row.append(i[0])
			occ_col.append(i[1])
		occ_row.append(0)
		occ_row.append(n + 1)
		occ_col.append(0)
		occ_col.append(m + 1)
		occ_row.sort()
		occ_col.sort()
		(max_row_diff, max_col_diff) = (0, 0)
		c = 0
		for i in range(1, len(occ_row)):
			max_row_diff = max(max_row_diff, occ_row[i] - occ_row[i - 1])
		for i in range(1, len(occ_col)):
			max_col_diff = max(max_col_diff, occ_col[i] - occ_col[i - 1])
		return (max_row_diff - 1) * (max_col_diff - 1)


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return m * n
		rows = [0, n + 1]
		cols = [0, m + 1]
		for (r, c) in enemy:
			rows.append(r)
			cols.append(c)
		rows.sort()
		cols.sort()
		maxCol = maxRow = 0
		for i in range(1, k + 2):
			maxRow = max(maxRow, rows[i] - rows[i - 1] - 1)
			maxCol = max(maxCol, cols[i] - cols[i - 1] - 1)
		return maxRow * maxCol


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		blocked_rows = [pos[0] for pos in enemy]
		blocked_rows.extend([0, n + 1])
		sorted_rows = sorted(blocked_rows)
		blocked_cols = [pos[1] for pos in enemy]
		blocked_cols.extend([0, m + 1])
		sorted_cols = sorted(blocked_cols)
		max_span_between_rows = 0
		max_span_between_cols = 0
		for row in range(1, len(sorted_rows)):
			max_span_between_rows = max(max_span_between_rows, sorted_rows[row] - sorted_rows[row - 1] - 1)
		for col in range(1, len(sorted_cols)):
			max_span_between_cols = max(max_span_between_cols, sorted_cols[col] - sorted_cols[col - 1] - 1)
		return max_span_between_rows * max_span_between_cols


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return n * m
		(row, col) = ([], [])
		for (i, j) in enemy:
			row.append(i)
			col.append(j)
		row.sort()
		col.sort()
		rowdiff = max(row[0] - 1, n - row[k - 1])
		coldiff = max(col[0] - 1, m - col[k - 1])
		for i in range(1, k):
			rowdiff = max(rowdiff, row[i] - row[i - 1] - 1)
			coldiff = max(coldiff, col[i] - col[i - 1] - 1)
		return rowdiff * coldiff


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		r = [0] * n
		c = [0] * m
		for x in enemy:
			r[x[0] - 1] = -1
			c[x[1] - 1] = -1
		rm = 0
		cm = 0
		j = 0
		i = 0
		while j < n:
			if r[j] != -1:
				rm = max(rm, j - i + 1)
			else:
				i = j + 1
			j += 1
		j = i = 0
		while j < m:
			if c[j] != -1:
				cm = max(cm, j - i + 1)
			else:
				i = j + 1
			j += 1
		return rm * cm


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		row = [0] * n
		col = [0] * m
		for (i, j) in enemy:
			row[i - 1] = 1
			col[j - 1] = 1
		mxrow = 0
		ini = -1
		for i in range(n):
			if row[i]:
				mxrow = max(mxrow, i - ini - 1)
				ini = i
		mxrow = max(mxrow, n - ini - 1)
		mxcol = 0
		ini = -1
		for i in range(m):
			if col[i]:
				mxcol = max(mxcol, i - ini - 1)
				ini = i
		mxcol = max(mxcol, m - ini - 1)
		return mxrow * mxcol


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return n * m
		row = [0] * n
		col = [0] * m
		for i in range(len(enemy)):
			row[enemy[i][0] - 1] = -1
			col[enemy[i][1] - 1] = -1
		maxRow = 0
		countR = 0
		for i in range(len(row)):
			if row[i] != -1:
				countR += 1
				if countR > maxRow:
					maxRow = countR
			else:
				countR = 0
		maxCol = 0
		c = 0
		for i in range(len(col)):
			if col[i] != -1:
				c += 1
				if c > maxCol:
					maxCol = c
			else:
				c = 0
		return maxRow * maxCol


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		rows = [n + 1]
		cols = [m + 1]
		for (a, b) in enemy:
			rows.append(a)
			cols.append(b)
		rows.sort()
		cols.sort()
		rm = 0
		prev = 0
		for r in rows:
			rd = r - prev - 1
			if rd > rm:
				rm = rd
			prev = r
		cm = 0
		prev = 0
		for c in cols:
			cd = c - prev - 1
			if cd > cm:
				cm = cd
			prev = c
		return rm * cm


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return n * m
		dictr = {}
		dictc = {}
		for ene in enemy:
			dictr[ene[0] - 1] = True
			dictc[ene[1] - 1] = True
		a = 0
		b = 0
		maxa = 0
		maxb = 0
		for i in range(n + 1):
			if i in dictr or i == n:
				if a > maxa:
					maxa = a
				a = 0
			else:
				a += 1
		for j in range(m + 1):
			if j in dictc or j == m:
				if b > maxb:
					maxb = b
				b = 0
			else:
				b += 1
		return maxa * maxb


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		tot = n * m
		if k == 0:
			return tot
		(cols, rows) = (list(), list())
		ans = 0
		for (row, col) in enemy:
			rows.append(row)
			cols.append(col)
		rows.sort()
		cols.sort()
		(row_max, col_max) = (0, 0)
		for i in range(len(rows)):
			if i == 0:
				row_max = max(row_max, rows[i] - 1)
			else:
				row_max = max(row_max, rows[i] - rows[i - 1] - 1)
			if i == len(rows) - 1:
				row_max = max(row_max, n - rows[i])
		for i in range(len(cols)):
			if i == 0:
				col_max = max(col_max, cols[i] - 1)
			else:
				col_max = max(col_max, cols[i] - cols[i - 1] - 1)
			if i == len(cols) - 1:
				col_max = max(col_max, m - cols[i])
		return col_max * row_max


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		x = [0, n + 1]
		y = [0, m + 1]
		for e in enemy:
			x.append(e[0])
			y.append(e[1])
		x = sorted(x, reverse=True)
		y = sorted(y, reverse=True)
		for i in range(len(x) - 1):
			x[i] -= x[i + 1] + 1
			y[i] -= y[i + 1] + 1
		del x[-1]
		del y[-1]
		return max(x) * max(y)


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return n * m
		dictr = []
		dictc = []
		for ene in enemy:
			dictr.append(ene[0])
			dictc.append(ene[1])
		dictr.sort()
		dictc.sort()
		dictr.append(n + 1)
		dictc.append(m + 1)
		maxa = 0
		maxb = 0
		prev = 0
		for i in dictr:
			prev = i - prev
			if prev > maxa:
				maxa = prev
			prev = i
		prev = 0
		for i in dictc:
			prev = i - prev
			if prev > maxb:
				maxb = prev
			prev = i
		return (maxa - 1) * (maxb - 1)


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if k == 0:
			return int(m * n)
		(rows, cols) = list(zip(*enemy)) if enemy else [[], []]
		rows = sorted(rows)
		cols = sorted(cols)
		currow = 0
		maxrow = 0
		for i in range(k):
			maxrow = max(rows[i] - currow - 1, maxrow)
			currow = rows[i]
		maxrow = max(n - currow, maxrow)
		curcol = 0
		maxcol = 0
		for j in range(k):
			maxcol = max(cols[j] - curcol - 1, maxcol)
			curcol = cols[j]
		maxcol = max(m - curcol, maxcol)
		return int(maxrow * maxcol)


from typing import List
from typing import List

class Solution:

	def largestArea(self, n: int, m: int, k: int, enemy: List[List[int]]) -> int:
		if not k:
			return n * m
		row = []
		col = []
		for i in range(len(enemy)):
			row.append(enemy[i][0])
			col.append(enemy[i][1])
		row.sort()
		col.sort()
		rd = max(row[0] - 1, n - row[k - 1])
		cd = max(col[0] - 1, m - col[k - 1])
		for i in range(1, k):
			rd = max(rd, row[i] - row[i - 1] - 1)
		for i in range(1, k):
			cd = max(cd, col[i] - col[i - 1] - 1)
		return rd * cd