Rectangle Overlap

📋

Problem

Imagine you have two windows on your computer screen, and you want to check if they overlap at all. This problem asks you to determine if two rectangles on a plane overlap.

Given two axis-aligned rectangles represented as lists of four integers [x1, y1, x2, y2], where (x1, y1) are the coordinates of the bottom-left corner and (x2, y2) are the coordinates of the top-right corner, determine if the two rectangles overlap. Return true if they overlap, otherwise false.

Coordinates are integers within the range [-10^9, 10^9]Rectangles are axis-aligned (edges parallel to axes)Input rectangles may be degenerate (zero area)

Edge cases: Rectangles touch at exactly one corner → falseOne rectangle completely inside another → trueRectangles share an edge but no area → false

</>

IDE

def isRectangleOverlap(rec1: list[int], rec2: list[int]) -> bool:public boolean isRectangleOverlap(int[] rec1, int[] rec2)bool isRectangleOverlap(vector<int> rec1, vector<int> rec2)function isRectangleOverlap(rec1, rec2)

def isRectangleOverlap(rec1, rec2):
    # Write your solution here
    pass

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isRectangleOverlap(vector<int> rec1, vector<int> rec2) {
    // Write your solution here
    return false;
}

function isRectangleOverlap(rec1, rec2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrectly returning false when rectangles overlap partially or fully due to using non-strict inequalities or missing axis checks.✅ Use strict inequality checks for both axes: return false if rec1[2] <= rec2[0] or rec2[2] <= rec1[0] or rec1[3] <= rec2[1] or rec2[3] <= rec1[1]. Otherwise, return true.

Wrong: Returning true when rectangles only touch at edges or corners without overlapping area.✅ Use strict inequalities to exclude edge or corner touching: return false if edges meet exactly without positive overlap.

Wrong: Treating zero-area rectangles as overlapping.✅ Check if either rectangle has zero width or height (rec[0] == rec[2] or rec[1] == rec[3]) and return false in those cases.

Wrong: Failing to detect full containment overlap when one rectangle is inside another.✅ Ensure overlap condition checks for positive intersection intervals on both axes, not just partial overlaps.

Wrong: TLEUsing loops or recursion instead of direct coordinate comparisons.✅ Implement O(1) solution by direct coordinate comparisons without loops.

✓

Test Cases

Focus on boundary conditions like zero-area rectangles and exact edge touching.

Test your logic against tricky partial overlaps and identical rectangles.

Ensure your solution runs in constant time without loops or recursion.

t1_01basic

Input{"rec1":[0,0,2,2],"rec2":[1,1,3,3]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The rectangles overlap in the area from (1,1) to (2,2).

💡 Check if one rectangle is completely to the left or right of the other.

💡 Also check if one rectangle is completely above or below the other.

💡 Return false if any of these conditions hold; otherwise, return true.

Why it failed: Returned false incorrectly: likely missed that overlapping area exists when edges intersect strictly inside. Fix by checking if rec1[2] <= rec2[0] or rec2[2] <= rec1[0] and similarly for y-coordinates.

✓ Correctly identified overlapping rectangles.

t1_02basic

Input{"rec1":[0,0,1,1],"rec2":[1,0,2,1]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Rectangles share an edge at x=1 but do not overlap in area.

💡 Remember that touching edges without area overlap means no overlap.

💡 Check if the right edge of one rectangle equals the left edge of the other.

💡 Return false if edges just touch without overlapping area.

Why it failed: Returned true incorrectly: failed to exclude cases where rectangles only share an edge without area overlap. Fix by using strict inequality in overlap checks.

✓ Correctly identified no overlap when rectangles only share an edge.

t2_01edge

Input{"rec1":[0,0,0,0],"rec2":[0,0,0,0]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Both rectangles are points with zero area; no overlap.

💡 Check if rectangles have zero width or height.

💡 Rectangles with zero area cannot overlap with any rectangle.

💡 Return false if either rectangle has zero width or height.

Why it failed: Returned true incorrectly: did not handle zero-area rectangles. Fix by checking if rec1[0] == rec1[2] or rec1[1] == rec1[3] or similarly for rec2 and returning false.

✓ Correctly handled zero-area rectangles as non-overlapping.

t2_02edge

Input{"rec1":[0,0,5,5],"rec2":[1,1,2,2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Second rectangle is completely inside the first; they overlap.

💡 Check if one rectangle is fully inside the other.

💡 Overlap occurs if intervals on both axes intersect with positive length.

💡 Return true if inner rectangle's edges lie strictly inside outer rectangle's edges.

Why it failed: Returned false incorrectly: failed to detect full containment as overlap. Fix by ensuring overlap condition checks for any positive intersection on both axes.

✓ Correctly identified full containment as overlap.

t2_03edge

Input{"rec1":[0,0,2,2],"rec2":[2,2,3,3]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Rectangles touch exactly at one corner (2,2) but do not overlap in area.

💡 Touching at a single point is not considered overlap.

💡 Check if edges meet exactly without positive area intersection.

💡 Return false if overlap area is zero.

Why it failed: Returned true incorrectly: treated corner touching as overlap. Fix by using strict inequalities in overlap checks.

✓ Correctly identified no overlap when rectangles touch only at a corner.

t3_01corner

Input{"rec1":[0,0,3,3],"rec2":[1,1,4,4]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Overlap area from (1,1) to (3,3); tests correct handling of partial overlap.

💡 Check overlap on both x and y axes independently.

💡 Use max of left edges and min of right edges to find overlap interval.

💡 Return true if overlap intervals on both axes have positive length.

Why it failed: Returned false incorrectly: likely used a greedy approach that only checks one axis or fails to check both axes. Fix by verifying overlap on both axes independently.

✓ Correctly handled partial overlap on both axes.

t3_02corner

Input{"rec1":[0,0,2,2],"rec2":[2,1,3,3]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Rectangles share vertical edge at x=2 but no area overlap; tests strict inequality handling.

💡 Check if edges just touch without overlapping area.

💡 Overlap requires strictly greater than conditions, not greater or equal.

💡 Return false if overlap intervals have zero length.

Why it failed: Returned true incorrectly: failed to use strict inequality in overlap condition. Fix by changing <= to < in comparisons.

✓ Correctly identified no overlap when rectangles share an edge only.

t3_03corner

Input{"rec1":[0,0,1,1],"rec2":[0,0,1,1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Rectangles are identical; tests that full overlap is detected.

💡 Check if rectangles have identical coordinates.

💡 Identical rectangles overlap fully.

💡 Return true if intervals on both axes overlap with positive length.

Why it failed: Returned false incorrectly: failed to handle identical rectangles as overlapping. Fix by ensuring overlap condition includes equality with positive area (width and height > 0).

✓ Correctly identified identical rectangles as overlapping.

t4_01performance

Input{"rec1":[-1000000000,-1000000000,1000000000,1000000000],"rec2":[-999999999,-999999999,999999999,999999999]}

Expectednull

⏱ Performance - must finish in 2000ms

Large coordinate values at constraint boundary; O(1) time expected to complete within 2s.

💡 This problem is O(1) time complexity regardless of input size.

💡 Check only coordinate comparisons without loops.

💡 Avoid unnecessary computations or data structures.

Why it failed: TLE: likely used an inefficient approach with loops or recursion. Fix by using direct coordinate comparisons with O(1) complexity.

✓ Efficient O(1) complexity confirmed.

Practice

1. Given the following code snippet, what is the output of clock.angleClock(3, 30)?

class ClockAngle:
    def __init__(self):
        self.precomputed = [[0]*60 for _ in range(12)]
        for h in range(12):
            for m in range(60):
                hour_angle = h * 30 + m * 0.5
                minute_angle = m * 6
                diff = abs(hour_angle - minute_angle)
                self.precomputed[h][m] = min(diff, 360 - diff)

    def angleClock(self, hour: int, minutes: int) -> float:
        return self.precomputed[hour % 12][minutes]

clock = ClockAngle()
print(clock.angleClock(3, 30))

easy

A. 105

B. 90

C. 75

D. 60

Solution

1. Step 1: Calculate hour hand angle at 3:30

   Hour angle = 3 * 30 + 30 * 0.5 = 90 + 15 = 105 degrees.

2. Step 2: Calculate minute hand angle and difference

   Minute angle = 30 * 6 = 180 degrees. Difference = |105 - 180| = 75 degrees. Minimal angle = 75 degrees.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Precomputed table stores minimal angle correctly -> 75 [OK]

Hint: Hour hand moves 0.5° per minute, not fixed 30° per hour [OK]

Common Mistakes:

• Using only hour * 30 without minute adjustment
• Returning absolute difference without min(., 360 - .)

2. You are given a list of points on a 2D plane. Your task is to find the rectangle with the minimum area such that all four corners are points from the list. Which approach guarantees finding the optimal solution efficiently?

easy

A. Use a hash set to store points and check pairs of points as diagonals to find rectangles.

B. Use dynamic programming to build rectangles from smaller sub-rectangles.

C. Use a greedy approach by sorting points and selecting closest pairs to form rectangles.

D. Use a brute force approach checking all quadruples of points to find rectangles.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding rectangles formed by points with minimum area, which involves checking pairs of points as potential diagonals.

2. Step 2: Evaluate approaches

   Brute force (checking all quadruples) is correct but inefficient (O(n^4)). Greedy and DP approaches do not guarantee correctness or efficiency here. Using a hash set to check existence of complementary points for diagonals is both correct and efficient (O(n^2)).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set + diagonal pairs -> optimal and correct [OK]

Hint: Hash set + diagonal pairs is key [OK]

Common Mistakes:

• Thinking greedy or DP solves this efficiently
• Using brute force without pruning

3. You need to reverse the digits of a 32-bit signed integer, returning 0 if the reversed integer overflows. Which approach guarantees an optimal solution that handles overflow correctly without converting the integer to a string?

easy

A. Greedy approach that swaps digits from ends until the middle is reached

B. Dynamic programming to store reversed prefixes and build the result

C. Brute force string conversion and reversal without overflow checks

D. Recursive digit extraction with overflow checks before each digit append

Solution

1. Step 1: Understand problem constraints

   The problem requires reversing digits without string conversion and must handle overflow safely.

2. Step 2: Identify approach that meets constraints

   Recursive digit extraction with overflow checks ensures digits are reversed one by one and stops if overflow would occur, guaranteeing correctness and optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursive digit extraction handles overflow and sign correctly [OK]

Hint: Overflow-safe digit extraction is key [OK]

Common Mistakes:

• Using string reversal without overflow checks
• Greedy swaps fail on overflow
• DP is unnecessary overhead

4. You need to find the nth number whose prime factors only include 2, 3, and 5. Which approach guarantees an optimal solution that efficiently generates these numbers without checking every integer sequentially?

easy

A. Use a min-heap (priority queue) to always extract the smallest candidate and generate new multiples, avoiding duplicates.

B. Use a greedy algorithm that picks the smallest next multiple of 2, 3, or 5 from previously found numbers.

C. Use dynamic programming with a 2D table to store all factors and their counts for each number up to n.

D. Use brute force by checking each integer sequentially and verifying if its prime factors are only 2, 3, and 5.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating numbers whose prime factors are only 2, 3, and 5, known as ugly numbers.

2. Step 2: Evaluate approaches for efficiency and correctness

   Brute force is too slow; min-heap approach is efficient but can be optimized further; dynamic programming with a 2D table is overcomplicated. The greedy approach with three pointers picks the smallest next multiple of 2, 3, or 5 from previously found numbers, efficiently generating the sequence without duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three-pointer greedy approach efficiently generates ugly numbers in ascending order without duplicates [OK]

Hint: Three-pointer greedy approach avoids duplicates and generates numbers in order [OK]

Common Mistakes:

• Assuming min-heap is the only efficient approach
• Thinking DP with 2D table is needed for prime factorization
• Believing brute force is efficient enough for large n

5. Suppose the clock can show times with fractional minutes (e.g., 3:30.5). Which modification to the precomputation approach is necessary to handle queries with fractional minutes correctly?

hard

A. Increase precomputed table size to include fractional minute indices (e.g., 60 * 10 for tenths of minutes).

B. Precompute only hour angles and calculate minute angles on the fly for fractional minutes.

C. Round fractional minutes down to nearest integer and use existing precomputed table.

D. Use the brute force direct calculation formula at query time instead of precomputation.

Solution

1. Step 1: Understand fractional minute impact

   Precomputing all fractional minute values is infeasible due to infinite possibilities.

2. Step 2: Evaluate options

   Increasing table size exponentially is impractical; rounding loses precision; precomputing only hour angles is insufficient because minute angle varies continuously.

3. Step 3: Use direct calculation

   Calculating angles on the fly with the formula handles fractional minutes accurately and efficiently.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Direct formula supports fractional inputs without huge memory [OK]

Hint: Precompute only works for discrete inputs; fractional requires formula [OK]

Common Mistakes:

• Trying to precompute infinite fractional values
• Rounding fractional minutes losing accuracy