Compute a Point Set's Bounding Rectangle
Company: Upstart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
# Compute a Point Set's Bounding Rectangle
Given two-dimensional integer points, return the smallest axis-aligned rectangle containing every point. Represent it as `[min_x, min_y, width, height]`.
### Function Signature
```python
def bounding_rectangle(points: list[list[int]]) -> list[int]:
...
```
### Example
```text
Input: points = [[2, 5], [-1, 4], [3, -2]]
Output: [-1, -2, 4, 7]
```
### Constraints
- `1 <= len(points) <= 200_000`
- Every point is exactly `[x, y]`.
- Coordinates are signed 64-bit integers.
### Clarifications
- `width = max_x - min_x` and `height = max_y - min_y`.
- A single point therefore produces width and height zero.
- Duplicate points are allowed.
- Do not mutate the input.
### Hints
- Maintain four extrema in one pass.
Quick Answer: Compute the smallest axis-aligned bounding rectangle for a nonempty set of two-dimensional integer points. Track minimum and maximum coordinates in one pass, then return the lower corner, width, and height without mutating the input.
Return the smallest axis-aligned rectangle containing all integer points as [min_x, min_y, width, height], where width and height are coordinate differences.
Constraints
- There is at least one point and at most 200,000.
- Every point contains exactly two signed 64-bit integers.
- Duplicate points are allowed.
- Inputs are not mutated.
Examples
Input: ([[2,5],[-1,4],[3,-2]],)
Expected Output: [-1, -2, 4, 7]
Explanation: The supplied example.
Input: ([[0,0]],)
Expected Output: [0, 0, 0, 0]
Explanation: A single point has zero width and height.
Hints
- Initialize all four extrema from the first point, then update them in one pass.