Given two integers L and W representing the dimensions of a grid, and two arrays X[] and Y[] of length N denoting the number of towers present on the grid at positions (X[i], Y[i]), where (0 <= i <= N – 1). The task is to find the largest unbounded area in the field which is not defended by the towers.
Examples:
Input: L = 15, W = 8, N = 3 X[] = {3, 11, 8} Y[] = {8, 2, 6}
Output: 12
Explanation:
The coordinates of the towers are (3, 8), (11, 2) and (8, 6).
Observe that the largest area of the grid which is not guarded by any of the towers is within the cells (4, 3), (7, 3), (7, 5) and (4, 5). Hence, the area for that part is 12.Input: L = 3, W = 3, N = 1 X[] = {1} Y[] = {1}
Output: 4
Explanation:
Observe that the largest area of the grid which is not guarded by any of the towers is 4.
Naive Approach: Follow the steps below to solve the problem:
- Initialize a matrix of dimensions L * W with 0s.
- Traverse X[] and Y[], and for every (X[i], Y[i]), mark all the cells in the X[i]th Row and Y[i]th Column by 1, to denote being guarded by the tower at (X[i], Y[i]).
- Then traverse the matrix and for each cell, and find the largest sub-matrix which is left unguarded, i.e. largest submatrix consisting of 0s. Print the corresponding area.
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Efficient Approach: The above approach can be optimized using the following Greedy technique:
- Sort both the lists of co-ordinates X[] and Y[].
- Calculate the empty spaces between the x co-ordinates, i.e. dX[] = {X1, X2 – X1, …., XN – X(N-1), (L+1) – XN }. Similarly, calculate the spaces between y co-ordinates, dY[] = {Y1, Y2 – Y1, …., YN – Y(N-1), (W + 1) – YN }.
- Traverse dX[] and dY[] and calculate their respective maximums.
- Calculate the product of their maximums and print it as the required longest unbounded area.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <algorithm>#include <iostream>using namespace std;// Function to calculate the largest// area unguarded by towersvoid maxArea(int point_x[], int point_y[], int n, int length, int width){ // Sort the x-coordinates of the list sort(point_x, point_x + n); // Sort the y-coordinates of the list sort(point_y, point_y + n); // dx --> maximum uncovered // tiles in x coordinates int dx = point_x[0]; // dy --> maximum uncovered // tiles in y coordinates int dy = point_y[0]; // Calculate the maximum uncovered // distances for both x and y coordinates for (int i = 1; i < n; i++) { dx = max(dx, point_x[i] - point_x[i - 1]); dy = max(dy, point_y[i] - point_y[i - 1]); } dx = max(dx, (length + 1) - point_x[n - 1]); dy = max(dy, (width + 1) - point_y[n - 1]); // Largest unguarded area is // max(dx)-1 * max(dy)-1 cout << (dx - 1) * (dy - 1); cout << endl;}// Driver Codeint main(){ // Length and width of the grid int length = 15, width = 8; // No of guard towers int n = 3; // Array to store the x and // y coordinates int point_x[] = { 3, 11, 8 }; int point_y[] = { 8, 2, 6 }; // Function call maxArea(point_x, point_y, n, length, width); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to calculate the largest// area unguarded by towersstatic void maxArea(int[] point_x, int[] point_y, int n, int length, int width){ // Sort the x-coordinates of the list Arrays.sort(point_x); // Sort the y-coordinates of the list Arrays.sort(point_y); // dx --> maximum uncovered // tiles in x coordinates int dx = point_x[0]; // dy --> maximum uncovered // tiles in y coordinates int dy = point_y[0]; // Calculate the maximum uncovered // distances for both x and y coordinates for(int i = 1; i < n; i++) { dx = Math.max(dx, point_x[i] - point_x[i - 1]); dy = Math.max(dy, point_y[i] - point_y[i - 1]); } dx = Math.max(dx, (length + 1) - point_x[n - 1]); dy = Math.max(dy, (width + 1) - point_y[n - 1]); // Largest unguarded area is // max(dx)-1 * max(dy)-1 System.out.println((dx - 1) * (dy - 1));}// Driver Codepublic static void main(String[] args){ // Length and width of the grid int length = 15, width = 8; // No of guard towers int n = 3; // Array to store the x and // y coordinates int point_x[] = { 3, 11, 8 }; int point_y[] = { 8, 2, 6 }; // Function call maxArea(point_x, point_y, n, length, width);}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach# Function to calculate the largest# area unguarded by towersdef maxArea(point_x, point_y, n, length, width): # Sort the x-coordinates of the list point_x.sort() # Sort the y-coordinates of the list point_y.sort() # dx --> maximum uncovered # tiles in x coordinates dx = point_x[0] # dy --> maximum uncovered # tiles in y coordinates dy = point_y[0] # Calculate the maximum uncovered # distances for both x and y coordinates for i in range(1, n): dx = max(dx, point_x[i] - point_x[i - 1]) dy = max(dy, point_y[i] - point_y[i - 1]) dx = max(dx, (length + 1) - point_x[n - 1]) dy = max(dy, (width + 1) - point_y[n - 1]) # Largest unguarded area is # max(dx)-1 * max(dy)-1 print((dx - 1) * (dy - 1))# Driver Codeif __name__ == "__main__": # Length and width of the grid length = 15 width = 8 # No of guard towers n = 3 # Array to store the x and # y coordinates point_x = [ 3, 11, 8 ] point_y = [ 8, 2, 6 ] # Function call maxArea(point_x, point_y, n, length, width)# This code is contributed by akhilsaini |
C#
// C# Program for the above approachusing System;class GFG{// Function to calculate the largest// area unguarded by towersstatic void maxArea(int[] point_x, int[] point_y, int n, int length, int width){ // Sort the x-coordinates of the list Array.Sort(point_x); // Sort the y-coordinates of the list Array.Sort(point_y); // dx --> maximum uncovered // tiles in x coordinates int dx = point_x[0]; // dy --> maximum uncovered // tiles in y coordinates int dy = point_y[0]; // Calculate the maximum uncovered // distances for both x and y coordinates for(int i = 1; i < n; i++) { dx = Math.Max(dx, point_x[i] - point_x[i - 1]); dy = Math.Max(dy, point_y[i] - point_y[i - 1]); } dx = Math.Max(dx, (length + 1) - point_x[n - 1]); dy = Math.Max(dy, (width + 1) - point_y[n - 1]); // Largest unguarded area is // max(dx)-1 * max(dy)-1 Console.WriteLine((dx - 1) * (dy - 1));}// Driver Codestatic public void Main(){ // Length and width of the grid int length = 15, width = 8; // No of guard towers int n = 3; // Array to store the x and // y coordinates int[] point_x = { 3, 11, 8 }; int[] point_y = { 8, 2, 6 }; // Function call maxArea(point_x, point_y, n, length, width);}}// This code is contributed by akhilsaini |
Javascript
<script>// javascript program for the// above approach// Function to calculate the largest// area unguarded by towersfunction maxArea(polet_x, polet_y, n, length, width){ // Sort the x-coordinates of the list polet_x.sort((a, b) => a - b);; // Sort the y-coordinates of the list polet_y.sort((a, b) => a - b);; // dx --> maximum uncovered // tiles in x coordinates let dx = polet_x[0]; // dy --> maximum uncovered // tiles in y coordinates let dy = polet_y[0]; // Calculate the maximum uncovered // distances for both x and y coordinates for(let i = 1; i < n; i++) { dx = Math.max(dx, polet_x[i] - polet_x[i - 1]); dy = Math.max(dy, polet_y[i] - polet_y[i - 1]); } dx = Math.max(dx, (length + 1) - polet_x[n - 1]); dy = Math.max(dy, (width + 1) - polet_y[n - 1]); // Largest unguarded area is // max(dx)-1 * max(dy)-1 document.write((dx - 1) * (dy - 1));} // Driver Code // Length and width of the grid let length = 15, width = 8; // No of guard towers let n = 3; // Array to store the x and // y coordinates let polet_x = [ 3, 11, 8 ]; let polet_y = [ 8, 2, 6 ]; // Function call maxArea(polet_x, polet_y, n, length, width); </script> |
Output:
12
Time Complexity: (N * log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
