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

0% completed

Vote For New Content
Solution: Most Stones Removed with Same Row or Column
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.

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

  1. Initialization:

    • Define a constant K = 10001 to differentiate between row and column nodes.
    • Initialize two arrays, parent and size, each with size 2 * K + 1.
    • Set parent[i] = i and size[i] = 1 for all i in the range 2 * K + 1.
  2. Union-Find Setup:

    • Define a helper function find(parent, x) to find the root representative of node x:
      • If x is its own parent, return x.
      • Otherwise, recursively find the parent of x and perform path compression by setting parent[x] to the root representative.
    • Define a helper function union(parent, size, x, y) to unite the sets containing x and y:
      • Find the root representatives of x and y.
      • If they are already in the same set, return 0.
      • Otherwise, unite the sets by size and update the parent and size arrays accordingly. Return 1 if a union operation was performed.
  3. 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] in stones:
        • If xi is not in seen, increment components and add xi to seen.
        • If yi + K is not in seen, increment components and add yi + K to seen.
  4. Union Operations:

    • For each stone [xi, yi] in stones:
      • Perform union operation between xi and yi + K.
      • If a union operation was successful, decrement components.
  5. Result Calculation:

    • The maximum number of stones that can be removed is len(stones) - components.

Algorithm Walkthrough

Let's walk through the algorithm with the example stones = [[1, 1], [2, 2], [3, 1], [3, 2], [4, 4]].

  1. Initialization:

    • Define K = 10001.
    • Initialize parent and size arrays:
      • parent = [0, 1, 2, ..., 20002]
      • size = [1, 1, 1, ..., 1]
  2. Union-Find Setup:

    • Define the find and union helper functions.
  3. Component Counting:

    • Initialize components = 0.
    • Initialize an empty hashmap seen.
    • Process each stone:
      • For stone [1, 1]:
        • 1 is not in seen -> components = 1, seen[1] = 1
        • 1 + K = 10002 is not in seen -> components = 2, seen[10002] = 1
      • For stone [2, 2]:
        • 2 is not in seen -> components = 3, seen[2] = 1
        • 2 + K = 10003 is not in seen -> components = 4, seen[10003] = 1
      • For stone [3, 1]:
        • 3 is not in seen -> components = 5, seen[3] = 1
        • 1 + K = 10002 is already in seen
      • For stone [3, 2]:
        • 3 is already in seen
        • 2 + K = 10003 is already in seen
      • For stone [4, 4]:
        • 4 is not in seen -> components = 6, seen[4] = 1
        • 4 + K = 10005 is not in seen -> components = 7, seen[10005] = 1
  4. Union Operations:

    • For stone [1, 1]:
      • Perform union(1, 10002) -> parent[1] = 1, parent[10002] = 1, size[1] = 2
      • Union successful -> components = 6
    • For stone [2, 2]:
      • Perform union(2, 10003) -> parent[2] = 2, parent[10003] = 2, size[2] = 2
      • Union successful -> components = 5
    • For stone [3, 1]:
      • Perform union(3, 10002) -> parent[3] = 3, parent[1] = 3, size[3] = 3
      • Union successful -> components = 4
    • For stone [3, 2]:
      • Perform union(3, 10003) -> parent[3] = 3, parent[2] = 3, size[3] = 5
      • Union successful -> components = 3
    • For stone [4, 4]:
      • Perform union(4, 10005) -> parent[4] = 4, parent[10005] = 4, size[4] = 2
      • Union successful -> components = 2
  5. Result Calculation:

    • The maximum number of stones that can be removed is len(stones) - components = 5 - 2 = 3.

Code

Python3
Python3

. . . .

Complexity Analysis

Time Complexity

  1. Initialization: Initializing the parent and size arrays takes O(K) time, where (K) is the 10001 constant value.
  2. 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.
  3. 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.

.....

.....

.....

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