Find minimum area of rectangle formed from given shuffled coordinates
Given an array arr[] of size N, the array represents N / 2 coordinates of a rectangle randomly shuffled with its X and Y coordinates. The task for this problem is to construct N / 2 pairs of (X, Y) coordinates by choosing X and Y from array arr[] in such a way that a rectangle that contains all these points has a minimum area.
Examples:
Input: arr[] = {4, 1, 3, 2, 3, 2, 1, 3}
Output: 1
Explanation: let pairs formed be (1, 3), (1, 3), (2, 3) and (2, 4) then the rectangle that contains these points will have a lower Left coordinate (1, 3) and upper right coordinate (2, 4). Hence area of rectangle = (xUpper – xLower) * (yUpper – yLower) = (2 – 1) * (4 – 3) = 1Input: arr[] = {5, 8, 5, 5, 7, 5}
Output: 0
Explanation: let pairs formed be (5, 5), (5, 7) and (5, 8) then the rectangle that contains these points will have a lower Left coordinate (5, 5) and upper right coordinate (5, 8). Hence area of rectangle = (xUpper – xLower) * (yUpper – yLower) = (5 – 5) * (8 – 5) = 0
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Observation: Sort the array arr[] and it will always be better to take X coordinate’s as subarray of size N / 2 from sorted array A[] and Y coordinates as leftover elements.
The answer can be tracked for all subarrays of size N / 2 by using the sliding window technique.
Follow the steps below to solve the problem:
- Sort the array arr[].
- Create a variable and to store the potential answer.
- Initialize window size from 0 to (N/2) – 1 by declaring low = 1 and high = N/2 – 1.
- Start a while loop and check if low==0 if yes,
- then, update the answer for the first slide
- Otherwise, break when the slide reaches the end high == N-1
- else, update the ans for ith slide and update the low and high pointers.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to Find minimum area // of rectangle formed from given // shuffled coordinates int minArea( int A[], int N) { // Sorting given array sort(A, A + N); // Initializing answer to infinity int ans = INT_MAX; // Initializing window from // 0 to (N / 2) - 1 int low = 0, high = N / 2 - 1; while (1) { if (low == 0) { // Updating answer for // first slide ans = (A[N / 2 - 1] - A[0]) * (A[N - 1] - A[N / 2]); } // Break when slide reaches // at end else if (high == N - 1) break ; else { // Updating answer for // i'th slide ans = min(ans, (A[high] - A[low]) * (A[N - 1] - A[0])); } // Moving slide of size N / 2 by // one position low++, high++; } // Returning the answer return ans; } // Driver Code int main() { // Input 1 int A[] = { 4, 1, 3, 2, 3, 2, 1, 3 }; int N = sizeof (A) / sizeof (A[0]); // Function Call cout << minArea(A, N) << endl; // Input 2 int A1[] = { 5, 8, 5, 5, 7, 5 }; int N1 = sizeof (A1) / sizeof (A1[0]); // Function Call cout << minArea(A1, N1) << endl; return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to Find minimum area // of rectangle formed from given // shuffled coordinates public static int minArea( int [] A, int N) { // Sorting given array Arrays.sort(A); // Initializing answer to infinity int ans = Integer.MAX_VALUE; // Initializing window from // 0 to (N / 2) - 1 int low = 0 , high = N / 2 - 1 ; while ( true ) { if (low == 0 ) { // Updating answer for // first slide ans = (A[N / 2 - 1 ] - A[ 0 ]) * (A[N - 1 ] - A[N / 2 ]); } // Break when slide reaches // at end else if (high == N - 1 ) break ; else { // Updating answer for // i'th slide ans = Math.min(ans, (A[high] - A[low]) * (A[N - 1 ] - A[ 0 ])); } // Moving slide of size N / 2 by // one position low++; high++; } // Returning the answer return ans; } public static void main (String[] args) { // Input 1 int [] A = { 4 , 1 , 3 , 2 , 3 , 2 , 1 , 3 }; int N = A.length; // Function Call System.out.println(minArea(A, N)); // Input 2 int [] A1 = { 5 , 8 , 5 , 5 , 7 , 5 }; int N1 = A1.length; // Function Call System.out.println(minArea(A1, N1)); } } // This code is contributed by lokesh. |
Python3
# Python code to implement the approach def minArea(A, N): # Sorting given array A.sort() # Initializing answer to infinity ans = float ( 'inf' ) # Initializing window from # 0 to (N / 2) - 1 low = 0 high = N / / 2 - 1 while True : if low = = 0 : # Updating answer for # first slide ans = (A[N / / 2 - 1 ] - A[ 0 ]) * (A[N - 1 ] - A[N / / 2 ]) # Break when slide reaches # at end elif high = = N - 1 : break else : # Updating answer for # i'th slide ans = min (ans, (A[high] - A[low]) * (A[N - 1 ] - A[ 0 ])) # Moving slide of size N / 2 by # one position low + = 1 high + = 1 # Returning the answer return ans # Driver code if __name__ = = '__main__' : # Input 1 A = [ 4 , 1 , 3 , 2 , 3 , 2 , 1 , 3 ] N = len (A) # Function Call print (minArea(A, N)) # Input 2 A1 = [ 5 , 8 , 5 , 5 , 7 , 5 ] N1 = len (A1) # Function Call print (minArea(A1, N1)) # This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approach using System; using System.Collections; public class GFG { // Function to Find minimum area // of rectangle formed from given // shuffled coordinates static int minArea( int [] A, int N) { // Sorting given array Array.Sort(A); // Initializing answer to infinity int ans = Int32.MaxValue; // Initializing window from // 0 to (N / 2) - 1 int low = 0, high = N / 2 - 1; while ( true ) { if (low == 0) { // Updating answer for // first slide ans = (A[N / 2 - 1] - A[0]) * (A[N - 1] - A[N / 2]); } // Break when slide reaches // at end else if (high == N - 1) break ; else { // Updating answer for // i'th slide ans = Math.Min(ans, (A[high] - A[low]) * (A[N - 1] - A[0])); } // Moving slide of size N / 2 by // one position low++; high++; } // Returning the answer return ans; } static public void Main() { // Code // Input 1 int [] A = { 4, 1, 3, 2, 3, 2, 1, 3 }; int N = A.Length; // Function Call Console.WriteLine(minArea(A, N)); // Input 2 int [] A1 = { 5, 8, 5, 5, 7, 5 }; int N1 = A1.Length; // Function Call Console.WriteLine(minArea(A1, N1)); } } // This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approach // Function to Find minimum area // of rectangle formed from given // shuffled coordinates function minArea(A, N) { // Sorting given array A.sort(); // Initializing answer to infinity let ans = Number.MAX_SAFE_INTEGER; // Initializing window from // 0 to (N / 2) - 1 let low = 0, high = N / 2 - 1; while (1) { if (low == 0) { // Updating answer for // first slide ans = (A[N / 2 - 1] - A[0]) * (A[N - 1] - A[N / 2]); } // Break when slide reaches // at end else if (high == N - 1) break ; else { // Updating answer for // i'th slide ans = Math.min(ans, (A[high] - A[low]) * (A[N - 1] - A[0])); } // Moving slide of size N / 2 by // one position low++, high++; } // Returning the answer return ans; } // Driver Code // Input 1 let A = [ 4, 1, 3, 2, 3, 2, 1, 3 ]; let N = A.length; // Function Call console.log(minArea(A, N)); // Input 2 let A1 = [ 5, 8, 5, 5, 7, 5 ]; let N1 = A1.length; // Function Call console.log(minArea(A1, N1)); |
1 0
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Related Articles:
Contact Us