Largest area of identical adjacent matrix elements

Question

Given a 2D matrix find the largest area of identical elements.

Here is my first implementation:

using System;
using System.Collections.Generic;
namespace ProgrammingBasics 
{
 class MaxArrayArea
 {
 static void Main()
 {
 // target matrix
 int[,] matrix = new int[,] { { 1, 3, 2, 2, 2, 4 },
 { 3, 3, 3, 2, 4, 4 },
 { 4, 3, 1, 2, 3, 3 },
 { 4, 3, 1, 3, 3, 1 },
 { 4, 3, 3, 3, 1, 1,}
 };
 PrintMatrix(matrix);
 MaxAreaOfIdenticalAdjacentElements(matrix);
 }
 //----------------------------------------------------------------------------
 /*
 Method: MaxAreaOfIdenticalAdjacentElements (arr2D);
 */
 static void MaxAreaOfIdenticalAdjacentElements(int[,] arr2D)
 {
 int value = 0;
 int largestArea = 0;
 HashSet<Tuple<int, int>> largestAreaElements = new HashSet<Tuple<int, int>>();
 for (int i = 0; i < arr2D.GetLength(0); i++)
 {
 for (int j = 0; j < arr2D.GetLength(1); j++)
 {
 // stores all unique matrix elements with the same values
 HashSet<Tuple<int, int>> visited = new HashSet<Tuple<int, int>>();
 // mark start element as visited
 Tuple<int, int> MatrixElement = new Tuple<int, int>(i, j);
 visited.Add(MatrixElement);
 CheckLeft(arr2D, i, j, visited);
 CheckRight(arr2D, i, j, visited);
 CheckUp(arr2D, i, j, visited);
 CheckDown(arr2D, i, j, visited);
 // check if area with current value is largest
 if (visited.Count > largestArea)
 {
 value = arr2D[i, j];
 largestArea = visited.Count;
 largestAreaElements = visited;
 }
 }
 }
 // mark the area
 char[,] area = new char[arr2D.GetLength(0), arr2D.GetLength(1)];
 foreach (var item in largestAreaElements)
 {
 area[item.Item1, item.Item2] = '*';
 }
 PrintMatrix(area);
 // print result
 Console.WriteLine("Value: {0} Area: {1}", value, largestArea);
 }
 //----------------------------------------------------------------------------
 /*
 Method: CheckLeft (arr2D, i, j, visited);
 arr2D - target 2D matrix storing seached elements
 i - row of current element
 j - column of current element
 visited - collection holding the unique adjacent elements with same value
 It recursively checks for elements with identical values to the left, up, and down.
 */
 static void CheckLeft(int[,] arr2D, int i, int j, HashSet<Tuple<int, int>> visited)
 {
 int currentValue = arr2D[i, j];
 int col = j - 1;
 if (col < 0)
 {
 return;
 }
 while (col >= 0)
 {
 Tuple<int, int> nextElement = new Tuple<int, int>(i, col);
 if (arr2D[i, col] == currentValue && !visited.Contains(nextElement))
 {
 visited.Add(nextElement);
 // check up
 CheckUp(arr2D, i, col, visited);
 // check down
 CheckDown(arr2D, i, col, visited);
 }
 else
 {
 break;
 }
 --col;
 }
 }
 //----------------------------------------------------------------------------
 /*
 Method: CheckUp (arr2D, i, j, visited);
 arr2D - target 2D matrix storing seached elements
 i - row of current element
 j - column of current element
 visited - collection holding the unique adjacent elements with same value
 It recursively checks for elements with identical values to the up, left, and right.
 */
 static void CheckUp(int[,] arr2D, int i, int j, HashSet<Tuple<int, int>> visited)
 {
 int currentValue = arr2D[i, j];
 int row = i - 1;
 if (row < 0)
 {
 return;
 }
 while (row >= 0)
 {
 Tuple<int, int> nextElement = new Tuple<int, int>(row, j);
 if (arr2D[row, j] == currentValue && !visited.Contains(nextElement))
 {
 visited.Add(nextElement);
 // check left 
 CheckLeft(arr2D, row, j, visited);
 // check right
 CheckRight(arr2D, row, j, visited);
 }
 else
 {
 break;
 }
 --row;
 }
 }
 //----------------------------------------------------------------------------
 /*
 Method: CheckRight (arr2D, i, j, visited);
 arr2D - target 2D matrix storing seached elements
 i - row of current element
 j - column of current element
 visited - collection holding the unique adjacent elements with same value
 It recursively checks for elements with identical values to the right, up, and down.
 */
 static void CheckRight(int[,] arr2D, int i, int j, HashSet<Tuple<int, int>> visited)
 {
 int currentValue = arr2D[i, j];
 int col = j + 1;
 if (col >= arr2D.GetLength(1))
 {
 return;
 }
 while (col < arr2D.GetLength(1))
 {
 Tuple<int, int> nextElement = new Tuple<int, int>(i, col);
 if (arr2D[i, col] == currentValue && !visited.Contains(nextElement))
 {
 visited.Add(nextElement);
 // check up
 CheckUp(arr2D, i, col, visited);
 // check down
 CheckDown(arr2D, i, col, visited);
 }
 else
 {
 break;
 }
 ++col;
 }
 }
 //----------------------------------------------------------------------------
 /*
 Method: CheckDown (arr2D, i, j, visited);
 arr2D - target 2D matrix storing seached elements
 i - row of current element
 j - column of current element
 visited - collection holding the unique adjacent elements with same value
 It recursively checks for elements with identical values to the down, left, and right.
 */
 static void CheckDown(int[,] arr2D, int i, int j, HashSet<Tuple<int, int>> visited)
 {
 int currentValue = arr2D[i, j];
 int row = i + 1;
 if (row >= arr2D.GetLength(0))
 {
 return;
 }
 while (row < arr2D.GetLength(0))
 {
 Tuple<int, int> nextElement = new Tuple<int, int>(row, j);
 if (arr2D[row, j] == currentValue && !visited.Contains(nextElement))
 {
 visited.Add(nextElement);
 // check left
 CheckLeft(arr2D, row, j, visited);
 // check right
 CheckRight(arr2D, row, j, visited);
 }
 else
 {
 break;
 }
 ++row;
 }
 }
 //-----------------------------------------------------------------------------
 /*
 Method: PrintMatrix(arr);
 It prints all the elements of the 2D integer array.
 */
 static void PrintMatrix(int[,] arr)
 {
 for (int row = 0; row < arr.GetLength(0); row++)
 {
 for (int column = 0; column < arr.GetLength(1); column++)
 {
 Console.Write("{0,3} ", arr[row, column]);
 }
 Console.WriteLine();
 }
 Console.WriteLine();
 }
 //-----------------------------------------------------------------------------
 /*
 Method: PrintMatrix(arr);
 It prints all the elements of the 2D char array.
 */
 static void PrintMatrix(char[,] arr)
 {
 for (int row = 0; row < arr.GetLength(0); row++)
 {
 for (int column = 0; column < arr.GetLength(1); column++)
 {
 Console.Write("{0,3} ", arr[row, column]);
 }
 Console.WriteLine();
 }
 Console.WriteLine();
 }
 }
}

Output:

enter image description here

Any constructive criticism will be greatly appreciated, especially regarding the reduction of the algorithm complexity.

Answer 1

Any constructive criticism will be greatly appreciated, especially regarding the reduction of the algorithm complexity.

Rather than doing a line-by-line review of your code, let me suggest a general problem-solving technique. Sometimes you get nicer code by solving the more general problem, and then applying your general solution to a specific problem.

Suppose we have an interface:

interface IGraph<T> where T : IEquatable<T> 
{
 IEnumerable<T> Nodes { get; }
 IEnumerable<T> Neighbors(T t);
}

That is, a graph is a thing that has a collection of nodes, and every node has a collection of nodes that it is "beside".

Can you write this method?

IEnumerable<T> Reachable(IGraph<T> graph, T start)

That is, given a graph and a node, return the set of nodes that is "reachable" starting at the start node.

Can you write this method?

IEnumerable<IEnumerable<T>> Partitions(IGraph<T> graph)

That is, given a graph, return a sequence where each element in the sequence is a collection of nodes that are all reachable from each other. That is, the transitive and reflexive closure of reachability.

And can you write this method?

IGraph<MyNode> ArrayToGraph(int[,] array)

That is, the method takes in an array and returns a graph of MyNode where two nodes are neighbours if they are neighbours in the array and have the same value.

If you can write those three methods then the solution to your problem is a one-liner:

int max = Partitions(ArrayToGraph(arr)).Select(p => p.Count()).Max();

When you solve the more general problem, the code to solve the more specific problem becomes very short and easy to understand.

• Ziezi: Thank you for the feedback. That is a great step-by-step explanation (of what I've understood) on how to build a graph out of the existing array and then to find the largest sequence (2D structure) of connected nodes with same value. That is actually beautiful and I will try to implement it.

Answer 2

First of all, I'd prefer to use this alias:

using Path = System.Collections.Generic.HashSet<System.Tuple<int, int>>;

Next, it makes sense to store a boolean flag for each matrix element indicating that this element has already been visited.

bool[,] visited = new bool[nx, ny];

And the last, I believe four methods CheckUp, CheckDown, CheckLeft and CheckRight could be combined into a single one.

private static void CheckAdjacent(int[,] arr2D, int i, int j, bool[,] visited,
 HashSet<Tuple<int, int>> path)

Here is the resulting code:

private static void MaxAreaOfIdenticalAdjacentElements(int[,] arr2D)
{
 int nx = arr2D.GetLength(0);
 int ny = arr2D.GetLength(1);
 int value = 0;
 int largestArea = 0;
 bool[,] visited = new bool[nx, ny];
 Path largestAreaElements = new Path();
 for (int j = 0; j < ny; j++)
 {
 for (int i = 0; i < nx; i++)
 {
 if (visited[i, j])
 continue;
 Path path = new Path();
 CheckAdjacent(arr2D, i, j, visited, path);
 // check if area with current value is largest
 if (path.Count > largestArea)
 {
 value = arr2D[i, j];
 largestArea = path.Count;
 largestAreaElements = path;
 }
 }
 }
 // mark the area
 char[,] area = new char[nx, ny];
 foreach (var item in largestAreaElements)
 {
 area[item.Item1, item.Item2] = '*';
 }
 PrintMatrix(area);
 // print result
 Console.WriteLine("Value: {0} Area: {1}", value, largestArea);
}
private static void CheckAdjacent(int[,] arr2D, int i, int j, bool[,] visited,
 HashSet<Tuple<int, int>> path)
{
 int currentValue = arr2D[i, j];
 path.Add(new Tuple<int, int>(i, j));
 visited[i, j] = true;
 // Check up
 if (i > 0 && !visited[i - 1, j] && arr2D[i - 1, j] == currentValue)
 CheckAdjacent(arr2D, i - 1, j, visited, path);
 // Check down
 if (i < arr2D.GetLength(0) - 1 && !visited[i + 1, j] && arr2D[i + 1, j] == currentValue)
 CheckAdjacent(arr2D, i + 1, j, visited, path);
 // Check left
 if (j > 0 && !visited[i, j - 1] && arr2D[i, j - 1] == currentValue)
 CheckAdjacent(arr2D, i, j - 1, visited, path);
 // Check right
 if (j < arr2D.GetLength(1) - 1 && !visited[i, j + 1] && arr2D[i, j + 1] == currentValue)
 CheckAdjacent(arr2D, i, j + 1, visited, path);
}