**Brute Force Approach** :\n\nThe naive approach would be to look for every possible pair.\nSince each pair consists 4 points, hence 4 "for" loops will be required to iterate through every pair.\nPseudo Code :\n\n```\n for ( a : 1 -> n) \n\t for ( b : 1 -> n)\n\t\t for ( c : 1 -> n)\n\t\t\t for ( d : 1 -> n)\n\t\t\t\t Area = Area of Rectangle formed by point[a], point[b], point[c], point[d]\n\t\t\t\t if (Minimum_Area > Area)\n\t\t\t\t\t Minimum_Area = Area\n\n return Minimum_Area\n```\n\nTime Complexity : O(n^4)\nSpace Complexity : O(1)\n\n\n**Optimal Approach** (Using HashMap) :\n\nWe can store values in a structured manner to reduce the number of iterations.\nOne interesting obsevation about the **rectangle having sides parallel to x & y axis** is :\n*Given two points of a diagonal, we can calculate the remaining two points of the second diagonal.*\n\n![image](https://assets.leetcode.com/users/images/ae788e03-3252-4f57-b2d2-9567b9cc6a49_1632377423.275515.png)\n\nSuppose we fix two points A & B out of N points in a plane, its possible to have AB as a diagonal of a rectangle only if\nthe x & y coordinates of points A & B are different ie. `x1 is not equal to x2` AND `y1 is not equal to y2`.\n\nHaving A & B fixed, we can calculate coordinates of points C & D which can possibly form a rectangle. \n`x coordinate of C = x coordinate of B = x2`\n`y coordinate of C = y coordinate of A = y1`\n`x coordinate of D = x coordinate of A = x1`\n`y coordinate of D = y coordinate of B = y2`\nThe above coordinates are the possible coordinates of points C & D.\nNow we have to search for the points (out of all the points) having same coordinates as that of the calculated possible coordinates.\n\nSo far, our approach is to iterate through different (A,B) pairs and for each pair, we have to search for points C & D. \nSpeaking of Time Complexity : \nO(n^2) *[iterate through different (A,B) pairs]* x O(n^2) *[iterate through all possible (C,D) points]*.\nWhich still makes the Time Complexity as O(n^4).\nBasically for figuring out points C & D out of the remaining points, we are iterating through all the remaining points which is same as the brute force approach. \nThis gives us an intuition that we need to somehow eliminate few set of points without iterating through each of them.\n\n![image](https://assets.leetcode.com/users/images/733c7645-0baa-4564-a3e1-6ec91c0cc9e0_1632377473.5340226.png)\n\nIn the above diagram, P1, P2, P3 & P4 all have x coordinate same as of point A. Altough each of them have different y coordinates.\nBut only P1 is resposible for the formation of rectangle because the y coordinate of P1 is same as that of B.\n\nHence we quickly found out a point (out of 4 points) that was having x coordinate of A & y coordinate of B.\nThis idea can be implemented using a HashMap where the lookup time will be of O(1) on average.\nSo if we group the y coordinates on the basis of same x coordinate, using a HashSet we can search for corresponding y coordinate in O(1) time.\n\nSo lets create a HashMap having \nKey => *Different x coordinates*\nValue => *HashSet of y coordinates of points having same x coordinate*\n\n![image](https://assets.leetcode.com/users/images/f3bea016-3d10-457f-a2dd-4115144602b6_1632377510.5062003.png)\n\nSo while iterating through different (A,B) pairs, we can check whether there exists value cooresponding to C & D points in the hashmap.\nLets say we check whether there exists a point D in the hashmap,\nStep 1 : Key => *x coordinate of point A* (x1)\nStep 2 : Value => Corresponding to Key(x1), search for *y coordinate of point B* (y2) in *HashSet*\nIf coordinates of D exists in the HashMap, then a rectangle is possible.\nIf coordinates of D doesn\'t exists in the HashMap, then a rectangle is NOT possible, and we **iterate to a different (A,B) pair**.\n\n**C++ Code** with explanation :\n*Note : In C++, we use Unordered Map & Unordered Set because there is no need to sort the values inside the map or set.\nUsing Ordered Map & Ordered Set would give TLE (Time Limit Exceeded), because those data structures consume time for \nunnecessary internal sorting*\n\n```\nclass Solution {\npublic:\n int minAreaRect(vector>& points) {\n unordered_map> hashmap; // Key => Integer | Value => Set\n \n for(auto& single_point: points) // Iterate through every single point & store the coordinates in map.\n hashmap[single_point[0]].insert(single_point[1]); // Insert y coordinate into Value (HashSet) corresponding to Key (equal to x coordinate)\n\t\t\t/* Explanation : \n\t\t\t\t\tsingle_point => refering to a single point [x,y] in vector\n\t\t\t\t\tx-coordinate of a single point => single_point[0]\n\t\t\t\t\ty-coordinate of a single point => single_point[1]\n\n\t\t\t\t\tKey => x coordinate of a point \n\t\t\t\t\t\t=> single_point[0]\n\n\t\t\t\t\tValue => HashSet of y coordinates \n\t\t\t\t\t\t=> hashmap[Key]\n\t\t\t\t\t\t=> hashmap[x-coordinate of a single point]\n\t\t\t\t\t\t=> hashmap[single_point[0]]\n\n\t\t\t\t\tInsert y coordinate into corresponding Value (HashSet)\n\t\t\t\t\t\t=> Value.insert(y-coordinate of a single point)\n\t\t\t\t\t\t=> hashmap[Key].insert(y-coordinate of a single point)\n\t\t\t\t\t\t=> hashmap[x-coordinate of a single point].insert(y-coordinate of a single point)\n\t\t\t\t\t\t=> hashmap[single_point[0]].insert(single_point[1])\n\t\t\t*/\n\t\t\t\n int minimum_area = INT_MAX; // Vairable to store the minimum area\n \n for(int i = 0; i < points.size(); i++) { // Iterator corresponding to different A points\n for(int j = i + 1; j < points.size(); j++) { // Iterator corresponding to different B points\n\t\t\t\n int x1 = points[i][0], y1 = points[i][1]; // Coordinates of Point A\n\t\t\t\tint x2 = points[j][0], y2 = points[j][1]; // Coordinates of Point B\n \n if(x1 != x2 && y1 != y2) // Point A & B must form a diagonal of the rectangle.\n if( hashmap[x1].find(y2) != hashmap[x1].end() // Check if D exists in hashmap\n\t\t\t\t\t\t\t\t\t\t\t&& \n\t\t\t\t\thashmap[x2].find(y1) != hashmap[x2].end() ) // Check if C exists in hashmap\n\t\t\t\t\t/* Explanation : \n\t\t\t\t\t\t\tCheck existence of y2 in Value (HashSet) corresponding to x1 Key\n\t\t\t\t\t\t\t\t=> Value.find(y-coordinate of point B)\n\t\t\t\t\t\t\t\t=> hashmap[Key].find(y-coordinate of point B)\n\t\t\t\t\t\t\t\t=> hashmap[x-coordinate of point A].find(y-coordinate of point B)\n\t\t\t\t\t\t\t\t=> hashmap[x1].find(y2) => Checks if point D exists in hashmap \n\t\t\t\t\t\t\tCheck existence of y1 in Value (HashSet) corresponding to x2 Key\n\t\t\t\t\t\t\t\t=> Value.find(y-coordinate of point A)\n\t\t\t\t\t\t\t\t=> hashmap[Key].find(y-coordinate of point A)\n\t\t\t\t\t\t\t\t=> hashmap[x-coordinate of point B].find(y-coordinate of point A)\n\t\t\t\t\t\t\t\t=> hashmap[x2].find(y1) => Checks if point C exists in hashmap \n\t\t\t\t\t*/\n minimum_area = min( minimum_area , abs(x1-x2) * abs(y1-y2) ); // Store the minimum area possible\n }\n }\n return minimum_area != INT_MAX ? minimum_area : 0; // Return 0 if no rectangle exists\n }\n};\n```\n\n**Java Code** with explanation :\n\n```\nclass Solution {\n public int minAreaRect(int[][] points) {\n HashMap> hashmap = new HashMap<>(); // Key => Integer | Value => Set\n \n for(int single_point[] : points) // Iterate through every single point & store the coordinates in map\n {\n if(!hashmap.containsKey(single_point[0])){ // Check if x coordinate of the single point already exisits as a Key in hasmap.\n hashmap.put(single_point[0], new HashSet()); // Insert a new Key (equal to x coordinate) in the hashmap with corresponding Value (equal to newly created empty HashSet).\n }\n hashmap.get(single_point[0]).add(single_point[1]); // Insert y coordinate into Value (HashSet) corresponding to Key (equal to x coordinate)\n\t\t\t/* Explanation : \n\t\t\t\t\tsingle_point => refering to a single point [x,y]\n\t\t\t\t\tx-coordinate of a single point => single_point[0]\n\t\t\t\t\ty-coordinate of a single point => single_point[1]\n\n\t\t\t\t\tKey => x coordinate of a point \n\t\t\t\t\t\t=> single_point[0]\n\n\t\t\t\t\tValue => HashSet of y coordinates \n\t\t\t\t\t\t=> hashmap.get(Key)\n\t\t\t\t\t\t=> hashmap.get(x-coordinate of a single point)\n\t\t\t\t\t\t=> hashmap.get(single_point[0])\n\n\t\t\t\t\tInsert y coordinate into corresponding Value (HashSet)\n\t\t\t\t\t\t=> Value.add(y-coordinate of a single point)\n\t\t\t\t\t\t=> hashmap.get(Key).add(y-coordinate of a single point)\n\t\t\t\t\t\t=> hashmap.get(x-coordinate of a single point).add(y-coordinate of a single point)\n\t\t\t\t\t\t=> hashmap.get(single_point[0]).add(single_point[1])\n\t\t\t*/\n }\n \n int minimum_area = Integer.MAX_VALUE; // Vairable to store the minimum area\n \n for(int i=0; i Value.contains(y-coordinate of point B)\n\t\t\t\t\t\t\t\t=> hashmap.get(Key).contains(y-coordinate of point B)\n\t\t\t\t\t\t\t\t=> hashmap.get(x-coordinate of point A).contains(y-coordinate of point B)\n\t\t\t\t\t\t\t\t=> hashmap.get(x1).contains(y2) => Checks if point D exists in hashmap \n\t\t\t\t\t\t\tCheck existence of y1 in Value (HashSet) corresponding to x2 Key\n\t\t\t\t\t\t\t\t=> Value.contains(y-coordinate of point A)\n\t\t\t\t\t\t\t\t=> hashmap.get(Key).contains(y-coordinate of point A)\n\t\t\t\t\t\t\t\t=> hashmap.get(x-coordinate of point B).contains(y-coordinate of point A)\n\t\t\t\t\t\t\t\t=> hashmap.get(x2).contains(y1) => Checks if point C exists in hashmap \n\t\t\t\t\t*/\n minimum_area = Math.min(minimum_area, Math.abs(x1-x2) * Math.abs(y1-y2)); // Store the minimum area possible\n }\n }\n return minimum_area != Integer.MAX_VALUE ? minimum_area : 0; // Return 0 if no rectangle exists\n }\n}\n```\n\n**Time Complexity : O(n^2)**\nwhere n = Total number of points\nExplanation :\nIteration Time: Iterating through different (A,B) pairs => O(n^2)\nSearch Time: Searching for y coordinate corresponding to x coordinate => O(n) {Worst case for searching in HashSet} + O(n) {Worst case for searching in HashMap} => O(n)\n*Time Complexity = Iteration Time * Search Time, since we are searching for point C & D for each pair of point A & B*\nSo in this case the time complexity will be O(n^2) * O(n) = O(n^3)\nBut usually, we consider the search operation in a HashMap & HashSet to run in constant time i.e. O(1).\nHence the time complexity will be O(n^2) * O(1) = O(n^2)\n\n**Space Complexity : O(n)**\nwhere n = Total number of points\nExplanation :\nLets assume we have 3 Keys in the hashmap & have corresposing y values mapped to it.\n![image](https://assets.leetcode.com/users/images/c6c148b0-3e95-478c-9506-902a08f3961a_1632377572.4723148.png)\nSpace Complexity = ["a" number of elements] + ["b" number of elements] + ["c" number of elements]\n=> Space Complexity = [Number of y coordinates having same x coordinate (**x1**)] +[Number of y coordinates having same x coordinate (**x2**)] + [Number of y coordinates having same x coordinate (**x3**)]\n=> Space Complexity = Total number of y coordinates of all the points\n=> Space Complexity = Total number of points\nHence, Space Complexity : O(n)

Minimum Area Rectangle

Problem Description

Problem Description

Answer Panel