Search Blogs

Showing results for "Rectangle Overlap"

Found 2 results

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.

LeetCodeJavaRectangle OverlapGeometryArraysCoordinatesMathEasy

LeetCode 735: Asteroid Collision — Java Solution Explained

IntroductionIf you have been building your stack skills through problems like Valid Parentheses, Next Greater Element, and Backspace String Compare, then LeetCode 735 Asteroid Collision is the problem where everything comes together. It is one of the most satisfying Medium problems on LeetCode because it feels like a real simulation — you are literally modelling asteroids flying through space and crashing into each other.You can find the problem here — LeetCode 735 Asteroid Collision.This article breaks everything down in plain English so that anyone — beginner or experienced — can understand exactly what is happening and why the stack is the perfect tool for this problem.What Is the Problem Really Asking?You have a row of asteroids moving through space. Each asteroid has a size and a direction:Positive number → asteroid moving to the rightNegative number → asteroid moving to the leftAll asteroids move at the same speed. When a right-moving asteroid and a left-moving asteroid meet head-on, they collide:The smaller one explodesIf they are the same size, both explodeThe bigger one survives and keeps movingTwo asteroids moving in the same direction never meet, so they never collide.Return the final state of all surviving asteroids after every possible collision has happened.Real Life Analogy — Cars on a HighwayImagine a highway with cars driving in both directions. Cars going right are in one lane, cars going left are in another lane. Now imagine the lanes overlap at some point.A small car going right crashes into a big truck going left — the car gets destroyed, the truck keeps going. Two equally sized cars crash — both are destroyed. A massive truck going right demolishes everything coming from the left until it meets something bigger or nothing at all.That is exactly the asteroid problem. The stack helps us track which asteroids are still "alive" and moving right, waiting to potentially collide with the next left-moving asteroid that comes along.Why Stack Is the Perfect Data Structure HereThe key observation is this — only a right-moving asteroid followed by a left-moving asteroid can collide. A left-moving asteroid might destroy several right-moving ones in a chain before it either survives or gets destroyed itself.This chain reaction behavior — where the outcome of one collision immediately triggers the possibility of another — is exactly what a stack handles naturally. The stack holds right-moving asteroids that are still alive and waiting. When a left-moving asteroid arrives, it battles the top of the stack repeatedly until either it is destroyed or no more collisions are possible.All Possible Collision ScenariosBefore looking at code it is important to understand every case that can happen:Case 1 — Right-moving asteroid (ast[i] > 0) No collision possible immediately. Push it onto the stack and move on.Case 2 — Left-moving asteroid, stack is empty Nothing to collide with. Push it onto the stack.Case 3 — Left-moving asteroid, top of stack is also left-moving (negative) Two asteroids going the same direction never meet. Push it onto the stack.Case 4 — Left-moving asteroid meets right-moving asteroid (collision!) Three sub-cases:Stack top is bigger → left-moving asteroid explodes, stack top survivesStack top is smaller → stack top explodes, left-moving asteroid continues (loop again)Same size → both explodeThe Solution — Stack Simulationpublic int[] asteroidCollision(int[] ast) { Stack<Integer> st = new Stack<>(); for (int i = 0; i < ast.length; i++) { boolean survived = true; // assume current asteroid survives // collision only happens when stack top is positive // and current asteroid is negative while (!st.empty() && st.peek() > 0 && ast[i] < 0) { if (st.peek() > Math.abs(ast[i])) { // stack top is bigger — current asteroid explodes survived = false; break; } else if (st.peek() < Math.abs(ast[i])) { // current asteroid is bigger — stack top explodes // current asteroid keeps going, check next stack element st.pop(); } else { // equal size — both explode st.pop(); survived = false; break; } } if (survived) { st.push(ast[i]); } } // build result array from stack (stack gives reverse order) int[] ans = new int[st.size()]; for (int i = ans.length - 1; i >= 0; i--) { ans[i] = st.pop(); } return ans;}Step-by-Step Dry Run — asteroids = [10, 2, -5]Let us trace exactly what happens:Processing 10:Stack is empty, no collision possiblesurvived = true → push 10Stack: [10]Processing 2:Stack top is 10 (positive), current is 2 (positive) — same direction, no collisionsurvived = true → push 2Stack: [10, 2]Processing -5:Stack top is 2 (positive), current is -5 (negative) — collision!2 < 5 → stack top smaller, pop 2. survived stays trueStack: [10]Stack top is 10 (positive), current is -5 (negative) — collision again!10 > 5 → stack top bigger, current asteroid destroyed. survived = false, breakStack: [10]survived = false → do not push -5Final stack: [10] → output: [10] ✅Step-by-Step Dry Run — asteroids = [3, 5, -6, 2, -1, 4]Processing 3: stack empty → push. Stack: [3]Processing 5: both positive, same direction → push. Stack: [3, 5]Processing -6:Collision with 5: 5 < 6 → pop 5. Stack: [3]Collision with 3: 3 < 6 → pop 3. Stack: []Stack empty → survived = true → push -6Stack: [-6]Processing 2: stack top is -6 (negative), current is 2 (positive) — same direction check fails, no collision → push. Stack: [-6, 2]Processing -1:Collision with 2: 2 > 1 → stack top bigger, -1 explodes. survived = falseStack: [-6, 2]Processing 4: stack top is 2 (positive), current is 4 (positive) — same direction → push. Stack: [-6, 2, 4]Final stack: [-6, 2, 4] → output: [-6, 2, 4] ✅Understanding the survived FlagThe survived boolean flag is the most important design decision in this solution. It tracks whether the current asteroid makes it through all collisions.It starts as true — we assume the asteroid survives until proven otherwise. It only becomes false in two situations — when the stack top is bigger (current asteroid destroyed) or when both are equal size (mutual destruction). If survived is still true after the while loop, the asteroid either won all its battles or never had any — either way it gets pushed onto the stack.This flag eliminates the need for complicated nested conditions and makes the logic clean and readable.Building the Result ArrayOne important detail — when you pop everything from a stack to build an array, the order is reversed. The stack gives you elements from top to bottom (last to first). So we fill the result array from the end to the beginning using i = ans.length - 1 going down to 0. This preserves the original left-to-right order of surviving asteroids.Time and Space ComplexityTime Complexity: O(n) — each asteroid is pushed onto the stack at most once and popped at most once. Even though there is a while loop inside the for loop, each element participates in at most one push and one pop across the entire run. Total operations stay linear.Space Complexity: O(n) — in the worst case (all asteroids moving right, no collisions) all n asteroids sit on the stack simultaneously.Common Mistakes to AvoidForgetting that same-direction asteroids never collide The collision condition is specifically st.peek() > 0 && ast[i] < 0. Two positive asteroids, two negative asteroids, or a negative followed by a positive — none of these collide. Only right then left.Not using a loop for chain collisions A single left-moving asteroid can destroy multiple right-moving ones in sequence. If you only check the stack top once instead of looping, you will miss chain destructions like in the [3, 5, -6] example.Forgetting the survived flag and always pushing Without the flag, a destroyed asteroid still gets pushed onto the stack, giving wrong results.Wrong array reconstruction from stack Forgetting that stack order is reversed and filling the array from left to right gives a backwards answer. Always fill from the last index downward.How This Problem Differs From Previous Stack ProblemsEvery previous stack problem in this series had a simple push-or-pop decision per character. Asteroid Collision introduces something new — a while loop inside the for loop. This is because one incoming asteroid can trigger multiple consecutive pops (chain collisions). The stack is no longer just storing history — it is actively participating in a simulation where multiple stored elements can be affected by a single incoming element.This is the defining characteristic of harder stack problems and is exactly what appears in problems like Largest Rectangle in Histogram and Trapping Rain Water.FAQs — People Also AskQ1. Why is a Stack used to solve LeetCode 735 Asteroid Collision? Because right-moving asteroids wait on the stack until a left-moving asteroid arrives. The left-moving asteroid battles the top of the stack repeatedly — this LIFO chain reaction behavior is exactly what a stack handles naturally and efficiently.Q2. What is the time complexity of LeetCode 735? O(n) time because each asteroid is pushed and popped at most once regardless of how many chain collisions happen. Space complexity is O(n) for the stack in the worst case.Q3. When do two asteroids NOT collide in LeetCode 735? Two asteroids never collide when both move right (both positive), both move left (both negative), or when a left-moving asteroid comes before a right-moving one — they move away from each other in that case.Q4. Is LeetCode 735 asked in coding interviews? Yes, it is commonly asked at companies like Amazon, Google, and Microsoft as a Medium stack problem. It tests whether you can handle simulation problems with multiple conditional branches and chain reactions — skills that translate directly to real world system design thinking.Q5. What is the difference between LeetCode 735 and LeetCode 496 Next Greater Element? Both use a stack and involve comparing elements. In Next Greater Element, you search forward for something bigger. In Asteroid Collision, collisions happen between the current element and stack contents, and the current element might destroy multiple previous elements in a chain before settling. The collision logic in 735 is more complex.Similar LeetCode Problems to Practice Next496. Next Greater Element I — Easy — monotonic stack pattern739. Daily Temperatures — Medium — next greater with index distance1047. Remove All Adjacent Duplicates In String — Easy — chain removal with stack84. Largest Rectangle in Histogram — Hard — advanced stack simulation503. Next Greater Element II — Medium — circular array with monotonic stackConclusionLeetCode 735 Asteroid Collision is a wonderful problem that takes the stack simulation pattern to the next level. The key insight is recognizing that only right-then-left asteroid pairs can collide, that chain collisions require a while loop not just an if statement, and that the survived flag keeps the logic clean across all cases.Work through every dry run in this article carefully — especially the [3, 5, -6, 2, -1, 4] example — because seeing chain collisions play out step by step is what makes this pattern click permanently.Once this problem makes sense, you are genuinely ready for the harder stack problems that follow. Keep going!

LeetCodeJavaStackArrayMedium