Swift solution with full comments, but broken in interpreter


  • 0
    S

    I'm pretty convinced this is a valid solution since it only breaks on submission, never in the test with the same values that throw an index out of bounds condition.

    class Solution {
        func maximalSquare(_ matrix: [[Character]]) -> Int {
            if matrix.count == 0 {
                return 0
            }
            
            var maxrun = 0
            
            // tracking matrix with length and width one larger
            // we sum runs at matrix[x][y] in runs[x+1][y+1]
            var runs = [[Int]](repeating:([Int](repeating: 0, count: matrix[0].count + 1)), count: matrix.count + 1)
            
            // walk the matrix incrementing ahead as we walk
            for x in 0..<matrix.count {
                for y in 0..<matrix[0].count {
                    // zero value runs reset the base to zero
                    if matrix[x][y] == "1" {
                        // ensure a zero resets the run, looking back to capture the prior run info
                        // we look back 1 row and column to ensure we are still building a square
                        let run = min(runs[x][y], runs[x+1][y], runs[x][y+1])
                        // save the current run + 1 for the current '1' value
                        runs[x+1][y+1] = run + 1
                        // do we have a new max run
                        maxrun = max(runs[x+1][y+1], maxrun)
                    }
                }
            }
            
            // area is square of max run
            return maxrun * maxrun
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.