947.Most-Stones-Removed-with-Same-Row-or-Column

947. Most Stones Removed with Same Row or Column

题目地址

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

题目描述

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3

Example 3:
Input: stones = [[0,0]]
Output: 0

Note:
1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

代码

Approach #2 Union-Find

Time O(N log N) Space O(N)

class Solution {
  public int removeStones(int[][] stones) {
    int N = stones.length;
    DSU dsu = new DSU(2000);

    for (int[] stone: stones) {
      dsu.union(stone[0], stone[1] + 10000);
    }

    Set<Integer> seen = new HashSet();
    for (int[] stone: stones) {
      seen.add(dsu.find(stone[0]));
    }

    return N - seen.size();
  }
}

class DSU {
  int[] parent;
  public DSU(int N) {
    parent = new int[N];
    for (int i = 0; i < N; i++) {
      parent[i] = i;
    }
  }

  public int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  public void union(int x, int y) {
    parent[find(x)] = find(y);
  }
}

Appraoch #3 DFS number of islands

class Solution {
  // Ans = # of stones - # of islands
  public int removeStones(int[][] stones) {
    Set<int[]> visited = new HashSet();
    int numOfIslands = 0;
    for (int[] s1: stones) {
      if (!visited.contains(s1)) {
        dfs(s1, visited, stones);
        numOfIslands++;
      }
    }
    return stones.length - numOfIslands;
  }

  private void dfs(int[] s1, Set<int[]> visited, int[][] stones) {
    visited.add(s1);
    for (int[] s2: stones) {
      if (!visited.contains(s2)) {
        // stone with same row or column. group them into island
        if (s1[0] == s2[0] || s1[1] == s2[1]) {
          dfs(s2, visited, stones);
        }
      }
    }
  }
}

Approach #4 BFS

Find connected components, with some specific connected component, the remove count is Num of elements - 1

class Solution {
  public int removeStones(int[][] stones) {
    int N = stones.length;
    int[] visited = new int[N];
    int ret = 0;
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < N; i++) {
      if (visited[i] == 0) {
        q.add(i);
      }
      int tmp = 0;
      while (!q.isEmpty()) {
        Integer pos = q.poll();
        if (visited[pos] == 1)    continue;
        int x = stones[pos][0];
        int y = stones[pos][1];
        tmp += 1;
        visited[pos] = 1;
        for (int j = 0; j < N; j++) {
          if (visited[j] == 0 && (stones[j][0] == x || stones[j][1] == y)) {
            q.add(j);
          }
        }
      }
      ret += (tmp != 0 ? (tmp - 1) : 0);
    }
    return ret;
  }
}

Approach #1 DFS

Time: O(N^2) && Space: O(N^2)

class Solution {
  public int removeStones(int[][] stones) {
        int N = stones.length;
    // graph[i][0] = the length of the 'list' graph[i][1:]
    int[][] graph = new int[N][N];
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
          graph[i][++graph[i][0]] = j; // ??
          graph[j][++graph[j][0]] = i; // ??
        }
      }
    }

    int ans = 0;
    boolean[] seen = new boolean[N];
    for (int i = 0; i < N; i++) {
      if (!seen[i]) {
        Stack<Integer> stack = new Stack();
        stack.push(i);
        seen[i] = true;
        ans--;
        while (!stack.isEmpty()) {
          int node = stack.pop();
          ans++;
          for (int k = 1; k <= graph[node][0]; k++) {
            int nei = graph[node][k];
            if (!seen[nei]) {
              stack.push(nei);
              seen[nei] = true;
            }
          }
        }
      }
    }

    return ans;
  }
}