0% completed
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.
Solution
To solve this problem, we can use the Union-Find algorithm, also known as Disjoint Set Union (DSU). The Union-Find algorithm helps us manage and merge sets efficiently. We treat each row and column as nodes and use the stones to connect these nodes. By merging sets where stones share rows or columns, we can determine the number of connected components. The size of the largest connected component gives us the maximum number of stones that can be removed.
This approach works efficiently because it optimizes both the union and find operations, making it suitable for large inputs.
Step-by-Step Algorithm
-
Initialization:
- Define a constant
K = 10001
to differentiate between row and column nodes. - Initialize two arrays,
parent
andsize
, each with size2 * K + 1
. - Set
parent[i] = i
andsize[i] = 1
for alli
in the range2 * K + 1
.
- Define a constant
-
Union-Find Setup:
- Define a helper function
find(parent, x)
to find the root representative of nodex
:- If
x
is its own parent, returnx
. - Otherwise, recursively find the parent of
x
and perform path compression by settingparent[x]
to the root representative.
- If
- Define a helper function
union(parent, size, x, y)
to unite the sets containingx
andy
:- Find the root representatives of
x
andy
. - If they are already in the same set, return 0.
- Otherwise, unite the sets by size and update the
parent
andsize
arrays accordingly. Return 1 if a union operation was performed.
- Find the root representatives of
- Define a helper function
-
Component Counting:
- Initialize a variable
components = 0
. - Use a hashmap
seen
to keep track of unique rows and columns encountered:- For each stone
[xi, yi]
instones
:- If
xi
is not inseen
, incrementcomponents
and addxi
toseen
. - If
yi + K
is not inseen
, incrementcomponents
and addyi + K
toseen
.
- If
- For each stone
- Initialize a variable
-
Union Operations:
- For each stone
[xi, yi]
instones
:- Perform
union
operation betweenxi
andyi + K
. - If a union operation was successful, decrement
components
.
- Perform
- For each stone
-
Result Calculation:
- The maximum number of stones that can be removed is
len(stones) - components
.
- The maximum number of stones that can be removed is
Algorithm Walkthrough
Let's walk through the algorithm with the example stones = [[1, 1], [2, 2], [3, 1], [3, 2], [4, 4]]
.
-
Initialization:
- Define
K = 10001
. - Initialize
parent
andsize
arrays:parent = [0, 1, 2, ..., 20002]
size = [1, 1, 1, ..., 1]
- Define
-
Union-Find Setup:
- Define the
find
andunion
helper functions.
- Define the
-
Component Counting:
- Initialize
components = 0
. - Initialize an empty hashmap
seen
. - Process each stone:
- For stone
[1, 1]
:1
is not inseen
->components = 1
,seen[1] = 1
1 + K = 10002
is not inseen
->components = 2
,seen[10002] = 1
- For stone
[2, 2]
:2
is not inseen
->components = 3
,seen[2] = 1
2 + K = 10003
is not inseen
->components = 4
,seen[10003] = 1
- For stone
[3, 1]
:3
is not inseen
->components = 5
,seen[3] = 1
1 + K = 10002
is already inseen
- For stone
[3, 2]
:3
is already inseen
2 + K = 10003
is already inseen
- For stone
[4, 4]
:4
is not inseen
->components = 6
,seen[4] = 1
4 + K = 10005
is not inseen
->components = 7
,seen[10005] = 1
- For stone
- Initialize
-
Union Operations:
- For stone
[1, 1]
:- Perform
union(1, 10002)
->parent[1] = 1
,parent[10002] = 1
,size[1] = 2
- Union successful ->
components = 6
- Perform
- For stone
[2, 2]
:- Perform
union(2, 10003)
->parent[2] = 2
,parent[10003] = 2
,size[2] = 2
- Union successful ->
components = 5
- Perform
- For stone
[3, 1]
:- Perform
union(3, 10002)
->parent[3] = 3
,parent[1] = 3
,size[3] = 3
- Union successful ->
components = 4
- Perform
- For stone
[3, 2]
:- Perform
union(3, 10003)
->parent[3] = 3
,parent[2] = 3
,size[3] = 5
- Union successful ->
components = 3
- Perform
- For stone
[4, 4]
:- Perform
union(4, 10005)
->parent[4] = 4
,parent[10005] = 4
,size[4] = 2
- Union successful ->
components = 2
- Perform
- For stone
-
Result Calculation:
- The maximum number of stones that can be removed is
len(stones) - components = 5 - 2 = 3
.
- The maximum number of stones that can be removed is
Code
Complexity Analysis
Time Complexity
- Initialization: Initializing the
parent
andsize
arrays takes O(K) time, where (K) is the10001
constant value. - Union-Find Operations: The Union-Find operations (find and union) each have an amortized time complexity of O(\alpha(N)), where \alpha is the inverse Ackermann function. This function grows very slowly and can be considered almost constant for practical purposes.
- Union Operations: We perform union operations for each stone. Since each union operation is O(\alpha(N)), performing (N) union operations is O(N \alpha(N)).
Therefore, the overall time complexity is O(N \alpha(N) + K).
Space Complexity
The space complexity is O(N) due to the storage of the parent
and size
arrays and the seen
hashmap.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible