Area of the largest rectangle formed by lines parallel to X and Y axis from given set of points
Given an array arr[] consisting of N pair of integers representing coordinates of N points, the task is to find the area of the largest rectangle formed by straight lines drawn parallel to X and Y-axis from a given set of points.
Examples:
Input: arr[] = {{0, 0}, {1, 1}}
Output: 1
Explanation: The area of the largest rectangle is 1 formed by the coordinates (0, 0), (0, 1), (1, 0), (1, 1).Input: arr[] = {{-2, 0}, {2, 0}, {4, 0}, {4, 2}}
Output: 8
Explanation: The area of the largest rectangle possible is 8 ( length = 4 and breadth = 2 ) by the coordinates (-2, 0), (2, 0), (2, 2), (-2, 2).
Approach: The problem can be solved using the sorting technique. Follow the steps below to solve the problem:
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to return the area of the largest // rectangle formed by lines parallel to X // and Y axis from given set of points int maxRectangle(vector<vector< int > > sequence, int size) { // Initialize two arrays long long int X_Cord[size], Y_Cord[size]; // Store x and y coordinates for ( int i = 0; i < size; i++) { X_Cord[i] = sequence[i][0]; Y_Cord[i] = sequence[i][1]; } // Sort arrays sort(X_Cord, X_Cord + size); sort(Y_Cord, Y_Cord + size); // Initialize max differences long long int X_Max = 0, Y_Max = 0; // Find max adjacent differences for ( int i = 0; i < size - 1; i++) { X_Max = max(X_Max, X_Cord[i + 1] - X_Cord[i]); Y_Max = max(Y_Max, Y_Cord[i + 1] - Y_Cord[i]); } // Return answer return X_Max * Y_Max; } // Driver Code int main() { // Given points vector<vector< int > > point = { { -2, 0 }, { 2, 0 }, { 4, 0 }, { 4, 2 } }; // Total points int n = point.size(); // Function call cout << maxRectangle(point, n); } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to return the area of the largest // rectangle formed by lines parallel to X // and Y axis from given set of points static int maxRectangle( int [][] sequence, int size) { // Initialize two arrays int [] X_Cord = new int [size]; int [] Y_Cord = new int [size]; // Store x and y coordinates for ( int i = 0 ; i < size; i++) { X_Cord[i] = sequence[i][ 0 ]; Y_Cord[i] = sequence[i][ 1 ]; } // Sort arrays Arrays.sort(X_Cord); Arrays.sort(Y_Cord); // Initialize max differences int X_Max = 0 , Y_Max = 0 ; // Find max adjacent differences for ( int i = 0 ; i < size - 1 ; i++) { X_Max = Math.max(X_Max, X_Cord[i + 1 ] - X_Cord[i]); Y_Max = Math.max(Y_Max, Y_Cord[i + 1 ] - Y_Cord[i]); } // Return answer return X_Max * Y_Max; } // Driver Code public static void main(String[] args) { // Given points int [][] point = { { - 2 , 0 }, { 2 , 0 }, { 4 , 0 }, { 4 , 2 } }; // Total points int n = point.length; // Function call System.out.print(maxRectangle(point, n)); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the # above approach # Function to return the # area of the largest # rectangle formed by lines # parallel to X and Y axis # from given set of points def maxRectangle(sequence, size): # Initialize two arrays X_Cord = [ 0 ] * size Y_Cord = [ 0 ] * size # Store x and y coordinates for i in range (size): X_Cord[i] = sequence[i][ 0 ] Y_Cord[i] = sequence[i][ 1 ] # Sort arrays X_Cord.sort() Y_Cord.sort() # Initialize max differences X_Max = 0 Y_Max = 0 # Find max adjacent differences for i in range (size - 1 ): X_Max = max (X_Max, X_Cord[i + 1 ] - X_Cord[i]) Y_Max = max (Y_Max, Y_Cord[i + 1 ] - Y_Cord[i]) # Return answer return X_Max * Y_Max # Driver Code if __name__ = = "__main__" : # Given points point = [[ - 2 , 0 ], [ 2 , 0 ], [ 4 , 0 ], [ 4 , 2 ]] # Total points n = len (point) # Function call print (maxRectangle(point, n)) # This code is contributed by Chitranayal |
C#
// C# program for the above approach using System; class GFG{ // Function to return the area of the largest // rectangle formed by lines parallel to X // and Y axis from given set of points static int maxRectangle( int [,] sequence, int size) { // Initialize two arrays int [] X_Cord = new int [size]; int [] Y_Cord = new int [size]; // Store x and y coordinates for ( int i = 0; i < size; i++) { X_Cord[i] = sequence[i, 0]; Y_Cord[i] = sequence[i, 1]; } // Sort arrays Array.Sort(X_Cord); Array.Sort(Y_Cord); // Initialize max differences int X_Max = 0, Y_Max = 0; // Find max adjacent differences for ( int i = 0; i < size - 1; i++) { X_Max = Math.Max(X_Max, X_Cord[i + 1] - X_Cord[i]); Y_Max = Math.Max(Y_Max, Y_Cord[i + 1] - Y_Cord[i]); } // Return answer return X_Max * Y_Max; } // Driver Code public static void Main(String[] args) { // Given points int [,] point = { { -2, 0 }, { 2, 0 }, { 4, 0 }, { 4, 2 } }; // Total points int n = point.GetLength(0); // Function call Console.Write(maxRectangle(point, n)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to implement // the above approach // Function to return the area of the largest // rectangle formed by lines parallel to X // and Y axis from given set of points function maxRectangle(sequence, size) { // Initialize two arrays let X_Cord = []; let Y_Cord = []; // Store x and y coordinates for (let i = 0; i < size; i++) { X_Cord[i] = sequence[i][0]; Y_Cord[i] = sequence[i][1]; } // Sort arrays X_Cord.sort(); Y_Cord.sort(); // Initialize max differences let X_Max = 0, Y_Max = 0; // Find max adjacent differences for (let i = 0; i < size - 1; i++) { X_Max = Math.max(X_Max, X_Cord[i + 1] - X_Cord[i]); Y_Max = Math.max(Y_Max, Y_Cord[i + 1] - Y_Cord[i]); } // Return answer return X_Max * Y_Max; } // Driver Code // Given points let point = [[ -2, 0 ], [ 2, 0 ], [ 4, 0 ], [ 4, 2 ]]; // Total points let n = point.length; // Function call document.write(maxRectangle(point, n)); </script> |
8
Time Complexity: O(N*log(N)) where N is the total number of points.
Auxiliary Space: O(N)