CODEWITHSUNDEEP
algorithmmemorygraphlanguage-agnosticmatrix
Michael
Michael

Reputation: 42050

How to find contiguous areas in matrix with less memory?

Suppose I have a matrix of 0 and 1. Now I would like to count all contiguous areas in the matrix that contain only 1.

allocate a new matrix "visited" to track visited elements
COUNT = 0
for each element E in the matrix
  if E == 1 and E is not visited
    COUNT = COUNT + 1
    run BFS/DFS to visit all not-visited matrix elements connected to E
return COUNT

If the matrix is N x N then we need additional N x N "visited" matrix and also a queue/stack for BFS/DFS. Now I wonder if there is an algorithm, which solves this problem and requires less memory.

Upvotes: 0

Views: 1084

Answers (1)

artahian
artahian

Reputation: 2093

If memory is so critical, then you can use the following approach:

Additionally keep only an array with the length of matrix's one row, then scan matrix rows from up to bottom, and each time when you process current row, there are intervals of continuous 1's in it, which can merge different pieces located above them, for example

1110001110011
1111001110011
0011111000011

if you consider only first 2 rows, there are three different pieces, but 3rd row merges first two of them. So you can use the additional array to keep what different pieces are there until last row, i.e. initially it will be filled with 0's, and when you are just starting scanning 3rd row of matrix, that array should look like 1111002220033, i.e. each number shows to which part that cell belongs. After processing 3rd row they will be merged and additional array will become 0011111000033. So after scanning each row some parts are merged, and some parts disappear. Each time a part disappears, you can increment the counter to have the answer in the end.

However, this is more tricky and complex approach than BFS/DFS, and I don't think that you will need to use this anyway in practice.

Upvotes: 1

Related Questions