Rectangle Overlap

▶

Steps

setup

Setup Input Arrays

Initialize the input arrays rec1 and rec2 with their respective coordinates.

💡 Setting up the input arrays clearly shows the rectangle coordinates we will use throughout the algorithm.

Line:

def isRectangleOverlap(rec1, rec2):

💡 The problem is defined by two arrays representing rectangles.

compare

Calculate max left x-coordinate

Compare the left x-coordinates of both rectangles: rec1[0] = 0 and rec2[0] = 1, then find the maximum.

💡 Finding the maximum left edge determines the start of the potential overlap on the x-axis.

Line:

max(rec1[0], rec2[0])

💡 Overlap on x-axis cannot start before the rightmost left edge.

compare

Calculate min right x-coordinate

Compare the right x-coordinates of both rectangles: rec1[2] = 2 and rec2[2] = 3, then find the minimum.

💡 Finding the minimum right edge determines the end of the potential overlap on the x-axis.

Line:

min(rec1[2], rec2[2])

💡 Overlap on x-axis cannot extend beyond the leftmost right edge.

calculate

Compute x-axis overlap length

Subtract max left x (1) from min right x (2) to get x_overlap = 1.

💡 The overlap length on the x-axis must be positive for rectangles to overlap horizontally.

Line:

x_overlap = min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])

💡 Positive x_overlap means rectangles intersect horizontally.

compare

Calculate max bottom y-coordinate

Compare the bottom y-coordinates of both rectangles: rec1[1] = 0 and rec2[1] = 1, then find the maximum.

💡 Finding the maximum bottom edge determines the start of the potential overlap on the y-axis.

Line:

max(rec1[1], rec2[1])

💡 Overlap on y-axis cannot start below the higher bottom edge.

compare

Calculate min top y-coordinate

Compare the top y-coordinates of both rectangles: rec1[3] = 2 and rec2[3] = 3, then find the minimum.

💡 Finding the minimum top edge determines the end of the potential overlap on the y-axis.

Line:

min(rec1[3], rec2[3])

💡 Overlap on y-axis cannot extend above the lower top edge.

calculate

Compute y-axis overlap length

Subtract max bottom y (1) from min top y (2) to get y_overlap = 1.

💡 The overlap length on the y-axis must be positive for rectangles to overlap vertically.

Line:

y_overlap = min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])

💡 Positive y_overlap means rectangles intersect vertically.

compare

Check if x_overlap > 0

Check if the horizontal overlap length x_overlap = 1 is greater than zero.

💡 A positive x_overlap is necessary for any horizontal intersection.

Line:

x_overlap > 0

💡 Rectangles overlap horizontally.

compare

Check if y_overlap > 0

Check if the vertical overlap length y_overlap = 1 is greater than zero.

💡 A positive y_overlap is necessary for any vertical intersection.

Line:

y_overlap > 0

💡 Rectangles overlap vertically.

decision

Determine final overlap result

Return true because both x_overlap > 0 and y_overlap > 0, indicating rectangles overlap.

💡 Both horizontal and vertical overlaps must be positive for rectangles to overlap.

Line:

return x_overlap > 0 and y_overlap > 0

💡 Overlap exists only if both axes overlap positively.

def isRectangleOverlap(rec1, rec2):
    # STEP 2 & 3: Calculate x-axis overlap boundaries
    x_overlap = min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])  # STEP 4
    # STEP 5 & 6: Calculate y-axis overlap boundaries
    y_overlap = min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])  # STEP 7
    # STEP 8 & 9: Check if overlaps are positive
    return x_overlap > 0 and y_overlap > 0  # STEP 10

if __name__ == '__main__':
    print(isRectangleOverlap([0,0,2,2], [1,1,3,3]))  # True
    print(isRectangleOverlap([0,0,1,1], [1,0,2,1]))  # False

📊

Rectangle Overlap - Watch the Algorithm Execute, Step by Step

Watching each calculation and comparison helps you understand how the algorithm determines overlap without guessing or complex geometry.

setup

0

0

0

1

2

2

2

3

1

4

1

5

3

6

3

7

compare

left_rec1

0

0

0

1

2

2

2

3

left_rec2

1

4

1

5

3

6

3

7

Result: 1

compare

0

0

0

1

right_rec1

2

2

2

3

1

4

1

5

right_rec2

3

6

3

7

Result: 2

calculate

0

0

0

1

2

2

2

3

1

4

1

5

3

6

3

7

Result: 1

compare

0

0

bottom_rec1

0

1

2

2

2

3

1

4

bottom_rec2

1

5

3

6

3

7

Result: 1

compare

0

0

0

1

2

2

top_rec1

2

3

1

4

1

5

3

6

top_rec2

3

7

Result: 2

calculate

0

0

0

1

2

2

2

3

1

4

1

5

3

6

3

7

Result: 1

compare

0

0

0

1

2

2

2

3

1

4

1

5

3

6

3

7

Result: true

compare

0

0

0

1

2

2

2

3

1

4

1

5

3

6

3

7

Result: true

record

0

0

0

1

2

2

2

3

1

4

1

5

3

6

3

7

Result: true

Key Takeaways

✓ Overlap is determined by comparing edges using max and min functions, not by complex geometry.

This insight is hard to see from code alone because it abstracts the geometric intuition into simple math operations.

✓ Both horizontal and vertical overlaps must be positive for rectangles to truly overlap.

Visualizing the separate x and y overlap calculations clarifies why both conditions are necessary.

✓ The algorithm efficiently checks overlap with just four coordinate comparisons and two subtractions.

Seeing each comparison and calculation step-by-step reveals the minimal operations needed.

Practice

1. Consider the following Python code snippet implementing the optimal approach for Max Points on a Line:

from collections import defaultdict
import math

def maxPoints(points):
    n = len(points)
    if n <= 2:
        return n
    max_points = 1
    points.sort()
    for i in range(n):
        if max_points >= n - i or max_points > n // 2:
            break
        slopes = defaultdict(int)
        duplicates = 0
        for j in range(i + 1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            if dx == 0 and dy == 0:
                duplicates += 1
                continue
            gcd = math.gcd(dy, dx)
            if gcd != 0:
                dy //= gcd
                dx //= gcd
            if dx < 0:
                dx = -dx
                dy = -dy
            slopes[(dy, dx)] += 1
        curr_max = max(slopes.values(), default=0) + duplicates + 1
        max_points = max(max_points, curr_max)
    return max_points

points = [(1,1), (2,2), (3,3)]
print(maxPoints(points))

What is the output of this code?

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace outer loop with i=0

   Points sorted: [(1,1), (2,2), (3,3)]. For i=0, slopes computed with points (2,2) and (3,3) both have slope (1,1) after normalization.

2. Step 2: Calculate max points for i=0

   Slopes[(1,1)] = 2, duplicates=0, so curr_max = 2 + 0 + 1 = 3. max_points updated to 3. Early termination triggers next iterations skipped.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All points lie on the same line y=x, so output is 3 [OK]

Hint: All points on line -> max points equals total points [OK]

Common Mistakes:

• Off-by-one in counting duplicates or base point
• Ignoring early termination condition

2. Given the following code snippet for converting Roman numerals to integers, what is the value of result after processing the input "IX"?

easy

A. 11

B. 1

C. 9

D. 0

Solution

1. Step 1: Trace iteration i=0 with s[i]='I'

   curr = 1, next_val = 10 (value of 'X'), since 1 < 10, subtract curr: result = 0 - 1 = -1

2. Step 2: Trace iteration i=1 with s[i]='X'

   curr = 10, next_val = 0 (no next), since 10 >= 0, add curr: result = -1 + 10 = 9

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Result matches expected integer for "IX" [OK]

Hint: Subtract when current < next, else add [OK]

Common Mistakes:

• Adding all values without subtraction
• Off-by-one errors in indexing
• Ignoring boundary conditions

3. What is the time complexity of the optimal approach for the Max Points on a Line problem that uses sorting, early termination, and slope normalization with a hash map?

medium

A. O(n^2) with early termination, but worst case still quadratic due to pairwise slope checks.

B. O(n^2) because for each point, slopes to all other points are computed and stored.

C. O(n^3) due to triple nested loops over points and slope calculations.

D. O(n log n) because sorting dominates and slope computations are constant time.

Solution

1. Step 1: Identify loops and operations

   Outer loop runs up to n times, inner loop up to n times, slope calculation and gcd normalization are O(1).

2. Step 2: Consider sorting and early termination

   Sorting is O(n log n), but nested loops dominate with O(n^2). Early termination can reduce average runtime but worst case remains O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Early termination improves average but worst case is still quadratic [OK]

Hint: Nested loops over points dominate complexity [OK]

Common Mistakes:

• Confusing sorting cost as dominant
• Assuming early termination reduces worst-case complexity

4. The following code attempts to check if an integer is a palindrome by reversing half of its digits. Which line contains a subtle bug that causes incorrect results for inputs like 10 or negative numbers?

medium

A. Line 6: return x == reversed_half or x == reversed_half // 10

B. Line 2: reversed_half = 0

C. Line 1: def is_palindrome(x: int) -> bool:

D. Line 3: while x > reversed_half:

Solution

1. Step 1: Identify missing edge case handling

   Negative numbers and numbers ending with zero (except zero itself) are not handled before the loop.

2. Step 2: Analyze loop condition

   Without checking negatives or trailing zeros, the loop condition allows incorrect inputs to proceed, causing wrong results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding pre-check for negatives and trailing zeros before loop fixes bug [OK]

Hint: Check input constraints before main logic to avoid subtle bugs [OK]

Common Mistakes:

• Ignoring negative input check
• Not handling trailing zeros
• Assuming loop condition suffices

5. Consider the following buggy code for finding the nth ugly number. Which line contains the subtle bug that causes incorrect results for some inputs?

import heapq

def nthUglyNumber(n):
    heap = [1]
    seen = set()
    ugly = 1
    for _ in range(n):
        ugly = heapq.heappop(heap)
        for factor in [2, 3, 5]:
            new_ugly = ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)
    return ugly

medium

A. Line 3: Initializing seen as an empty set instead of containing 1

B. Line 6: Popping from heap before checking if heap is empty

C. Line 9: Multiplying ugly by factor without checking for overflow

D. Line 11: Adding new_ugly to seen before pushing to heap

Solution

1. Step 1: Check initialization of seen set

   The seen set is empty initially, but 1 is already in the heap. This causes duplicates because 1 is not marked as seen.

2. Step 2: Understand impact of missing 1 in seen

   Without 1 in seen, the algorithm may push 1 multiple times, causing duplicates and incorrect nth ugly number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding 1 to seen fixes duplicates and ensures correctness [OK]

Hint: Always mark initial heap elements as seen to avoid duplicates [OK]

Common Mistakes:

• Forgetting to add initial element to seen set
• Assuming heap uniqueness without seen tracking
• Ignoring edge cases with initial values