How can I find, and store, the groups of values in a two-dimensional array?

Question

I'm working with a two dimensional array that contains values at each spot, and I need to find a way to calculate and return the number of groups made of values adjacent to the same value. For example:

+ - -
+ - -
+ + +

In this ASCII version of a 3x3 array, there would be groups of two values, '+', and '-'. I would define this array to have two distinct groups, based on adjacency. If two squares are not connected by path of adjacancy, they would not be in the same group.

3 groups:

+ - -
- - -
+ - -

5 groups :

+ - +
- - -
+ - +

How can I write an algorithm that could find the number of groups, their values and positions?

Thanks for the help!

Answer 1

The algorithm you are looking for is Flood Fill. To find the groups start from [0, 0] in your array and flood fill to find all the connected cells with the same value, marking them as "complete" as you go. Once the flood fill terminates the list of cells it visited is your first group. Then scan across your array until you find a cell not marked as complete and start another flood fill from there to find your next group. Repeat until all cells are marked as complete.

Answer 2

We can solve this problem by modeling it as a graph as follows:

• Create a vertex for each cell in the array
• Add an edge between two vertices if they are adjacent in the array and are of the same "type"

So, for example, for this array:

+ - -     
+ - -     
+ + +

the adjacency list representation of our graph will be (here, a vertex is labelled as a coordinate like 0,0 which corresponds to the cell at array[0][0]):

0,0 -> 1,0
0,1 -> 0,2  1,1
0,2 -> 0,1  1,2
1,0 -> 0,0  2,0
1,1 -> 0,1  1,2
1,2 -> 1,1  0,2
2,0 -> 1,0  2,1
2,1 -> 2,0  2,2
2,2 -> 2,1

which visually looks like this (horizontal edges are represented as ...):

+   -...-     
|   |   |
+   -...-     
|
+...+...+

Note that our graph construction is in line with what we want at a high level (i.e. connect similar "regions"). Now we need to count these regions. For this, we can use depth first search.

Our strategy will be to start DFS at any vertex and finish it. This will completely cover the region that the initial vertex belonged to. We will keep doing this for all vertices that have not been touched by any DFSs yet and count how many times we need to do these DFSs.

This is more generally know as the connect components problem. This algorithm to find the number of components for our specific case will take O(n^2) time for an n x n array, because we'll have n^2 vertices and less than n^2 edges (time complexity of DFS is O(V + E)).

Here's a working solution in javascript based on the above algorithm (tests for your examples are at the bottom):

function getGroups(array) {
  const graph = buildGraph(array);
  const components = getConnectedComponents(graph);
  return components;
}

function getConnectedComponents(graph) {
  let componentId = 0,
    vertexComponent = {},
    marked = new Set();

  let dfs = function(source) {
    marked.add(source);
    vertexComponent[source] = componentId;
    for (let u of graph[source]) {
      if (!marked.has(u)) dfs(u);
    }
  }

  for (let v in graph) {
    if (!marked.has(v)) {
      dfs(v); // start dfs from an unmarked vertex
      componentId++; // dfs must have "touched" every vertex in that component, so change componentId for the next dfs
    }
  }
  return vertexComponent;
}

function buildGraph(grid) {
  // builds an adjacency list (set) graph representation from a 2d grid
  let g = {};
  grid.forEach((row, i) => {
    row.forEach((cell, j) => {
      let v = i + ',' + j; // vertex label ( e.g 0,1 )
      if (!(v in g)) g[v] = new Set();
      getNeighbors(grid, i, j).forEach(n => {
        if (!(n in g)) g[n] = new Set();
        g[v].add(n);
        g[n].add(v);
      });
    });
  });
  return g;
}

function getNeighbors(grid, i, j) {
  // returns neighboring cells of the same type as grid[i][j]
  let n = [];
  let color = grid[i][j];
  if (i - 1 >= 0 && grid[i - 1][j] === color) n.push([i - 1, j].join());
  if (j - 1 >= 0 && grid[i][j - 1] === color) n.push([i, j - 1].join());
  if (i + 1 < grid.length && grid[i + 1][j] === color) n.push([i + 1, j].join());
  if (j + 1 < grid[0].length && grid[i][j + 1] === color) n.push([i, j + 1].join());
  return n;
}

// Let's do some testing

let array = [
  [0, 1, 1],
  [0, 1, 1],
  [0, 0, 0]
];
let arrayGroups = getGroups(array);
console.log(arrayGroups);
console.log('Total groups: ', new Set(Object.values(arrayGroups)).size);

array = [
  [0, 1, 1],
  [1, 1, 1],
  [0, 1, 1]
];
arrayGroups = getGroups(array);
console.log(arrayGroups);
console.log('Total groups: ', new Set(Object.values(arrayGroups)).size);

array = [
  [0, 1, 0],
  [1, 1, 1],
  [0, 1, 0]
];
arrayGroups = getGroups(array);
console.log(arrayGroups);
console.log('Total groups: ', new Set(Object.values(arrayGroups)).size);