This problem we can solve using one checkOverlapArea(vector &rec1, vect &rec2, long long &area) which will return true if overlap and calculate area of largest rectange into area variable. 1. to check if two rectangle overlap we can use line concept, since line itself is a rectangle so, let L1 : x1---------------x2 L2: x3----------x4 L1 & L2 overlap only when smallest of (largest- x of L1,L2) > largest of (smallest-x L1, L2); => bool lengthoverlap min(x2,x4) > max(x1,x3); simillarly for height of rectangle bool heightOverlap = min(y2,y4) > max(y1, y3) if(lengthoverlap && heightOverlap){ // overlap is true now calculate area of square. } ===> No need to sort rectanges. O(N^2) class Solution { /* rec1: x1,y1,x2,y2 rec2: x3,y3,x4,y4 0 1 2 3 x1-----------x2 x3--------x4 x2 > x3 min(x2, x4) > max(x1, x3); min(rec1[2],rec2[2]) > max(rec1[0], rec2[0]); min(rec1[3],rec2[3]) > max(rec1[1], rec2[1]); */ public: bool checkOverLap(vector &rec1, vector &rec2, long long &area) { bool isLength = min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]); bool isHeight = min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]); if(isLength && isHeight){ int intersectLenght = min(rec1[2], rec2[2]) - max(rec1[0], rec2[0]); int intersectHeight = min(rec1[3], rec2[3]) - max(rec1[1], rec2[1]); long long squareSide = min(intersectLenght, intersectHeight); area = squareSide * squareSide; return true; } return false; } long long largestSquareArea(vector& bottomLeft, vector& topRight) { int n = bottomLeft.size(); vector rectangles(n, vector(4)); for(int i = 0; i < n; i++){ rectangles[i][0] = bottomLeft[i][0]; //x1 //x3 rectangles[i][1] = bottomLeft[i][1]; //y1 //y3 rectangles[i][2] = topRight[i][0]; //x2 //x4 rectangles[i][3] = topRight[i][1]; //y2 //y4 } long long maxArea = 0; for(int i = 0; i < n - 1; i++) { for(int j = i + 1; j < n; j++) { // if i,j overlap long long area = 0; if(checkOverLap(rectangles[i], rectangles[j], area)) maxArea = max(area, maxArea); } } return maxArea; } };
