Design an algorithm that takes a 2d black and white grid and an index pair (i, j), and sets the value specified by (i, j) to black. It then returns the size of the largest black region after the pixel (i, j) has been changed to black (note: book is ambiguous on this). Optimize runtime for many repeated calls to this algorithm.

[Chinmay26]

Is the algorithm shared really O(m + n) time* where m - total number of calls n - total pixels

If we end up merging 2, 4, 8, 16, ... cells, I suspect it will be O(n * log n) ? This is since we have to update "region_id_matrix".

While the book does not cover it, I believe this is perfect use case for Union Find. The above use case can be achieved in O(m + n) in practice by using union by size and path compression with Union Find.

[Chinmay26]

Same for problem: Given a connected undirected graph, determine if the graph remains connected if any one edge is removed.

Precompute UF for each edge of the graph. O(V+E)

For any repeated calls to check if an edge is part of cycle can be done in constant time. For an edge u---v, if parent[u] == parent[v], then it is part of cycle and can be easily removed.

[Apollys]

If we end up merging 2, 4, 8, 16, ... cells, I suspect it will be O(n * log n) ? This is since we have to update "region_id_matrix".

In the last paragraph of my write-up I explained this case. The sum of 2 + 4 + 8 + 16 ~= 32, or 2 * 16. So after creating a region of size 16, the number of updates we had to do was bounded above by 2*16. Or in general, to create a region of size n from an exponential sequence of powers of 2, the number of updates is bounded by 2n.

[Apollys]

Remember what I wrote:

For a two-region merge, the time complexity is O(size of smaller region)

We don't rewrite the region id's of the largest region!