Problem Statement
Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.
If there isn’t any rectangle, return 0.
Sample Test Case
Example 1: Input: [[1,1],[1,3],[3,1],[3,3],[2,2]] Output: 4 Example 2: Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] Output: 2
Problem Solution
Our Approach will be to sort the given points on the basis of columns(x co-ordinate) and then count each rectangle on the basis right most edges.
Group the points by x coordinates, so that we have columns of points. Then, for every pair of points in a column (with coordinates (x, y1) and ( x, y2), check for the smallest rectangle with this pair of points as the rightmost edge. We can do this by keeping memory of what pairs of points we’ve seen before.
We create a map which contains all the values of y for a particular x. Now for a pair of x, we need to find a pair of y to complete the rectangle. We take the minimum ans in each case.
Complexity Analysis
Complexity Analysis
- Time Complexity: O(N^2), where N is the length of points.
- Space Complexity: O(N) since we are storing all the points in our map.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
// function to find minimum area of Rectangle
int minAreaRect(vector<vector<int>> A){
// creating empty columns
map<int,vector<int>> columns;
// fill columns with coordinates
for(auto i:A)
columns[i[0]].push_back(i[1]);
map<pair<int,int>,int > lastx;
int ans = INT_MAX;
for (auto x:columns)
{
vector<int> column = x.second;
sort(column.begin(), column.end());
for (int j = 0; j < column.size(); j++)
{
for (int i = 0; i < j; i++)
{
int y1 = column[i];
// check if rectangle can be formed
if (lastx.find({y1, column[j]}) != lastx.end())
{
ans = min(ans, (x.first - lastx[{y1, column[j]}]) *
(column[j] - column[i]));
}
lastx[{y1, column[j]}] = x.first;
}
}
}
if (ans < INT_MAX)
return ans;
else
return 0;
}
// Driver code
int main()
{
vector<vector<int>> A = {{1, 1}, {1, 3}, {3, 1}, {3, 3}, {2, 2}};
cout << (minAreaRect(A));
return 0;
}
