Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Most Stones Removed with Same Row or Column (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You have a 2D grid where you place n stones at specific integer coordinates, and each coordinate can have at most 1 stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Given an array stones of length n, where stones[i] = [x<sub>i</sub>, yi<sub>i</sub>] is the location of the i<sup>th</sup> stone, return the maximum number of stones that can be removed.

Examples

Example 1:

  • Input: stones = [[1, 1], [2, 2], [3, 1], [3, 2], [4, 4]]
  • Expected Output: 3
  • Justification: You can remove stones from [1, 1], [3, 1], and [3, 2] positions.

Example 2:

  • Input: stones = [[0, 0], [0, 1], [1, 0], [1, 1], [2, 2]]
  • Expected Output: 3
  • Justification: You can remove stones from [0, 0], [0, 1], and [1, 0] positions.

Example 3:

  • Input: stones = [[0, 1], [3, 4], [4, 3], [4, 4], [5, 5]]
  • Expected Output: 2
  • Justification: You can remove stones from [4, 4], and [3, 4] positions.

Constraints:

  • 1 <= stones.length <= 1000
  • 0 <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>4</sup>
  • No two stones are at the same coordinate point.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible