<p>You are given an array of points in the <strong>X-Y</strong> plane <code>points</code> where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>

<p>Return <em>the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes</em>. If there is not any such rectangle, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/rec1.JPG" style="width: 500px; height: 447px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/rec2.JPG" style="width: 500px; height: 477px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 500</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 4 * 10<sup>4</sup></code></li>
	<li>All the given points are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) 
    {
        int num_points=points.size();
        map<pair<int,int>,vector<int>> map;
        int i,j,x,y,x1,y1,length;
        int min_area=INT_MAX,min_width;
        
        for(i=0;i<num_points;i++)
        {
            x = points[i][0]; y = points[i][1];
            for(j=0;j<num_points;j++)
            {
                x1 = points[j][0]; y1 = points[j][1];
                if(y==y1 && x<x1)                   
// x < x1, to make unique pair otherwise if x and x1 are 2 or 4 , then (2,4) and (4,2) would be two different entrys in map
                    map[make_pair(x,x1)].push_back(y);
            }
        }
        
        for(auto i:map)
        {
            length = i.first.second-i.first.first;
            vector<int> widths = i.second;
            
            sort(widths.begin(),widths.end());      // sorting to get minimum area
            
            min_width=INT_MAX;
            for(j=1;j<widths.size();j++)
                min_width = min(min_width, widths[j]-widths[j-1]);
            if(min_width!=INT_MAX)
                min_area = min(min_area, length*min_width);
        }
        return (min_area<INT_MAX)?min_area:0;
    }
};
358371