What Is a Bounding Box? The Geometry Primitive Every Grid Problem Hides
- Axis-aligned bounding box (AABB) = four extreme values (min_x, max_x, min_y, max_y) enclosing a point set, computed in a single O(n) pass
- Overlap check = two independent interval overlap tests, O(1) with six comparisons
- Grid off-by-one: cell width is
max_col - min_col + 1; coordinate difference is a length, not a count - Bounding box vs convex hull: AABB is O(n) and loose; convex hull is O(n log n) and tight — use AABB as the cheap filter first
- LeetCode 3195 (minimum area covering all ones) and LeetCode 939 (minimum area rectangle) are the canonical bounding box interview problems
- Interview signal: "minimum enclosing rectangle with axis-aligned sides" means scan for four extremes in one pass — no more complexity needed
You've already computed hundreds of bounding boxes. You just called them min_row, max_row, min_col, max_col.
Every time you scan a grid to find the smallest rectangle enclosing a region, you're computing a bounding box. Same when you write those four tracking variables at the top of a traversal. Same when an interviewer says "find the minimum enclosing rectangle" and you just... track extremes without thinking too hard about it. The bounding box is the simplest shape that completely contains a set of points, a region, or an object. Most engineers never name it explicitly, which means they miss the pattern when it shows up wearing a disguise.
You've been speaking bounding-box prose this whole time. Molière would be proud.
Four Numbers, One Box
A bounding box (formally, an axis-aligned bounding box, or AABB) is the smallest rectangle with sides parallel to the coordinate axes that encloses a set of points.
Four values fully define it:
min_x: leftmost x-coordinatemax_x: rightmost x-coordinatemin_y: bottommost y-coordinatemax_y: topmost y-coordinate
The rectangle runs from (min_x, min_y) to (max_x, max_y). Area: (max_x - min_x) * (max_y - min_y). No trigonometry, no rotation matrices, no eigenvalues. Just four extreme values.
That's it. That's the whole data structure. I'm slightly embarrassed that I have to write 1,500 words about this.
One Pass Is All You Need
Computing the bounding box of n points takes a single scan: O(n) time and O(1) extra space.
def bounding_box(points: list[tuple[int, int]]) -> tuple[int, int, int, int]: min_x = min_y = float('inf') max_x = max_y = float('-inf') for x, y in points: min_x = min(min_x, x) max_x = max(max_x, x) min_y = min(min_y, y) max_y = max(max_y, y) return min_x, max_x, min_y, max_y
On a grid: scan all cells with value 1, track the four extremes. Done. You do this constantly. You just rarely call it by name.
The anticlimactic part is that "bounding box computation" sounds like it should involve at least three coordinate systems and possibly a meditation retreat. It is, in fact, four variables and a for loop. Computer science is humbling like that.
When the Box Can Rotate
The "axis-aligned" qualifier matters. Sides run parallel to the x and y axes, so the box never tilts. This is the version you see in nearly every interview problem involving rectangles.
The alternative is an oriented bounding box (OBB): a rectangle that can rotate to fit the shape more tightly. An OBB always has area less than or equal to the AABB, but computing it requires finding the shape's principal axes through rotating calipers or covariance matrix analysis. That is a genuinely different problem. One that takes much longer to implement and explain on a whiteboard.
When an interview says "minimum area rectangle," ask explicitly whether sides must be axis-aligned. LeetCode 939 constrains to axis-aligned. LeetCode 963 does not. The answer to that one clarifying question determines whether you write ten lines of code or spend the next 30 minutes doing things no reasonable person should do in 45 minutes.
This is the only question that doubles your chance of finishing on time.
Two Boxes, Six Comparisons
Checking whether two AABBs overlap takes six comparisons, O(1), and it's the first step in almost every collision detection system ever written.
def boxes_overlap( a_min_x: int, a_max_x: int, a_min_y: int, a_max_y: int, b_min_x: int, b_max_x: int, b_min_y: int, b_max_y: int, ) -> bool: x_overlap = a_min_x <= b_max_x and b_min_x <= a_max_x y_overlap = a_min_y <= b_max_y and b_min_y <= a_max_y return x_overlap and y_overlap
The inverse is easier to remember: boxes do NOT overlap if one is entirely to the left, right, above, or below the other. Negate any of those four conditions and they overlap.
Every game engine on the planet runs this test before doing any real collision detection. Polygon intersection math is expensive. A bounding box check is six comparisons and essentially free. If the boxes don't even touch, skip the expensive test entirely. The fancy physics engine gatekeeps on min/max arithmetic.
This "no-gap-on-any-axis" logic is the same principle behind interval overlap problems (LeetCode 56). A bounding box check is just two independent interval overlap checks running simultaneously. You've probably solved the 1D version without realizing you were doing 2D collision detection.
Where This Shows Up in Interviews
Grid problems with connected regions
Any problem asking for the "minimum rectangle containing all 1s" or "smallest bounding area of an island" is a bounding box problem. Scan the relevant cells and track the four extremes.
LeetCode 3195 is the purest form. Iterate every cell. Find the four extremes among cells equal to 1. Return (max_row - min_row + 1) * (max_col - min_col + 1).
def minimumArea(grid: list[list[int]]) -> int: min_r = min_c = float('inf') max_r = max_c = float('-inf') for r, row in enumerate(grid): for c, val in enumerate(row): if val == 1: min_r = min(min_r, r) max_r = max(max_r, r) min_c = min(min_c, c) max_c = max(max_c, c) return (max_r - min_r + 1) * (max_c - min_c + 1)
O(m * n) time, O(1) space. Nothing clever, just knowing what to track. The candidates who struggle here aren't confused about the algorithm. They just don't recognize that "minimum enclosing rectangle with sides parallel to the axes" is a bounding box problem. The name is the unlock.
Point set problems
LeetCode 939 gives you a set of points and asks for the smallest axis-aligned rectangle they can form. Two points on a diagonal determine the other two corners. Store points in a hash set, then for every candidate pair of diagonal corners, check whether the other two exist.
def minAreaRect(points: list[list[int]]) -> int: point_set = {(x, y) for x, y in points} min_area = float('inf') for i in range(len(points)): for j in range(i + 1, len(points)): x1, y1 = points[i] x2, y2 = points[j] if x1 != x2 and y1 != y2: if (x1, y2) in point_set and (x2, y1) in point_set: area = abs(x2 - x1) * abs(y2 - y1) min_area = min(min_area, area) return min_area if min_area != float('inf') else 0
The check x1 != x2 and y1 != y2 ensures the two points are genuinely diagonal, not just sitting on the same row or column. O(n²) time, O(n) space.
As a pruning step in harder problems
Bounding boxes show up as a first-pass filter before expensive geometry. In a sweep line algorithm, you build bounding boxes around groups of shapes to prune the search space before doing exact overlap tests.
In computational geometry, bounding boxes are the cheapest approximation available. Build them first. If they don't overlap, nothing inside them overlaps either, and you skip all the hard work. This is the professional way to not do work that doesn't need doing.
Bounding Box vs Convex Hull: Speed vs Accuracy
The bounding box and the convex hull both describe the "outer boundary" of a point set, but they answer different questions.
| Property | Bounding Box (AABB) | Convex Hull |
|---|---|---|
| Shape | Rectangle | Polygon (tight fit) |
| Computation | O(n) | O(n log n) |
| Tightness | Loose | Tight |
| Sides | Parallel to axes | Arbitrary angles |
| Common use | Fast approximation | Exact boundary needed |
Use the bounding box for speed; use the convex hull for accuracy. Many algorithms take one O(n) pass for the bounding box to rule things out, then fall back to convex hull math only if that test passes. The bounding box is the bouncer who checks if you're even in the right zip code. The convex hull is the actual ID check at the door.
The Off-by-One Trap
Here's where people lose points right at the finish line. If you're working with grid cells (not coordinates), the width of the bounding box is max_col - min_col + 1, not max_col - min_col.
A rectangle from column 2 to column 4 spans 3 columns, not 2. You can verify this on your fingers right now. You will still get it wrong under interview pressure. This is not a skill issue; it is a brain issue.
# Grid cells: include both endpoints width = max_col - min_col + 1 height = max_row - min_row + 1 # Geometric coordinates: difference is the length width = max_x - min_x height = max_y - min_y
Grid indices are positions of cells. Coordinate differences are lengths. Know which one you're computing before you write the return statement, not after you fail four test cases and start second-guessing your entire approach.
This is the kind of thing that turns a correct algorithm into a "great approach, wrong answer" write-up in the interviewer's notes. You catch it immediately if you dry-run a 3x3 example before declaring victory. So do that. Every time.
What Interviewers Actually Want to See
When a problem says "find the minimum enclosing rectangle with sides parallel to the axes," the intended solution is a bounding box scan. Reaching for something more complex is overengineering, which interviewers read as poor pattern recognition.
The signal they want: you recognize that four extreme values fully determine an axis-aligned bounding box, and you compute all four in a single pass. State O(n) time, O(1) space, and handle the edge case where no valid shape exists (return 0 or whatever the problem specifies, not float('inf')).
If they ask "what if the rectangle doesn't have to be axis-aligned?" that's your opening. Axis-aligned is O(n). Oriented bounding boxes need rotating calipers or a convex hull step and jump to at least O(n log n). You now sound like you've read more than just the top-voted LeetCode solution.
The harder part for most people isn't the code itself. It's explaining spatial reasoning out loud to another human being in real time. If you want to practice that specifically, SpaceComplexity runs voice-based mock interviews where the AI probes exactly how you verbalize geometric intuitions like this. Many candidates who solve these cold on paper go quiet when asked to justify their approach in words. That's the gap.