Example: Biggest square with sides with all Xs - rFronteddu/general_wiki GitHub Wiki

You are given a matrix of X and 0 and are tasked to find the biggest sub-square that has Xs on all sides.

---	0	1	2	3	4
0	0	0	0	0	X
1	X	0	X	X	X
2	X	0	X	0	X
3	X	X	X	X	X
4	0	0	X	X	X

The idea is to keep track in each cell the number of consecutive Xs top and left

---	0	1	2	3	4
0	0	0	0	0	1,1
1	1,1	0	1,1	1,2	2,3
2	2,1	0	2,1	0	3,1
3	3,1	1,2	3,3	1,4	4,5
4	0	0	4,1	2,2	5,3

From bottom left we examine cell to cell. For each cell (i,j)

• we pick the m = min(i,j)
• while m > maxA
  • we move left of m-1 cell,
  • if min ( $i_2$, $j_2$ ) >= m
    • we move up of m-1 cells
    • if min ( $i_3$, $j_3$ ) >= m
    • we store the current max area
    • maxA = max(maxA, currMaxA) m--
• we move to the next cell

largestXSquares(x)
    n = x.len
    if n == 0
        return
    m = x[0].len
    d = [0..n-1, 0..m-1]

    // fill d
    for i 0 to n-1
        for j = 0 to m-1
        if x[i,j] == 'X'
            d[i,j] = (i > 0 ? d[i-1,j][0] + 1 : 1, j > 0 ? d[i,j-1][1] + 1 : 1)

    maxSide = 0
    // from bottom-left to top-left, find largest sub-square

    for i = n-1 to 0
        for j = m-1 to 0
            if m[i,j] != 'X'
                continue
            minSide = min(d[i,j][0], d[i,j][1])
            while minSide > maxSide
                // check all possible subsquares > maxA found previously
                if d[i-minSide+1][j][1] >= minSide && d[i][j-minSide+1][0] >= minSide
                    maxSide = minSide
                minSide--

    return maxSide