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:

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.

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);
}