This problem looks busy at first, but the accepted solution is built around one steady invariant. For 836. Rectangle Overlap, the solution in this repository is mainly a two pointers solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are isRectangleOverlap.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(1)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01/**
02A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.
03
04Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.
05
06Given two (axis-aligned) rectangles, return whether they overlap.
07
08Example 1:
09
10Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
11Output: true
12Example 2:
13
14Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
15Output: false
16Notes:
17
18Both rectangles rec1 and rec2 are lists of 4 integers.
19All coordinates in rectangles will be between -10^9 and 10^9.
20**/
21
22/**
23Time and Space Complexity: O(1)
24**/
25
26//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Rectangle Overlap.
27//Memory Usage: 8.2 MB, less than 100.00% of C++ online submissions for Rectangle Overlap.
28class Solution {
29public:
30 bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
31 //min(x22-x11, x12-x21)
32 //min(y22-y11, y12-y21)
33 return min(rec2[2]-rec1[0], rec1[2]-rec2[0]) > 0 && \
34 min(rec2[3]-rec1[1], rec1[3]-rec2[1]) > 0;
35 }
36};Cost