Find minimum area of rectangle formed from given shuffled coordinates

By Ann Roberts On Jan 5, 2023

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) = 1

Input: 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 ans 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 i^th slide and update the low and high pointers.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int minArea(int A[], int N)

{

sort(A, A + N);

int ans = INT_MAX;

int low = 0, high = N / 2 - 1;

while (1) {

if (low == 0) {

ans = (A[N / 2 - 1] - A[0])

* (A[N - 1] - A[N / 2]);

}

else if (high == N - 1)

break;

else {

ans = min(ans, (A[high] - A[low])

* (A[N - 1] - A[0]));

}

low++, high++;

}

return ans;

}

int main()

{

int A[] = { 4, 1, 3, 2, 3, 2, 1, 3 };

int N = sizeof(A) / sizeof(A[0]);

cout << minArea(A, N) << endl;

int A1[] = { 5, 8, 5, 5, 7, 5 };

int N1 = sizeof(A1) / sizeof(A1[0]);

cout << minArea(A1, N1) << endl;

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles: