How should I practice Maximum Points in a Perimeter-Bounded Rectangle?

Start by reading the full statement, solve the visible examples, then compare the pattern against related American Express online assessment problems in FastPrep.

Is Maximum Points in a Perimeter-Bounded Rectangle associated with American Express?

FastPrep tags this as a American Express online assessment coding practice problem when the problem catalog has that company and stage context.

Maximum Points in a Perimeter-Bounded Rectangle

American Express● HardINTERNOA

Learn

Problem statement

You are given distinct integer-coordinate points in the plane and a non-negative integer perimeter.

You may place one axis-aligned rectangle whose width and height are non-negative real values and whose perimeter is at most perimeter. A point is covered when it lies inside the rectangle or on its boundary.

Return the maximum number of points that one such rectangle can cover.

Function

maxPointsWithPerimeter(points: int[][], perimeter: int) → int

Examples

Example 1

points = [[0,0],[1,1],[2,2],[3,3]]perimeter = 8return = 3

A rectangle spanning from (0,0) through (2,2) has perimeter 8 and covers three points. Covering all four would require horizontal and vertical spans of 3, for perimeter 12.

Example 2

points = [[0,0],[0,2],[2,0],[2,2],[10,10]]perimeter = 8return = 4

The rectangle with corners (0,0) and (2,2) uses the full budget and covers the four nearby points.

Example 3

points = [[-3,1],[-1,1],[1,1],[3,1]]perimeter = 6return = 2

A zero-height rectangle may use width at most 3, so it can cover any adjacent pair but not three of the points.

Constraints

1 <= points.length <= 200.
points[i].length = 2.
-10^9 <= points[i][0], points[i][1] <= 10^9.
All points are distinct.
0 <= perimeter <= 2 * 10^9.
A rectangle may have zero width or zero height.