Given the top-left and bottom-right coordinates of two rectangles, determine if they overlap or not. That is, determine if any part of one rectangle overlaps with any part of the other.

You get coordinates for the rectangles as tuples of x and y, e.g. [2,5].

The function signature in TypeScript would be:

type point = [number, number];
type rectanglesOverlap = (
topLeft1: point,
bottomRight1: point,
topLeft2: point,
bottomRight2: point
) => boolean


## Brute force method

There is a direct brute force method to solving this. You iterate on one rectangle gathering all the points, then iterate on the other, returning true if any point also exists in the other.

function* iteratePoints(topLeft, bottomRight) {
for (let x = topLeft[0]; x <= bottomRight[0]; x++) {
for (let y = topLeft[1]; y <= bottomRight[1]; y++) {
yield [x, y];
}
}
}

function rectanglesOverlap(topLeft1, bottomRight1, topLeft2, bottomRight2) {
const rectangle1Points = {};
for (let point1 of iteratePoints(topLeft1, bottomRight1)) {
rectangle1Points[${point1[0]},${point1[1]}] = true;
}
for (let point2 of iteratePoints(topLeft2, bottomRight2)) {
if (rectangle1Points[${point2[0]},${point2[1]}] === true) {
return true;
}
}
return false;
}


This works but is O(mn) with m and n being the number of points in each rectangle.

## Negative edge check method

There is a simpler and faster method to determine if two rectangles overlap. The key idea is to check if they don’t overlap, which is easier. If they don’t not overlap, then they overlap.

The rectangles don’t overlap if any of these are true:

• One left edge is to the right of the other right edge.
• One top edge is below the other bottom edge.
function rectanglesOverlap(topLeft1, bottomRight1, topLeft2, bottomRight2) {
if (topLeft1[0] > bottomRight2[0] || topLeft2[0] > bottomRight1[0]) {
return false;
}
if (topLeft1[1] > bottomRight2[1] || topLeft2[1] > bottomRight1[1]) {
return false;
}
return true;
}


This is now O(1).