<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) {
        /*  for each point
            map row to map col to point

            for each point
                // find 3 other points
                for each point in same col in order of closest
                    for each point in same row in order of closest
                        find opposing point to form rect
                            save min and break
            
            for each point
                // find opposing point where row and col is not same as current point
                for each in map that is not same row and col in order of closest (rdelta + cdelta)
                    // avoid recomputing rectangles by only looking at points > than current point
                    lookup in map for existing topleft point and bottom right point based on opposing point
                        save minrect and break
        */

        // this is basically ordered by points closest to origin which makes for iterating 
        // in order of points closest first i think
        map<int, map<int, int>> point_map;
        // map<int, map<int, int>> point_map_by_col;
        for (int i = 0; i < points.size(); ++i) {
            auto p = points[i];
            point_map[p[0]][p[1]] = i;
            // point_map_by_col[p[1]][p[0]] = i;
        }

        int min_rect = std::numeric_limits<int>::max();

        // looking for the opposing point initially version
        // nlogn + n*n*log(n)
        // takes less space then solution 1 version below but same runtime beat
        // simpler to write
        for (const auto& p: points) {
            int r = p[0];
            int c = p[1];
            // iterate through all other points
            for (const auto& it_r: point_map) {
                for (const auto& it_c: it_r.second) {
                    vector<int>& op = points[it_c.second];
                    int o_r = op[0];
                    int o_c = op[1];
                    if (o_r <= r || o_c <= c) continue;
                    
                    // lookup the other 2 points
                    if (/*topleft */ point_map[o_r].contains(c)) {
                        if (/*bottom right */ point_map[r].contains(o_c)) {
                            min_rect = min(min_rect, (o_r - r) * (o_c - c));
                            break; // can break because ran in order of nearest origin first
                        }
                    }
                }
            }
        }

        // soln 1 with O(N*logNLogN) with worse case all points in the same place
        // if all unique points, worst case is all points like an L with half the points in same row other half in same col
        // so it's nlogn + n*n/2*n/2*logN = N^3*logN
        // for (const auto& p: points) {
        //     int r = p[0];
        //     int c = p[1];
        //     for (const auto& it_c: point_map[r]) {
        //         auto& br = points[it_c.second];
        //         int br_r = br[0];
        //         int br_c = br[1];
        //         // std::cout << "at br: r " << r << " c " << c << " br_r " << br_r << " br_c " << br_c << std::endl;
        //         if (br_c <= c) continue;
        //         // std::cout << "using br: r " << r << " c " << c << " br_r " << br_r << " br_c " << br_c << std::endl;
        //         for (const auto& it_r: point_map_by_col[c]) {
        //             auto& tl = points[it_r.second];
        //             int tl_r = tl[0];
        //             int tl_c = tl[1];
        //             // std::cout << "at tl: r " << r << " c " << c << " tl_r " << tl_r << " tl_c " << tl_c << std::endl;
        //             if (tl_r <= r) continue;
        //             // std::cout << "using tl: r " << r << " c " << c << " tl_r " << tl_r << " tl_c " << tl_c << std::endl;
        //             // lookup opposing points
        //             if (point_map[tl_r].contains(br_c)) {
        //                 min_rect = min(min_rect, (tl_r - r) * (br_c - c));
        //                 break; // since search in order of closest to origin, can break
        //             }
        //         }
        //     }
        // }
        return min_rect == std::numeric_limits<int>::max()? 0 : min_rect;
    }
};
29553