FastPrep
Problem · Graph

Most Stones Removed with Same Row or Column

Learn this problem
● MediumSnap Inc. logoSnap Inc.FULLTIMEPHONE SCREEN

Problem statement

There are stones at distinct integer coordinates on a two-dimensional plane. A stone may be removed if another remaining stone shares its row or its column.

Return the maximum number of stones that can be removed.

Function

removeStones(stones: int[][]) → int

Examples

Example 1

stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]return = 5

All six stones form one connected component, so one must remain.

Example 2

stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]return = 3

Four corner stones are connected and the center stone is isolated, so two stones remain.

Constraints

  • 1 <= stones.length <= 1000
  • 0 <= stones[i][0], stones[i][1] <= 10000
  • All coordinates are distinct.

More Snap Inc. problems

drafts saved locally
public int removeStones(int[][] stones) {
    // Write your code here
}
stones[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
expected5
checking account