Challenge: Maximum Square

[tpphu]

Challenge

Have the function MaximalSquare(strArr) take the strArr parameter being passed which will be a 2D matrix of 0 and 1's, and determine the area of the largest square submatrix that contains all 1's. A square submatrix is one of equal width and height, and your program should return the area of the largest submatrix that contains only 1's. For example: if strArr is ["10100", "10111", "11111", "10010"] then this looks like the following matrix:

1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0

For the input above, you can see the bolded 1's create the largest square submatrix of size 2x2, so your program should return the area which is 4. You can assume the input will not be empty.

Sample Test Cases

Case 1

Input:["0111", "1111", "1111", "1111"] Output:9

Case 2

Input:["0111", "1101", "0111"] Output:1

[hiepndd]

Hi anh @tpphu , day la solution cua em, big-o khoang O(m*n)^2 , voi m la row va n va col, em nghi em co the optimize big-o tu O(m*n)^2 xuong O(m*n), tam thoi em chua nghi ra 🤣 , em se suy nghi them

func maximalSquare(matrix [][]byte) int {
    rows := len(matrix)
    if rows == 0 {
        return 0
    }
    cols := len(matrix[0])
    max := 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if matrix[i][j] == 1 {
                current := 1
                check := true
                for current+i < rows && current+j < cols && check {
                    for k := j; k <= current+j; k++ {
                        if matrix[i+current][k] == 0 {
                            check = false
                            break
                        }
                    }

                    for k := i; k <= current+i; k++ {
                        if matrix[k][i+current] == 0 {
                            check = false
                            break
                        }
                    }
                    if check {
                        current++
                    }
                }
                if max < current {
                    max = current
                }
            }

        }
    }
    return max * max
}

func TestMaximalSquare(t *testing.T) {
    testcases := []struct {
        name   string
        input  [][]byte
        expect int
    }{
        {"Test Case 1", [][]byte{{0, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}}, 9},
        {"Test Case 2", [][]byte{{0, 1, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 1}}, 1},
        {"Test Case 3", [][]byte{{1, 0, 1, 0, 0}, {1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 1, 0}}, 4},
    }

    for _, testcase := range testcases {
        t.Run(testcase.name, func(t *testing.T) {
            got := maximalSquare(testcase.input)
            if !reflect.DeepEqual(got, testcase.expect) {
                t.Fatalf("expected: %v, but got: %v, with inputs: %v",
                    testcase.expect, got, testcase.input)
            }
        })
    }
}

[tpphu]

Vào cái này để test bài nha

https://www.coderbyte.com/challenges

[tpphu]

Solution của anh, mất cả ngày mới viết được :dancer:

package main

import "fmt"

func SquareArea(strArr []string, x0, y0 int) (area int) {
    rows := len(strArr)
    cols := len(strArr[0])
    if strArr[x0][y0] != '1' {
        return 0
    }
    vertex := 0
    isStop := false
    for ; ; vertex++ {
        if vertex >= (cols-y0) || vertex >= (rows-x0) {
            break
        }
        vRows := x0 + vertex
        vCols := y0 + vertex
        // Theo dong
        for i := y0; i <= vCols; i++ {          
            if strArr[vRows][i] != '1' {
                isStop = true
                break
            }
        }
        // Theo cot
        for i := x0; i <= vRows; i++ {
            if strArr[i][vCols] != '1' {
                isStop = true
                break
            }
        }

        if isStop {
            break
        }
    }
    return vertex  * vertex
}

/**
 * Muc tieu cua func nay la de:
 * 1. Tim cac squre di tu vi tri [x, y]
 * 2. So sanh voi square truoc do de cap nhat square lon hon
 */
func MaximalSquare(strArr []string) (maxArea int) {
    rows := len(strArr)
    cols := len(strArr[0])
    for x := 0; x < rows; x++ {
        for y := 0; y < cols; y++ {
            area := SquareArea(strArr, x, y)
            // fmt.Printf("square at [%d, %d] is %d\n", x, y, area)
            if area > maxArea {
                maxArea = area
            }
        }
    }
    return maxArea
}

func main() {

    // do not modify below here, readline is our function
    // that properly reads in the input for you
    fmt.Println(MaximalSquare(readline()))
}

[tpphu]

Test case

package main

import (
    "testing"
)

func Test_MaximalSquare_1(t *testing.T) {
    in := []string{"0111", "1111", "1111", "1111"}
    expected := 9
    actual := MaximalSquare(in)
    if actual != expected {
        t.Errorf("Actual %d should be expected %d", actual, expected)
    }
}

func Test_MaximalSquare_2(t *testing.T) {
    in := []string{"10100", "10111", "11111", "10010"}
    expected := 4
    actual := MaximalSquare(in)
    if actual != expected {
        t.Errorf("Actual %d should be expected %d", actual, expected)
    }
}

func Test_MaximalSquare_3(t *testing.T) {
    in := []string{"0111", "1101", "0111"}
    expected := 1
    actual := MaximalSquare(in)
    if actual != expected {
        t.Errorf("Actual %d should be expected %d", actual, expected)
    }
}

func Test_MaximalSquare_4(t *testing.T) {
    in := []string{"1111", "1101", "1111", "0111"}
    expected := 4
    actual := MaximalSquare(in)
    if actual != expected {
        t.Errorf("Actual %d should be expected %d", actual, expected)
    }
}