Show problems as
Classic problem #947MediumHash TableDepth-First SearchUnion-FindGraph TheoryBipartite Graph

Most Stones Removed with Same Row or Column

Real-world version: Pegboard Pin Removal
Tracked in this browser only
Read Most Stones Removed with Same Row or Column on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A large pegboard has pins pushed into some of its holes. pins[i] = [row_i, col_i] gives the hole holding pin i, and no two pins share a hole.

Pins come out one at a time. A pin may be pulled only if, at that moment, another pin still in the board sits in the same row or in the same column as it.

Return the largest number of pins that can be pulled out.

Examples

Example 1

Input
pins = [[0, 0], [0, 2], [2, 2], [2, 0], [1, 1]]
Output
3

Pull [0, 2] (its row mate [0, 0] is still in), then [2, 2] (its column mate [2, 0] is still in), then [2, 0] (its column mate [0, 0] is still in). That leaves [0, 0] and [1, 1], which share neither a row nor a column, so three pins come out.

Example 2

Input
pins = [[0, 1], [1, 0]]
Output
0

The two pins sit in different rows and different columns, so neither one is ever eligible to be pulled.

Example 3

Input
pins = [[0, 0], [0, 1], [1, 0], [1, 1]]
Output
3

Pull [1, 1], then [1, 0], then [0, 1]; each had a row or column mate on the board at the time, and [0, 0] stays behind.

Example 4

Input
pins = [[3, 3]]
Output
0

A lone pin has no row or column mate, so nothing can be pulled.

Constraints

  • 1 <= pins.length <= 1000
  • 0 <= row_i, col_i <= 10^4
  • No two pins occupy the same hole.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def remove_stones(pins: list[list[int]]) -> int:
Java
public int removeStones(int[][] pins)

More on the same topics