CareerCup

Using the power and flexibility of C# ->Used recursion

internal int FindTheBiggestCross(int[,] matrix, int xLength, int yLength)
        {
            int total = 0;
            for (int i = 0; i < xLength; i++)
            {
                for (int j = 0; j < yLength; j++)
                {
                    if (matrix[i, j] == 1 && i - 1 >= 0 && j - 1 >= 0 && i + 1 < xLength && j + 1 < yLength
                        && matrix[i - 1, j] == 1
                        && matrix[i + 1, j] == 1
                        && matrix[i, j - 1] == 1
                        && matrix[i, j + 1] == 1
                        )
                    {
                        
                        var listofAnswer = new List<int>();

                        listofAnswer.Add(SizeOfCross1(matrix, i, j, xLength, yLength));
                        listofAnswer.Add(SizeOfCross2(matrix, i, j, xLength, yLength));
                        listofAnswer.Add(SizeOfCross3(matrix, i, j, xLength, yLength));
                        listofAnswer.Add(SizeOfCross4(matrix, i, j, xLength, yLength));

                        if(listofAnswer.Distinct().Count() == 1)
                        {
                            if(total < listofAnswer[0])
                            {
                                total = listofAnswer[0];
                            }
                        }

                    }
                }
            }
            return total;

        }

        private int SizeOfCross1(int[,] matrix, int xIndex, int yIndex, int xLength, int yLength)
        {
            if (xIndex >= 0 && xIndex < xLength && yIndex >= 0 && yIndex < yLength)
            {
                if (matrix[xIndex, yIndex] == 0) return 0;
                return 1+ SizeOfCross1(matrix, xIndex, --yIndex, xLength, yLength);
            }
            return 0;
        }

        private int SizeOfCross2(int[,] matrix, int xIndex, int yIndex, int xLength, int yLength)
        {
            if (xIndex >= 0 && xIndex < xLength && yIndex >= 0 && yIndex < yLength)
            {
                if (matrix[xIndex, yIndex] == 0) return 0;
                return 1 + SizeOfCross2(matrix, ++xIndex, yIndex, xLength, yLength);
            }
            return 0;
        }

        private int SizeOfCross3(int[,] matrix, int xIndex, int yIndex, int xLength, int yLength)
        {
            if (xIndex >= 0 && xIndex < xLength && yIndex >= 0 && yIndex < yLength)
            {
                if (matrix[xIndex, yIndex] == 0) return 0;
                return 1 + SizeOfCross3(matrix, xIndex, ++yIndex, xLength, yLength);
            }
            return 0;
        }

        private int SizeOfCross4(int[,] matrix, int xIndex, int yIndex, int xLength, int yLength)
        {
            if (xIndex >= 0 && xIndex < xLength && yIndex >= 0 && yIndex < yLength)
            {
                if (matrix[xIndex, yIndex] == 0) return 0;
                return 1 + SizeOfCross4(matrix, --xIndex, yIndex, xLength, yLength);
            }
            return 0;

}

Let the input matrix be called input[][].
Have another matrix of same size called num[][].
copy the first row and first column from input[][] to num[][].
Then update the num matrix such that num[i][j] should hold the number of continuous 1s in that column j if the input[i][j] == 1.
if input[i][j] == 0, then num[i][j] = 0.
Now look for odd numbers in num[][] greater than 1.
Lets say you find 3, then go up one step and check if the left and right are non zero.
If yes, then the size of plus is 1.
Now, keep looking for odd numbers greater than 3.
If you found 5, check again for left and right of two places up.
Then look for 7.. and so on.

complexity : O(n2)

Finds the size of largest ‘+’ formed by a particular element(here called 'symbol') in a 2D matrix of any size.

Highly optimized and generic version of plus(+) pattern search.

Complexity = O(m*n) for matrix of size {m x n}
Auxiliary space requirements = O(1).

public class PlusPattern {

    /**
     * Utility method to verify matrix dimensions
     *
     * @param a matrix to be verified
     * @return true if matrix size is greater than 0;
     */
    private static boolean isValid(int[][] a) {
        return a.length > 0 && a[0].length > 0;
    }

    /**
     * Finds the size of largest plus(+) pattern of given 'symbol' integer in an integer 2D matrix .
     *
     * The idea is to find for the biggest possible plus(+) pattern first around the central elements
     * of the matrix. If largest is found return the largest size. If largest possible + is not
     * found, store the size of whatever smaller than that was found and repeat search for 1 size
     * smaller + in the next outer window around the previous window.
     *
     * @param arr    matrix to be searched
     * @param symbol whose + patter is sought
     * @return the radius of largest + found in the matrix.
     */
    static int findLargestPlusPattern(int[][] arr, int symbol) {
        if (!isValid(arr)) {
            throw new IllegalArgumentException("Cannot perform search on empty array");
        }
        int maxPlusRadius = 0;

        int rows = arr.length;
        int cols = arr[0].length;
        int min = rows < cols ? rows : cols;
        int diff = rows > cols ? rows - cols : cols - rows;

        // Initializing initial window params. The center most smallest window possible
        // Example - For matrix of size {4x3}, smallest central window lies from [1][1] to [2][1]
        // Example - For matrix of size {3x9}, smallest central window lies from [1][1] to [1][7]
        int first_r, first_c, last_r, last_c;
        first_r = (min - 1) / 2;
        first_c = (min - 1) / 2;
        last_r = rows < cols ? (rows / 2) : (cols / 2) + diff;
        last_c = rows > cols ? (cols / 2) : (rows / 2) + diff;

        // Initializing with biggest possible search radius in the matrix
        int searchRadius = (min - 1) / 2;

        int r, c;
        int found;

        // Iteratively searching for + in an 'onion layer pattern' from inside to outside
        while (searchRadius > maxPlusRadius) {     // no need to find smaller + patterns than the one already found
            // initializing r and c cursor for this window iterations.
            r = first_r;
            c = first_c;

            // Search each of the 4 sides of the current window in a clockwise manner
            // 1# Scan the top line of window
            do { // do-while used to search inside initial window with width==1
                found = findLargestPlusAt(r, c, arr, symbol, searchRadius);
                if (found == searchRadius) {
                    return searchRadius;      // cannot find a bigger plus(+) than this in remaining matrix
                } else if (found > maxPlusRadius) {
                    maxPlusRadius = found;
                }
                c++;
            } while (c < last_c);
            if (c > last_c)
                c--; // for initial window with width==1. Otherwise #3 condition will be true for invalid c-index

            // 2# Scan the right line of window
            do {  // do-while used to search inside initial window with height==1
                found = findLargestPlusAt(r, c, arr, symbol, searchRadius);
                if (found == searchRadius) {
                    return searchRadius;
                } else if (found > maxPlusRadius) {
                    maxPlusRadius = found;
                }
                r++;
            } while (r < last_r);
            if (r > last_r)
                r--; // for initial window with height==1. Otherwise #4 condition will be true for invalid r-index

            // 3# Scan the bottom line of window
            while (c > first_c) {
                found = findLargestPlusAt(r, c, arr, symbol, searchRadius);
                if (found == searchRadius) {
                    return searchRadius;
                } else if (found > maxPlusRadius) {
                    maxPlusRadius = found;
                }
                c--;
            }

            // 4# Scan the left line of window
            while (r > first_r) {
                found = findLargestPlusAt(r, c, arr, symbol, searchRadius);
                if (found == searchRadius) {
                    return searchRadius;
                } else if (found > maxPlusRadius) {
                    maxPlusRadius = found;
                }
                r--;
            }
            // r and c comes back at first_r and first_c.

            // increasing window on all sides by 1.
            first_r--;
            first_c--;
            last_r++;
            last_c++;

            // reducing search radius to avoid out of bounds error on next window.
            searchRadius--;
        }
        return maxPlusRadius;
    }

    /**
     * Finds, if exist, the size of largest plus around a given point a[r][c]. It grows radius
     * greedily to maximise the search for + pattern returns 0 if is the point is the only symbol.
     *
     * @param r          row coordinate of search center
     * @param c          column coordinate of search center
     * @param a          matrix
     * @param symbol     search symbol
     * @param max_radius around the center to be searched for + pattern
     * @return returns -1 if the point itself is not the symbol.
     * returns n if all the next elements in E W N S directions within radius n are the symbol elements.
     */
    static int findLargestPlusAt(int r, int c, int[][] a, int symbol, int max_radius) {
        int largest = -1;

        if (a[r][c] != symbol) {   // If center coordinate itself is not the symbol
            return largest;
        } else {
            largest = 0;
        }
        for (int rad = 1; rad <= max_radius; rad++) {
            if (a[r + rad][c] == symbol && a[r][c + rad] == symbol && a[r - rad][c] == symbol && a[r][c - rad] == symbol) {
                largest = rad;   // At least a '+' of radius 'rad' is present.
            } else {
                break;
            }
        }
        return largest;
    }

    public static void main(String[] args) {
        int mat[][];
        mat = new int[][]{      // max + = 3
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 1, 1, 1, 1, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
                {1, 1, 0, 1, 1, 0, 1,},
        };
        int find = findLargestPlusPattern(mat, 1);
        System.out.println("# Max + size radius is : " + find);
        mat = new int[][]{  // max + = 2
                {1, 1, 9, 1, 1, 9, 1,},
                {1, 1, 9, 1, 1, 9, 1,},
                {7, 1, 1, 1, 1, 1, 1,},
                {1, 1, 9, 1, 1, 9, 1,},
                {1, 1, 9, 1, 1, 9, 1,},
        };
        find = findLargestPlusPattern(mat, 1);
        System.out.println("# Max + size radius is : " + find);

        mat = new int[][]{      // max + = 1
                {1, 1, 0, 1, 1},
                {1, 1, 0, 1, 1},
                {1, 1, 0, 1, 1},
                {1, 1, 1, 6, 1},
                {1, 1, 0, 1, 1},
                {1, 1, 0, 1, 1},
        };
        find = findLargestPlusPattern(mat, 1);
        System.out.println("# Max + size radius is : " + find);
    }
}