Quick Overview

Maximize point coverage with an axis-aligned rectangle under a perimeter budget, including boundary points and repeated coordinates.

Cover the Most Points with an Axis-Aligned Rectangle of Bounded Perimeter

Company: American

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Place an axis-aligned rectangle with perimeter at most P to cover as many supplied two-dimensional points as possible. ### Function Signature `maximum_covered_points(points: list[list[int]], P: int) -> int` ### Geometry Rules - Rectangle sides are parallel to the coordinate axes. - Its width and height are nonnegative real numbers and must satisfy `2 * (width + height) <= P`. - For this exercise, zero width or zero height is allowed, so collinear or coincident points can be covered by a degenerate rectangle. - Points on the boundary count as covered. - Repeated coordinates count as separate input points. - Rectangle coordinates need not be integers. The at-most perimeter, boundary inclusion, and degenerate-rectangle rules are explicit conventions for this exercise. ### Output Return the maximum number of input points covered by one such rectangle. Return 0 for no points. ### Constraints - `0 <= len(points) <= 200`. - Each point is `[x, y]` with integer coordinates in `[-1000000, 1000000]`. - `0 <= P <= 1000000000`. ### Examples Input: `points = [[0,0],[2,0],[0,1],[2,1],[10,10]], P = 6` Output: `4` A width-2, height-1 rectangle covers the first four points. Input: `points = [[1,1],[1,1],[2,1]], P = 0` Output: `2` Input: `points = [[0,0],[3,0]], P = 5` Output: `1`

Overview: Maximize point coverage with an axis-aligned rectangle under a perimeter budget, including boundary points and repeated coordinates.

Read the full American Software Engineer interview experience this question came from

You are given a list of points on a two-dimensional plane and an integer perimeter budget `P`. Place one axis-aligned rectangle whose perimeter is at most `P` and report the largest number of the given points it can cover. Geometry rules: - The rectangle's sides are parallel to the coordinate axes. - Its width and height are nonnegative real numbers and must satisfy `2 * (width + height) <= P`. - Zero width or zero height is allowed, so collinear or coincident points can be covered by a degenerate rectangle. - Points lying exactly on the rectangle's boundary count as covered. - Repeated coordinates in the input count as separate points, so a rectangle covering that location covers every copy. - The rectangle's coordinates need not be integers. Implement `maximum_covered_points(points, P)`, which returns the maximum number of input points that a single such rectangle can cover. Return `0` when `points` is empty. The return value is a single integer count, so no ordering or tie-breaking rule is involved. Example 1: Input: points = [[0,0],[2,0],[0,1],[2,1],[10,10]], P = 6 Output: 4 Explanation: A rectangle of width 2 and height 1 has perimeter 2 * (2 + 1) = 6 <= 6 and covers the first four points. Reaching [10,10] as well would require width at least 8. Example 2: Input: points = [[1,1],[1,1],[2,1]], P = 0 Output: 2 Explanation: With P = 0 the rectangle collapses to a single location; the location (1, 1) holds two of the input points, and repeated points count separately. Every quantity in this problem fits in a 32-bit signed integer: coordinates stay within +/- 1000000, the largest possible perimeter value is 1000000000, and the answer never exceeds 200. Java may use `int` and C++ may use `int`; no value can exceed 2^31 - 1.

Constraints

  • 0 <= len(points) <= 200
  • Each point is [x, y] with integer coordinates in [-1000000, 1000000]
  • 0 <= P <= 1000000000
  • Repeated coordinates count as separate input points
  • The rectangle is axis-aligned; its width and height are nonnegative real numbers satisfying 2 * (width + height) <= P, and zero width or zero height is allowed
  • Rectangle coordinates need not be integers, and points on the boundary count as covered
  • Return 0 when there are no points

Examples

Input: ([], 0)

Expected Output: 0

Explanation: No points at all, so the answer is 0.

Input: ([[5, -3]], 0)

Expected Output: 1

Explanation: A single point is covered by a degenerate 0-by-0 rectangle of perimeter 0 <= 0.

Hints

  1. A rectangle that covers a set of points can be shrunk until each side touches one of those points, so only the spans between input coordinates ever matter.
  2. The perimeter budget ties width and height together: once you commit to a horizontal extent, the rest of the budget fixes the largest vertical extent you may still use.
  3. All coordinates are integers, so the entire feasibility test 2 * (width + height) <= P can be done in integer arithmetic; check the P = 0 case and repeated points before you are done.

Loading coding console...

Show the approach

Approach

Key reduction. A rectangle covers a subset S of points exactly when S fits inside it. Any rectangle that covers S can be shrunk to the bounding box of S without losing a point, and shrinking never increases the perimeter. So a subset S is achievable if and only if 2 * ((max x in S - min x in S) + (max y in S - min y in S)) <= P. Because all input coordinates are integers, the tight spans dx and dy are integers and the whole feasibility test is integer arithmetic; the real-valued, non-integer-cornered rectangles allowed by the statement never help.

Algorithm. Collect the distinct x-coordinates and sort them. For every pair xa <= xb of distinct x-coordinates, consider rectangles whose horizontal extent is exactly [xa, xb], so dx = xb - xa. Skip (and break out of the inner loop, since dx only grows) once 2 * dx > P. Otherwise the remaining budget allows a vertical span of at most dy_max = (P - 2 * dx) // 2; floor division is exact here because dy is an integer and 2 * dy <= P - 2 * dx is equivalent to dy <= floor((P - 2 * dx) / 2), which correctly handles odd P. Take the points whose x lies in [xa, xb], read their y values in globally sorted order, and slide a two-pointer window that maintains the invariant window[hi] - window[lo] <= dy_max; the largest window size over all pairs is the answer.

Correctness. Every count the scan reports is achievable: the rectangle [xa, xb] x [window[lo], window[hi]] has perimeter 2 * (dx + (window[hi] - window[lo])) <= 2 * (dx + dy_max) <= P and contains exactly those points. Conversely, an optimal subset has a tight bounding box whose left and right edges sit on input x-coordinates, so that pair (xa, xb) is enumerated; within that strip the optimum's y values are contiguous in the sorted y order, so the two-pointer window reaches at least that size. Hence the maximum over the scan equals the optimum.

Edge cases. An empty input returns 0 before any scanning. For a nonempty input P >= 0 always permits the degenerate 0-by-0 rectangle, so the answer is at least 1 (best starts at 1). P = 0 forces dx = dy = 0, which makes the answer the largest number of coincident points -- duplicates are never deduplicated, since the window is built from point records rather than distinct coordinates. Boundary inclusion is modeled by the non-strict comparisons xa <= x <= xb and span <= dy_max, matching the at-most perimeter rule; a set whose perimeter is exactly P is accepted.

Time complexity:
O(n^3)
Space complexity:
O(n)