Katkat
Back

Compute a Point Set's Bounding Rectangle

UpstartSoftware Engineer · Online Assessment
EasySoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests the ability to find the extrema of a coordinate set in a single linear pass to define an axis-aligned bounding box.

Problem Statement

Given a list of 2D coordinates points where each point is represented as a tuple (x, y), compute the smallest axis-aligned bounding rectangle that encloses all points. An axis-aligned rectangle is defined by its bottom-left corner (min_x, min_y), its width, and its height.

Function Signature

def get_bounding_rectangle(points: list[tuple[int, int]]) -> tuple[tuple[int, int], int, int]

Constraints

  • points will contain at least one point.
  • The number of points is between 1 and 10^6.
  • Coordinates are integers between -10^9 and 10^9.

Examples

Example 1: Input: points = [(1, 1), (3, 4), (0, 2)] Output: ((0, 1), 3, 3) Explanation: Min x is 0, max x is 3 (width = 3). Min y is 1, max y is 4 (height = 3). The bottom-left corner is (0, 1).

Example 2: Input: points = [(5, 5)] Output: ((5, 5), 0, 0) Explanation: A single point results in a bounding box with zero area.

Edge Cases

  • A set containing only one point.
  • Points with negative coordinates.
  • Multiple points sharing the same x or y coordinate (resulting in 0 width or height).

Hints

Hint 1

Initialize the minimum and maximum x and y values using the coordinates of the first point in the list.

Hint 2

Iterate through the list once, updating your min and max values whenever you encounter a point outside the current range.

Hint 3

Calculate the width as (max_x - min_x) and the height as (max_y - min_y).

Follow-up questions

  • How would you modify your solution to return the coordinates of all four corners of the rectangle?
  • What is the time and space complexity of your approach, and can it be improved?
  • How would you handle the input if it were provided as a stream of points where you don't know the total number of points in advance?