CODEWITHSUNDEEP
algorithmmatrixmultidimensional-array
Distraction
Distraction

Reputation: 460

2d array, all values are adjacent

I need a fast way to check if a 2d array is entirely adjacent, meaning all values are adjacent to other same values. Adjacent means the four cardinal directions.

This would be an adjacent array
[1 1 2]
[1 2 2]
[3 3 3]

This isn't
[1 2 1]
[1 2 2]
[3 3 3]

This is
[1 2 4]
[1 2 2]
[3 3 3]

So far, I've tried an O(M * N) method where I go through the whole array and check if at least one of the neighbors is the same value. I'm looking for a possibly faster way.

EDIT: just noticed my method doesn't even work correctly. eg:

This should fail (not all of the 1s are adjacent)
[1 2 1]
[1 2 1]
[3 3 3]

So now I need an actual algorithm for this.

Upvotes: 2

Views: 860

Answers (3)

Karthik
Karthik

Reputation: 5040

I just want to mention that you can't create an algorithm which is better than O(M*N)(of course this is worst case complexity), because in worst case you will have to visit all the elements.

As you said your O(M*N) algorithm does not work for all cases, you can solve this using BFS and Time complexity is O(M*N)

if(no.of connected components == no.of distinct elements) {
    return true;
}else{
    return false;
}

How do you find number of connected components? 

     yourFunction(int[][] matrix){
         boolean visited[][];
         for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
               if(!visited[i][j]){
                   BFS(matrix,i,j);
                   connectedComponents++;
               }
            }
         }
         int distinctNumbers = findDistinctNumbers(matrix); // you can write this function easily.
     }
    void BFS(int[][] martix, int i,int j){
         queue<Point> queue = new LinkedList<>();
         queue.add(new Point(i,j));
         while(queue.isEmpty()){
             Point point = queue.poll();
              for each neighbour of point
                  if neighbour is not visited && neighbour value =current point value
                      add neighbour to queue;
         }
    }

Upvotes: 0

Brent Washburne
Brent Washburne

Reputation: 13148

I'm reminded of the game Minesweeper.

  1. Outer loop: Scan the entire array (row by row, from left to right). This is to find the next position for the inner loop. If we have not visited this position from the inner loop, and the number at this position has not yet been seen, start the inner loop at this position. If we have already seen the number at this position, then the matrix is not "adjacent".

  2. Inner loop: Find all adjacent cells with the same number and mark them as visited (the Minesweeper part). Record this number as visited and return to the outer loop.

This requires a boolean matrix showing "visited" positions (the same size as the array being scanned) and a boolean list of numbers [1..n] that have been "visited".

Upvotes: 1

dpmcmlxxvi
dpmcmlxxvi

Reputation: 1302

Since, I assume, similar values can be arbitrarily far from each other, and can take any shape, in the matrix I don't see how you do it with out first computing the connected components of the values:

  1. Find the connected components labeling of your matrix
  2. For each matrix value keep a list of the component label it belongs to.
  3. If any value already has a label associated with it, stop, the matrix is not "adjacent". If none, then the matrix is "adjacent".

Upvotes: 1

Related Questions