GeeksforGeeks 2 October Problem: Enemy

You live in Geek land. Geek land can be seen as a grid of shape N x M. Their 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 <= 104
0<=K<=min(N,M)
1<=Xi<=N
1<=Yi<=M

Code:

def largestArea(self,n:int,m:int,k:int, enemy : List[List[int]]) -> int:
        # code here
        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))
            
            
#This Code Is Written By Upendra Charasiya

Comments

Popular posts from this blog

Computer game, This is the Problem statement given in the techgig Platform.