Struggling with this question. Can I get some help?

  1. Count the number of islands initially and mark the clusters, when a insert happens look around 4 directionally and connect to the clusters if present and decrease the count of total islands if you connect to more than one island. Increase by one if there are none. Doable using union find by adding nodes in a cluster under one parent. Best I can think of at the moment.

  2. I would start with a zero matrix let's call it N and set count =0. Iterate over indices of the given matrix so that on the i,j step, if the i,j entry of the given matrix is 1, insert a 1 into N at its i,j spot. If there is no nonzero entry neighboring i,j in N you increment the count by 1. Then return the count at the end of the iteration.

  3. for each x,y in col,rows, if components[x][y] == 1, run bfs on the original array and mark those coordinates in the component array with the id. increment the id. I would start id at 2 since 0 represents blocked and 1 represents unvisited.

  4. Union Find algorithm is actually "online" in Nature, so let's say you insert a new row to the bottom, then at the time of insertion, we'll perform a union operation with the elements in the row above and adjacent elements in the current row.

  5. First, you need to understand what a connected component really is. A connected component of an undirected graph is a subgraph in which every two vertices are connected to each other by a path (or multiple paths), and it isn't connected to no other vertices outside the subgraph.

  6. Start with i&j to the bounds of the matrix, sink (set 1s to 0 if they are connected to the initial 1(recursively)) return 1 once all 1 are 0.

  7. Every time there's an insertion, just check perform a dsu find set with its neighbours. And the number of unions required (i.e. find({i,j}) != find({i+x, j+y}) for (x,y) = [(-1,1),(1,1),(1,-1),(-1,-1)]) is how much you should subtract from previous answer. Note that when you find such pairs, you have to perform a union immediately after (before checking the next (x,y)).

Leave a Reply

Your email address will not be published. Required fields are marked *

Author: admin