Counting Max Consecutive elements in an array!!

Hello friends,

In this post, I would like to present a problem I encountered where we need to find consecutive occurrence of elements in a 2D matrix of N * N size. If  a cell has same element as contained by itself in the  top, bottom , right or left direct neighbor cell, then these two cells are said to have consecutive  occurrence of same element .
The consecutive same elements form a cluster  (sector).
The problem is to find the number of such clusters of same elements and to find the maximum size of the cluster.

For example
Input
N = 5;

Matrix :
{ 1, 1, 1, 0, 0 },
{ 1, 0, 1, 0, 0 },
{ 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 1 },
{ 0, 1, 0, 1, 1 }

Solution :

We can see we have three clusters with sizes as 8, 4 and 1.

So we need to output number of clusters followed by a space and then need to output the maximum size;

Output : 3 8



Lets see the code for this problem. I have used a stack for brack-tracing in this problem ( implemented the basic stack using array, although I could have used the java.util.Stack or simply ArrayList which would have reduced few lines of code, but anyways I choose to use basic array based Stack) In the program below I have used 'sector' instead of cluster.


There can be a approach using recursion, but I find understanding the code execution flow better in iterative manner.

public class LargestGridSector {
 /// input starts
 public static int data[][] = 

                                    { { 1, 1, 1, 0, 0 }, 

                                    { 1, 0, 1, 0, 0 }, 

                                    { 1, 0, 1, 0, 1 }, 

                                    { 1, 0, 0, 0, 1 }, 

                                    { 0, 1, 0, 1, 1 } };
 public static int N = 5;
 /// input ends

 public static void main(String[] args) {
  largedtGridSector();
  System.out.println(numOfSectors +" "+maxSectorSize);
 }

 public static class Point {
  int x;
  int y;

  public Point(int x, int y) {
   this.x = x;
   this.y = y;
  }
 }

 public static int largedtGridSector = 0;
 public static final int ONE = 1;
 public static final int ZERO = 0;
 public static final int VISITED = 3;
 public static final int INSTACK = 2;
 public static int numOfSectors = 0;
 public static int maxSectorSize = 0;
 public static int currentSectorSize = 0;
 public static Point[] stack = new Point[N * N];
 public static int stackIndex = -1;

 public static void largedtGridSector() {
  for (int i = 0; i < N; i++) {
   for (int j = 0; j < N; j++) {
    switch (data[i][j]) {
    case ONE:
     int x = i;
     int y = j;
     numOfSectors++;
     currentSectorSize = 0;
     boolean toBreakWhile = false;
     while (true) {
      switch (data[x][y]) {
      case ONE:
       Point p = new Point(x, y);
       push(p);
       data[p.x][p.y] = INSTACK;
       currentSectorSize++;
       if (y < N - 1 && data[x][y + 1] == ONE) {
        y++;
       } else if (y > 0 && data[x][y - 1] == ONE) {
        y--;
       } else if (x < N - 1 && data[x + 1][y] == ONE) {
        x++;
       } else if (x > 0 && data[x - 1][y] == ONE) {
        x--;
       } else if (stackIndex >= 0) {
        Point prePoint = pop();
        data[prePoint.x][prePoint.y] = VISITED;
        if (stackIndex >= 0) {
         x = stack[stackIndex].x;
         y = stack[stackIndex].y;
        }
       }
       break;
      case INSTACK:
       if (y < N - 1 && data[x][y + 1] == ONE) {
        y++;
       } else if (y > 0 && data[x][y - 1] == ONE) {
        y--;
       } else if (x < N - 1 && data[x + 1][y] == ONE) {
        x++;
       } else if (x > 0 && data[x - 1][y] == ONE) {
        x--;
       } else if (stackIndex >= 0) {
        Point prePoint = pop();
        data[prePoint.x][prePoint.y] = VISITED;
        if (stackIndex >= 0) {
         x = stack[stackIndex].x;
         y = stack[stackIndex].y;
        }
       }
       break;
      default:
       toBreakWhile = true;
       break;
      }
      if (stackIndex < 0 || toBreakWhile) {
       break;
      }
     }
     if (currentSectorSize > maxSectorSize) {
      maxSectorSize = currentSectorSize;
     }
     break;
    default:
     continue;
    }
   }
  }
 }

 public static void push(Point p) {
  stackIndex++;
  stack[stackIndex] = p;
 }

 public static Point pop() {
  Point p = stack[stackIndex];
  stack[stackIndex] = null;
  stackIndex--;
  return p;
 }

}