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.

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.

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.

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.

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.

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)).

Hint 1:What if you run union find once at the start before insert value is called

… maybe don’t re-run union find on every insert?

Ya trying to figure out how to get around doing that.

Are you allowed to modify the graph? Seems like the question is similar to 827. Making A Large Island

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.

This was my thought to

Bruhhh let’s say I got one of these for a faang I bombed it tho.

Well yes but then why else would I be trying to get help :)

Which Leetcode number is this?

Wow you’re a genius

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.

Just use iterative bfs

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.

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.

whats this from? link?

I wrote a Java implementation here for the same problem:

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.

Solve Number of Islands everytime a new value is inserted.

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.

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)).