Overlap Area of Two Axis-Aligned Rectangles

Reported in interviews at Jump Trading Zillow

Problem statement

Two rectangles in the plane have sides parallel to the coordinate axes. Rectangle 1 has bottom-left corner $(x_{11}, y_{11})$ and top-right corner $(x_{12}, y_{12})$; rectangle 2 has bottom-left $(x_{21}, y_{21})$ and top-right $(x_{22}, y_{22})$.

Return the area of their overlap, or 0 if they do not overlap.

Example

  • Rectangle 1 $= (0,0)$ to $(4,4)$, rectangle 2 $= (2,1)$ to $(6,3)$ -> overlap is the box $(2,1)$ to $(4,3)$, area $2 \times 2 = 4$.
Show hint

Can a two-dimensional overlap be broken into simpler one-dimensional pieces?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems