CareerCup

If for each cell we would know these information the problem would be solved:

Left(x,y)= maximum number of consecutive 1's in the left of cell(x,y) (including cell(x,y))
Right(x,y)= the same as above with right direction
Up(x,y) = same for up direction
Down(x,y)=same for down direction

And then the answer (largest +) for each cell would be the minimum of all of its directions ( min(Left(x,y),Right(x,y), ... )

And the final answer would be the cell with largest +.

Calculating mentioned arrays can be done with a simple dynamic programming.
For example:
Left(x,y) = if (cell(x,y)==0) 0 else Left(x,y-1)+1

So Total time complexity would be O(N*N).

arent yall assuming the thickness of the "+" is always 1 "1"? because how i see is that
0110
1111
1111
0110 should return 12 rather than 5

How about using DP to compute the total amount of consecutive 1s in every direction. And then using that information to compute the largest plus that could be created. It would take O(2n^2) which is O(n^2) time but it would be rather sucky regarding memory consumption at O(4n^2) ~ O(n^2):

public static int largestPlus(int[][] arr){
   if(arr == null){
        throw new NullPointerException();
   }

   int[][] lefts = new int[arr.length][arr[0].length];
   int[][] rights = new int[arr.length][arr[0].length];
   int[][] ups = new int[arr.length][arr[0].length];
   int[][] downs = new int[arr.length][arr[0].length];

   //compute DP cases
   for(int i = 0; i < arr.length; i++){
      ups[0][i] = arr[0][i];
      lefts[i][0] = arr[i][0];
      downs[arr.length-1][i] = arr[arr.length-1][i];
      rights[i][arr.length-1] = arr[i][arr.length-1];
   }
   for(int x = 0; x < arr.length; x++){
        for(int y = 1; y < arr.length; y++){
            if(arr[y][x] == 1){
                ups[y][x] = ups[y-1][x] + 1;
            }
            else{
                ups[y][x] = 0;
            }
            if(arr[x][y] == 1){
                lefts[x][y] = lefts[x][y-1] + 1;
            }
            else{
                lefts[x][y] = 0;
            }
            int invY = arr.length - y;
            if(arr[invY  - 1][x] == 1){
                downs[invY  - 1][x] = downs[invY ][x] + 1;
            }
            else{
                downs[invY  - 1][x] = 0;
            }
            if(arr[x][invY  - 1] == 1){
                rights[x][invY  - 1] = rights[x][invY ] + 1;
            }
            else{
                rights[x][invY  - 1] = 0;
            }
        }
    }

    //find best case
    int best = 0;
    for(int x = 0; x < arr.length; x++){
        for(int y = 0; y < arr.length; y++){
            int local = ups[x][y] < rights[x][y] ? ups[x][y] : rights[x][y];
            local = local < downs[x][y] ? local : downs[x][y];
            local = local < lefts[x][y] ? local : lefts[x][y];
            local = 4 * (local - 1) + 1;
            if(local > best){
                best = local;
            }
        }
    }
    return best;
}

can you please explain more

// Determine if coordinate is 1) valid, and 2) contains a 1
bool coordinatesAreValidOne(const vector<vector<int>>& matrix, int x, int y) {
    return  y >=0 && y < matrix.size() &&
            x >=0 && x < matrix.size() &&
            matrix[y][x] == 1;
}

// Find Large '1' Plus by iterating through the matrix, and for each 1, expanding outwards
// to find the min number of 1's shared by each direction 
int getLargestPlus(const vector<vector<int>>& matrix) {
    if(matrix.size() == 0) return 0;
    int largestPlus = 0;
    for(int i=0; i<matrix.size(); ++i) {
        for(int j=0; j<matrix.size(); ++j) {
            if(matrix[i][j] == 1) {
                int horz1 = 0, horz2 = 0, vert1 = 0, vert2 = 0;
                int y = i, x = j;
                while(coordinatesAreValidOne(matrix, x, --y)) { ++vert1; }
                y = i;
                while(coordinatesAreValidOne(matrix, x, ++y)) { ++vert2; }
                y = i;
                while(coordinatesAreValidOne(matrix, --x, y)) { ++horz1; }
                x = j;
                while(coordinatesAreValidOne(matrix, ++x, y)) { ++horz2; }
                int plusSize = 4 * min( min(horz1, horz2) , min(vert1, vert2) ) + 1;
                largestPlus = (plusSize > largestPlus) ? plusSize : largestPlus;
            }
        }
    }
    return largestPlus;
}

Ruby. DFS. Running time: O(|V|+|E|). Space: O(|V|)

matrix=[
  [0,0,0,0],
  [1,1,0,1],
  [1,1,1,1],
  [1,1,1,0]
]

@visited={}

def visited?(row,col)
  @visited.has_key?(row.to_s.to_sym) && @visited[row.to_s.to_sym].has_key?(col.to_s.to_sym) &&
  @visited[row.to_s.to_sym][col.to_s.to_sym]
end

def mark_visited(row,col)
  @visited[row.to_s.to_sym]={} if !@visited.has_key?(row.to_s.to_sym)
  @visited[row.to_s.to_sym][col.to_s.to_sym]=true
  #puts "[mark_visited] Visited: #{@visited}"
end

def left?(matrix,row,col)
  mark_visited(row,col) if block?(matrix,row,col+1)
  row>=0 && col>=0 && col+1<matrix.length && !visited?(row,col+1)
end

def right?(matrix,row,col)
  mark_visited(row,col) if block?(matrix,row,col-1)
  row>=0 && col>=0 && col-1<matrix.length && !visited?(row,col-1)
end

def up?(matrix,row,col)
  mark_visited(row,col) if block?(matrix,row-1,col)
  row>=0 && col>=0 && row-1<matrix.length && !visited?(row-1,col)
end

def down?(matrix,row,col)
  mark_visited(row,col) if block?(matrix,row+1,col)
  row>=0 && col>=0 && row+1<matrix.length && !visited?(row+1,col)
end

def block?(matrix,row,col)
  row>=0 && col>=0 && row<matrix.length && col<matrix.length && matrix[row][col]==0
end

def longest_path(matrix,row,col,path_length)  
  longest_paths_found=[]

  #puts "[longest_path] Visited: #{@visited}"
  #puts "[longest_path] curr pos: #{row},#{col}"
  mark_visited(row,col)
  
  # down?
  if down?(matrix,row,col)
    longest_paths_found << longest_path(matrix,row+1,col,path_length+1)
  end
  
  # up?
  if up?(matrix,row,col)
    longest_paths_found << longest_path(matrix,row-1,col,path_length+1)
  end
  
  # left?  
  if left?(matrix,row,col)
    longest_paths_found << longest_path(matrix,row,col-1,path_length+1)
  end
    
  # right?
  if right?(matrix,row,col) 
    longest_paths_found << longest_path(matrix,row,col+1,path_length+1)
  end
  
  
  return longest_paths_found.max if !longest_paths_found.empty?
  path_length+1
end

puts "longest_path: #{longest_path(matrix,1,0,1)}"

Output:
longest_path: 5

#include <iostream>
#include <stdio.h>

using namespace std;

int TestPlus(int** m, int x, int y, int span) {
    if(m[x][y] == 0) return 0;
    int count=0;
    for(int i=1; i<=span/2; i++) {
        if(m[x][y+i] == 1 && m[x][y-i] == 1 &&
           m[x+i][y] == 1 && m[x-i][y] == 1) {
               count++;
               continue;
           }
           break;
    }
    
    return (count == 0 ? count : 4*count+1);
}

int LargestPlus(int** m, int N) {
    int n = (N%2 == 0 ? N-1 : N);  
    int max = 0;
    for(int span = n; span >= 3; span -= 2) {
        if(max >= 2*span-1) return max;
        
        for(int x=span/2; x+span/2 < N; x++) {
            for(int y=span/2; y+span/2 < N; y++) {
                int val = TestPlus(m, x, y, span);
                if(max < val) max = val;
                if(max == 2*span-1) return max;
            }
        }
    }
    
    return max;
}

int main() {
    freopen("input.txt", "r", stdin);
    int N;
    scanf("%d", &N);
    int** m;
    m = new int*[N];
    for(int i=0; i<N; i++) m[i] = new int[N];
    
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++){
            scanf("%d", &m[i][j]); 
        }
    }
    cout << LargestPlus(m, N) << endl;
    
    for(int i=0; i<N; i++) delete [] m[i];
    delete [] m;
    return 0;
}

class DirectionInfo:
    def __init__(self):
        self.map = {}

class Solution:

    def __init__(self, matrix, n):
        self.memory = {}
        self.matrix = matrix
        self.N = n

    def LargestPlus(self):
        if not self.matrix:
            return -1
        largest = 0
        directions = [(-1, 0), (0, -1), (0, 1)]
        for i in range(0, self.N):
            for j in range(0, self.N):
                if self.matrix[i][j] == 1:
                    minDir = self.largestOnesSequence((i,j), (1,0), 0)
                    for d in directions:
                        res = self.largestOnesSequence((i,j), d, 0)
                        if res < minDir:
                            minDir = res
                    if 4* minDir + 1 > largest:
                        largest = 4* minDir + 1
        return largest

    def largestOnesSequence(self, start, direction, distance):
        if not self.legal(start):
            return 0
        if self.get_val(start) == 0:
            return 0
        if start not in self.memory:
            print('Creating direction Info for: ' + str(start))
            self.memory[start] = DirectionInfo()
        memo = self.memory[start]
        if direction not in memo.map:
            print('Entro con: '+ str(start) + 'en direccion' + str(direction))
            next_coord = Solution.apply_direction(start, direction)
            calc = self.largestOnesSequence(next_coord, direction, distance + 1)
            memo.map[direction] = calc + 1
        if distance > 0:
            odirection = Solution.get_opposite(direction)
            if odirection not in memo.map:
                memo.map[odirection] = distance
        return memo.map[direction]

    @staticmethod
    def get_opposite(direction):
        return -1 * direction[0], -1 * direction[1]

    @staticmethod
    def apply_direction(coord, direction):
        return coord[0] + direction[0], coord[1] + direction[1]

    def legal(self, coord):
        return 0 <= coord[0] < self.N and 0 <= coord[1] < self.N and self.get_val(coord) == 1

    def get_val(self, coord):
        return self.matrix[coord[0]][coord[1]]

public static int maxOfOne(int[][] arr, int con, int i, int j){
		if(i>=arr.length || j>=arr.length){
			return con;
		}else{
			con += arr[i][j];
			int x = maxOfOne(arr, con, i+1, j);
			int y = maxOfOne(arr, con, i, j+1) ;
			return x > y ? x : y ;
		}

public static int maxOfOne(int[][] arr, int con, int i, int j){
		if(i>=arr.length || j>=arr.length){
			return con;
		}else{
			con += arr[i][j];
			int x = maxOfOne(arr, con, i+1, j);
			int y = maxOfOne(arr, con, i, j+1) ;
			return x > y ? x : y ;
		}
	}

public static int maxOfOne(int[][] arr, int con, int i, int j){
		if(i>=arr.length || j>=arr.length){
			return con;
		}else{
			con += arr[i][j];
			int x = maxOfOne(arr, con, i+1, j);
			int y = maxOfOne(arr, con, i, j+1) ;
			return x > y ? x : y ;
		}

Use a helper class to keep track of the number of elements in the 4 posible directions: Top, Left, Right, Bottom and if the cell is valid, a call is valid if has values in all directions; Just need two scans to calculate the values (Top, Left) and (Bottom, Right) and a final pass to get the max cross

// Time 3*O(M) => O(M); Space O(M) where M = NxN

private class Helper
{
    public bool IsValid;
    public int Left;
    public int Right;
    public int Top;
    public int Bottom;
}

// Time 3*O(M) =>  O(M);  Space O(M) where M = NxN
public int GetMaxCross(int[,] matrix)
{
    var dp = new Helper[matrix.GetLength(0), matrix.GetLength(1)];

    // From (Top, Left) to (Bottom, Right) calculates Top, Right
    for (int i = 0; i < dp.GetLength(0); i++)
    {
        for (int j = 0; j < dp.GetLength(1); j++)
        {
            dp[i, j] = new Helper();
            if (matrix[i, j] == 0)
                continue;

            if (i - 1 >= 0 && matrix[i - 1, j] == 1)
                dp[i, j].Top = dp[i - 1, j].Top + 1;
            if (j - 1 >= 0 && matrix[i, j - 1] == 1)
                dp[i, j].Left = dp[i, j - 1].Left + 1;

            dp[i, j].IsValid = dp[i, j].Top != 0 && dp[i, j].Left != 0;
        }
    }

    // From (Bottom, Right) to (Top, Left) calculates Bottom, Right
    int lastRow = dp.GetLength(0) - 1;
    int lastCol = dp.GetLength(1) - 1;
    for (int i = lastRow; i >= 0; i--)
    {
        for (int j = lastCol; j >= 0; j--)
        {
            if (matrix[i, j] == 0)
                continue;

            if (i + 1 <= lastRow && matrix[i + 1, j] == 1)
                dp[i, j].Bottom = dp[i + 1, j].Bottom + 1;
            if (j + 1 <= lastCol && matrix[i, j + 1] == 1)
                dp[i, j].Right = dp[i, j + 1].Right + 1;

            dp[i, j].IsValid = dp[i, j].IsValid && dp[i, j].Bottom != 0 && dp[i, j].Right != 0;
        }
    }

    int max = 0;
    for (int i = 0; i < dp.GetLength(0); i++)
    {
        for (int j = 0; j < dp.GetLength(1); j++)
        {
            if (!dp[i, j].IsValid)
                continue;

            int n = Math.Min(Math.Min(dp[i, j].Top, dp[i, j].Bottom), Math.Min(dp[i, j].Right, dp[i, j].Left));
            max = Math.Max(max, n);
        }
    }

    return max * 4 + 1;
}