Find the Number of Groups of "1" in a Matrix

Problem: Given a matrix, each cell of the matrix is either "1" or "0". Consider that all the adjacent "1" form a group, find out how many such groups are in the matrix.  By"adjacent",  we mean a cell's left, right, up and down. The diagonal is not considered as "adjacent". For example, if we have a matrix as follow:

1 0 0 1

1 1 0 1

0 1 1 1

1 0 0 0

then the output will be 2. There are two groups of "1" here.

Solution: This is where disjoint-set can help. The algorithm is outlined as below:

• Basically, we scan the matrix row by row and from left to right. We need some auxiliary data structure stat[][] to keep some states. The states include the parent of a cell (it actually means which group a cell belongs to and each group has one unique parent) and the group id.
• Once we encounter a cell with value "1", if we find it is left and up neighbors are both "0", then we  can create a new group, and this cell also becomes the parent of the group.
• If we find its left neighbor is "1" and up neighbor is "0", then the current cell belongs to the same group where its left neighbor is. Similarly, if we find its left neighbor is "0" and up neighbor is "1", then the current cell belongs to the same group where its up neighbor is. 
• If we find both its left neighbor and up neighbor are "1", we need to do some Union() operation. First we need to find which group has a smaller group id between its left neighbor's group and up neighbor's group. Then we make the parent of the group that has a bigger id point to the parent of the group that has a smaller id. By doing this, we actually merge the two groups together and decrease the total number of groups by 1. If two groups have the same id, we don't need to do the Union().
• We can also do some optimization such as path compression. Here we actually use a simplified disjoint-set approach. The total time complexity is close to O(M*N) where M and N are the dimensions of the matrix.

The code is as below:

typedef struct cell
{
  int value;
  pair parent;
}cell;


pair<int, int> parent(int x, int y, cell stat[][M])
{
    //here we also implemented path compression
    if(stat[x][y].parent.first!=x || stat[x][y].parent.second!=y)
    {
        stat[x][y].parent =  parent(stat[x][y].parent.first, stat[x][y].parent.second, stat);
    }
    return stat[x][y].parent;

}


int group_of_1(int a[][M])
{
    cell stat[N][M];

    int group = 0;
    for(int i=0; ilt;N; i++)
    for(int j=0; jlt;M; j++)
    {
       if(a[i][j])
       {
         int g1,g2;
         g1 = g2 = -1;
         pair<int, int> p1, p2;

         if(i>0 && a[i-1][j])
         {
            p1 = parent(i-1, j, stat);
            g1 = stat[p1.first][p1.second].value;

         }
         if(j>0 && a[i][j-1])
         {
            p2 = parent(i, j-1, stat);
            g2 = stat[p2.first][p2.second].value;

         }

         if(g1<0 && g2<0)
         {
             group++;
             stat[i][j].value = group;
             stat[i][j].parent = pair<int, int>(i,j);
         }

         if(g1<0 && g2 > 0) stat[i][j].parent = p2;
         

        if(g1>0 && g2<0)   stat[i][j].parent = p1;
         

        if(g1>0 && g2 > 0)
         {
             stat[i][j].value = g1 < g2 ? g1:g2;

             if(g1<=g2)
                  stat[p2.first][p2.second].parent = stat[i][j].parent = p1;

             
             if(g1>g2)
                  stat[p1.first][p1.second].parent = stat[i][j].parent = p2;
               
             if(g1!=g2) group--;

         }

      }

    }

    return group;
}

Find the Sub-Matrix with the Largest Sum in a Matrix

Problem: Given a m*n matrix that is made up of integers (positive and negative), find the sub-matrix with the largest sum.

Solution: There is an O(n) algorithm to find the sub-array with the largest sum in a one-dimension array. So here, we will try to reduce our problem to the one-dimension array problem.

1. Assume the sub-matrix is between row a and b where 0<=a<=b<=m,  then we discard all the rows that are out of the range [a, b]. We then squeeze the sub-matrix into a one-dimension array. How to squeeze? Just use the sum of the elements remaining in each row to replace that row! Therefore we get a one dimensional array with n elements (each element is a sum). 
2. Then apply the O(n) algorithm we mentioned previously, we will get the sub-array with the largest sum in this one-dimension array, which is actually the sub-matrix between row a and b with the largest sum.
3. Until now, we have examined one pair a and b. If we try all the combination of a and b, we will be able to find the the sub-matrix in the with the largest sum in the m*n matrix. Assume n<m, we need repeat n^2 such operation. Then the overall time complexity is O(n^3). Naive way may take O(n^4). 
4. In order to make the "squeeze" operation (summing the column elements) with a constant time complexity, we need to do some pre-processing. We just need to calculate the prefix-sum. For example, c[i][j] = a[0][j] + a[1][j] +...+ a[i][j] . It is easy to calculate this for the whole matrix with time complexity O(n^2).

Search for an Element in a Matrix

Problem: A m*n matrix with its each row and each column sorted in ascending order. Given a target element, find that element in the matrix or return null if not found.

Solution: The following gives an O(m+n) algorithm.

1. Start from matrix[0][n-1], compare it with the target element. If equal, return; if matrix[0][n-1] is smaller than the target value, go vertically down to next row (examine matrix[1][n-1]); if matrix[0][n-1] is bigger than the target value, go horizontally left to the previous column (examine matrix[0][n-2]).
2. Compare the current cell in the matrix with the target element. If equal, return; if current cell is smaller than the target value, go vertically down to next row. if current cell is bigger than the target value, go horizontally left to the previous column.
3. Stop when it reaches the last row or first column or the target element is found. 
4. We actually can use binary search here.

Rotate an image 90 degree clockwise

Problem: an image stored as a M*N matrix (two dimensional array), give an in-place algorithm to rotate it 90 degree clockwise.

Solution: First assume a simpler case where M=N, we can only use O(1) memory. Basically, each iteration we change the location of four elements (sometime, these four elements may just points to the same one): a[x,y] -> a[y,N-1-x] -> a[N-1-x, N-1-y] -> a[N-1-y, x] -> a[x,y]. The algorithm is as follow:

for(int x =0; x<n; x++)
{
   y = x;
   if(y>=n-x-1) break;
   for(; y<n-x-1; y++)
   {
      temp = a[x,y];
      a[x,y] = a[y,n-1-x];
      a[y,n-1-x] = a[n-1-x,n-1-y];
      a[n-1-x,n-1-y] = a[n-1-y,x];
      a[n-1-y,x] = temp;
   }
}

If N!=M, things will be complex, we may need an auxiliary array to track if we had visited some elements or not, the algorithm (may not be optimal) is as follow:

int visited[N][M];
  int i,j;
  for(i=0; i<N; i++)
  for(j=0; j<M; j++)
        visited[i][j] = 0;

  for(i=0; i<N; i++)
  for(j=0; j<M; j++)
  {
        if(visited[i][j]==0)
        {
           int tmp = a[i][j];
           int c_i = i;
           int c_j = j;

           do
           {
             int ii = c_j;
             int jj = N - 1 - c_i;

             int to_i = (ii*N + jj + 1)/M;
             int to_j = (ii*N + jj + 1)%M;

             if(to_j==0)
             {
                to_i--;
                to_j = M - 1;
             }
             else to_j--;

             int tmp1 = a[to_i][to_j];
             a[to_i][to_j] = tmp;
             visited[to_i][to_j] = 1;
             c_i = to_i;
             c_j = to_j;
             tmp = tmp1;
           }
           while(!(c_i==i && c_j==j));
  }
}

Related:  In-place matrix transposition