can counting contiguous regions in a bitmap be improved over O(r * c)?
algorithm, c, time-complexity
Solution
I think the confusion here is that your algorithm does actually run in linear time, not quadratic time.
When using big-O notation, `n` stands for the input size. Your input here is not just `r` or just `c`, but rather, `r` * `c`, as it is a grid of nodes. Your algorithm runs in `O(r * c)`, as you said in your question... thus your algorithm runs in `O(n)` which is linear time.
It seems to me that any algorithm that solves this problem will have to read each input cell once in the worst case. Thus the best running time you can hope for is `O(n)`. As your algorithm runs in `O(n)` you can't have any algorithm that runs of a faster order, in the worst case, than the algorithm you proposed.
I can think of some clever tricks. For example, if you have a block of `*`s, you could only check the diagonals, in certain cases. That is, if you have
......
.****.
.****.
.****.
.****.
......
it won't matter if you only read these cells:
......
.*.*..
..*.*.
.*.*..
..*.*.
......
unless for example you have something in the bottom-left-most corner, in which case you would need to read that bottom-left-most `*`. So maybe in certain cases your algorithm can run more quickly, but for the worst case (which is what `O` measures), it will have to be `O(n)`.
EDIT: Also even in that case where you only read half the nodes, the run-time would be `O(n/2)` which is still of the same order (`O(n)`).
Problem
You are given an image of a surface photographed by a satellite.The image is a bitmap where water is marked by '.' and land is marked by '`*`'. Adjacent group of '`*`'s form an island. (Two '`*`' are adjacent if they are horizontal, vertical or diagonal neighbours). Your task is to print the number of islands in the bitmap. Example Input:- ``` .........** **......*** ........... ...*....... *........*. *.........* ``` Output:- 5 Here, is my implementation which takes `O(r * c)` space and `O(r * c)` space where r is total no. of rows and c is total no of cols. ``` #include <stdio.h> #define COLS 12 void markVisted(char map[][COLS], int visited[][COLS], int row, int col, int rowCount) { if((row < 0) || (row >= rowCount) || (col < 0) || (col >= COLS) || (map[row][col] != '*') || (visited[row][col] == 1)) return; visited[row][col] = 1; //calling neighbours markVisted(map, visited, row+1, col, rowCount); markVisted(map, visited, row, col+1, rowCount); markVisted(map, visited, row-1, col, rowCount); markVisted(map, visited, row, col-1, rowCount); markVisted(map, visited, row+1, col+1, rowCount); markVisted(map, visited, row-1, col-1, rowCount); markVisted(map, visited, row-1, col+1, rowCount); markVisted(map, visited, row+1, col-1, rowCount); } int countIslands(char map[][COLS], int visited[][COLS], int rowCount) { int i, j, count = 0; for(i=0; i<rowCount; ++i){ for(j=0; j<COLS; ++j){ if((map[i][j] == '*') && (visited[i][j] == 0)){ ++count; markVisted(map, visited, i, j, rowCount); } } } return count; } int main() { char map[][COLS] = { "*..........", "**........*", "...........", "...*.......", "*........*.", "..........*" }; int rows = sizeof(map)/sizeof(map[0]); int visited[rows][COLS], i, j; for(i=0; i<rows; ++i){ for(j=0; j<COLS; ++j) visited[i][j] = 0; } printf("No. of islands = %d\n", countIslands(map, visited, rows)); return 0; } ``` please suggest some better logic for this problem also, suggestions to improve my solution is welcomed.