Interview Question Categories

COUNT MAX NUMBER OF CONNECTED 1s IN A MATRIX

COUNT MAX NUMBER OF CONNECTED 1s IN A MATRIX


namespace CountMaxNoOfConnected1s
{
    //you have a matrix of N x N filled with 1 or 0. you can move 
    //only 1 step either right or 1 step down. you need to count 
    //maximum number of "connected 1" in given matrix. for example
    //0 0 1 1
    //1 1 1 0
    //1 0 1 0
    //0 1 0 1
    //[Start from top left] maximum no. of connected 1s is 4
    //[1,0][1,1][1,2][2,2]
    class Program
    {
        static int MaxNoOfConnected1s(int[,] Mat)
        {
            int[,] ComputeMat = new int[Mat.GetLength(0), Mat.GetLength(1)];
            int Max1s = 0;

            for (int i = 0; i < Mat.GetLength(0); i++)
            {
                for (int j = 0; j < Mat.GetLength(1); j++)
                {
                    if (i > 0 || j > 0)
                    {
                        if (i > 0 && j > 0)
                        {
                            if (Mat[i - 1, j] == 1 || Mat[i, j - 1] == 1)
                            {
                                ComputeMat[i, j] = Math.Max(ComputeMat[i - 1, j], ComputeMat[i, j - 1]) + Mat[i, j];
                            }
                            else ComputeMat[i, j] = Mat[i, j];
                        }
                        else if (i > 0)
                        {
                            if (Mat[i - 1, j] == 1)
                            {
                                ComputeMat[i, j] = ComputeMat[i - 1, j] + Mat[i, j];
                            }
                            else ComputeMat[i, j] = Mat[i, j];
                        }
                        else if (j > 0)
                        {
                            if (Mat[i, j-1] == 1)
                            {
                                ComputeMat[i, j] = ComputeMat[i, j-1] + Mat[i, j];
                            }
                            else ComputeMat[i, j] = Mat[i, j];
                        }

                        if (ComputeMat[i, j] > Max1s) Max1s = ComputeMat[i, j];
                    }
                }
            }
            return Max1s;
        }

        static void Main(string[] args)
        {
            int[,] Mat = {
                             {0,0,1,1},
                             {1,1,1,0},
                             {1,0,1,0},
                             {0,1,1,1}
                         };

            Console.WriteLine(MaxNoOfConnected1s(Mat));
        }
    }
}

No comments:

Post a Comment