LeetCode 836: Rectangle Overlap – Java Solution, Explanation & Approach
IntroductionLeetCode 836, Rectangle Overlap, is a simple geometry problem that tests an important idea: how to determine whether two ranges actually intersect.Each rectangle is represented using four coordinates:[x1, y1, x2, y2]where:(x1, y1) → bottom-left corner(x2, y2) → top-right cornerThe rectangles are axis-aligned, so their sides are always parallel to the X and Y axes.The important part is that touching is not considered overlap.For example, if two rectangles share only an edge or a corner, the answer must be false.The solution can be built entirely using coordinate comparisons, without calculating the actual intersection area.Some example testcase with visualized coordinates:-Example 1:Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]Output: trueExample 2:Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]Output: falseExample 3:Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3]Output: falseQuestion LinkLeetCode 836 – Rectangle OverlapUnderstanding the IdeaFor two rectangles to have a positive-area overlap, they must overlap in both dimensions:Along the X-axisAlong the Y-axisIf they fail to overlap in either dimension, the rectangles cannot overlap.For example, if one rectangle is completely above another:There is no overlap.The same happens if one rectangle is completely to the left or right of the other.ApproachThe solution first extracts the four important boundaries of both rectangles:Rectangle 1:left = rec1[0]bottom = rec1[1]right = rec1[2]top = rec1[3]Rectangle 2:left = rec2[0]bottom = rec2[1]right = rec2[2]top = rec2[3]Then the solution checks whether the rectangles are separated.Check vertical separationif(rect1h1 >= rect2h2 || rect2h1 >= rect1h2){ return false;}If the bottom of Rectangle 1 is at or above the top of Rectangle 2, they do not overlap.Similarly, if the bottom of Rectangle 2 is at or above the top of Rectangle 1, there is no overlap.The use of >= is important because rectangles that only touch an edge must return false.Check horizontal separationif(rect1l1 >= rect2l2 || rect2l1 >= rect1l2){ return false;}This checks whether one rectangle is completely to the left of the other.Again, >= handles the edge-touching case.After these separation checks pass, the rectangles must overlap with positive width and height.Java Solutionclass Solution { public boolean isRectangleOverlap(int[] rec1, int[] rec2) { boolean leno = false; boolean heio = false; int rect1l1 = rec1[0]; int rect1l2 = rec1[2]; int rect1h1 = rec1[1]; int rect1h2 = rec1[3]; int rect2l1 = rec2[0]; int rect2l2 = rec2[2]; int rect2h1 = rec2[1]; int rect2h2 = rec2[3]; // Check if the rectangles are separated vertically if (rect1h1 >= rect2h2 || rect1l1 >= rect2l2) { return false; } // Check if the rectangles are separated horizontally if (rect2h1 >= rect1h2 || rect2l1 >= rect1l2) { return false; } // There is horizontal overlap if (rect1l2 > rect2l1) { leno = true; } // There is vertical overlap if (leno && rect1h2 <= rect2h2) { heio = true; } if (leno && rect1h2 > rect2h2) { heio = true; } return leno && heio; }}Dry RunConsider:rec1 = [0,0,2,2]rec2 = [1,1,3,3]Rectangle 1:left = 0bottom = 0right = 2top = 2Rectangle 2:left = 1bottom = 1right = 3top = 3Vertical checkrect1 bottom >= rect2 top0 >= 3 → falseandrect2 bottom >= rect1 top1 >= 2 → falseSo they are not vertically separated.Horizontal checkrect1 left >= rect2 right0 >= 3 → falseandrect2 left >= rect1 right1 >= 2 → falseSo they are not horizontally separated either.Therefore, there is a positive-area intersection.Answer = trueThe overlapping region is:x: 1 to 2y: 1 to 2which has positive width and height.Why Edge Touching Returns FalseConsider:rec1 = [0,0,1,1]rec2 = [1,0,2,1]The rectangles touch at x = 1, but there is no positive-width intersection.The condition:rect2l1 >= rect1l2becomes:1 >= 1which is true.Therefore:return false;This is why >= is used instead of simply >.A Useful Way to Think About the ProblemA rectangle overlap problem can be reduced to this simple rule:If the rectangles are separated in X or separated in Y → no overlap. Otherwise → overlap.The four separation cases are:Rectangle 1 is above Rectangle 2Rectangle 2 is above Rectangle 1Rectangle 1 is left of Rectangle 2Rectangle 2 is left of Rectangle 1If none of these situations occurs, the rectangles overlap.Complexity AnalysisThere are only a constant number of coordinate comparisons.Time Complexity: O(1)Space Complexity: O(1)No loops, additional arrays, or data structures are required.Code ImprovementThe current solution works, but the final leno and heio checks are more complicated than necessary.Once all four separation cases have been eliminated, overlap is already guaranteed.The same idea can therefore be written more directly:class Solution { public boolean isRectangleOverlap(int[] rec1, int[] rec2) { // No vertical overlap if (rec1[1] >= rec2[3] || rec2[1] >= rec1[3]) { return false; } // No horizontal overlap if (rec1[0] >= rec2[2] || rec2[0] >= rec1[2]) { return false; } return true; }}This version has exactly the same asymptotic complexity but makes the core geometry easier to recognize.Interview TipFor coordinate and geometry problems, avoid immediately trying to calculate the intersection area.A better first question is:"When can the two objects definitely NOT overlap?"For rectangles, there are only four separation cases. Once those are handled, the remaining case automatically represents a positive-area overlap.This "check the impossible cases first" technique is useful in many interval and geometry problems.ConclusionLeetCode 836 is a good example of how a seemingly geometric problem can be solved using simple comparisons.The key observation is that two rectangles overlap only when they have overlap on both the X-axis and Y-axis. If one rectangle is completely separated from the other in either direction, the answer is false.The important boundary detail is using >=, because merely touching at an edge or corner does not count as an overlap.
