How should I practice Minimum Coordinate-Conflict Deletions?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Minimum Coordinate-Conflict Deletions associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Minimum Coordinate-Conflict Deletions

Google● HardNEW GRADONSITE INTERVIEW

Learn

Problem statement

You are given integer coordinate pairs in points. Delete as few input points as possible so that no two retained points share an x coordinate or share a y coordinate.

Return the minimum number of deletions. Each input occurrence is a separate point, including repeated coordinate pairs. An empty collection requires 0 deletions.

Function

minimumCoordinateConflictDeletions(points: int[][]) → int

Examples

Example 1

points = [[0,1],[0,2],[1,0],[2,0]]return = 2

At most one of the first two points and at most one of the last two points can remain. Keeping (0,1) and (1,0) achieves two deletions.

Example 2

points = [[0,0],[0,1],[1,0]]return = 1

Keep (0,1) and (1,0), deleting only (0,0). A greedy first choice of (0,0) would keep too few points.

Example 3

points = [[1,2],[3,4],[5,6]]return = 0

Every point already has a unique x and a unique y.

Constraints

0 <= points.length <= 500.
Every point is a pair [x, y].
-10^9 <= x, y <= 10^9.