Minimum Area Rectangle

Companies:
  • Facebook Interview Questions
  • Google Interview Questions

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; 
}

 

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]