mediumGraphsPure DSA~25 min
Maximum Markers Removable That Share a Row or Column
Markers sit on a grid. You may remove a marker if another marker shares its row or column. Remove as many as possible; report the maximum number of removals.
Problem
Given n markers as stones where stones[i] = [row, col], a marker can be removed if it shares a row or column with another not-yet-removed marker. Return the largest number of markers that can be removed.
Input
A list stones of [row, col] coordinates.
Output
An integer: the maximum number of removable markers.
Constraints
- 1 <= stones.length <= 1000
- 0 <= row, col <= 10^4
- No two markers share the same cell.
Examples
Example 1
Input
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output
5
All six markers are connected; you can remove all but one, leaving 5.
Example 2
Input
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output
3
Two connected components leave two markers behind, so 5 - 2 = 3 removals.