algorithms/leetcode/1292-MaximumSideLengthOfASquareWithSumLessThanOrEqualToThreshold.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package main

// 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
// Given a m x n matrix mat and an integer threshold,
// return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

// Example 1:
// <img src="https://assets.leetcode.com/uploads/2019/12/05/e1.png" />
// Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
// Output: 2
// Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

// Example 2:
// Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
// Output: 0

// Constraints:
//     m == mat.length
//     n == mat[i].length
//     1 <= m, n <= 300
//     0 <= mat[i][j] <= 10^4
//     0 <= threshold <= 10^5

import "fmt"

// prefixSum + binarySearch
func maxSideLength(mat [][]int, threshold int) int {
    m, n := len(mat), len(mat[0])
    sum := make([][]int, m + 1, m + 1)
    for i := range sum {
        sum[i] = make([]int, n + 1, n + 1)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + mat[i][j]
        }
    }
    min := func (x, y int) int { if x < y { return x; }; return y; }
    inThreshold := func(threshold int, length int) bool {
        for i := 1; i < len(sum); i++ {
            for j := 1; j < len(sum[0]); j++ {
                if i < length || j < length {
                    continue
                }
                if sum[i][j]+ sum[i-length][j-length]- sum[i-length][j]- sum[i][j-length] <= threshold {
                    return true
                }
            }
        }
        return false
    }
    l, r := 0, min(m, n)
    for l+1 < r {
        mid := (l + r) / 2
        if !inThreshold(threshold, mid) {
            r = mid
        } else {
            l = mid
        }
    }
    if inThreshold(threshold, r) {
        return r
    } else {
        return l
    }
}

func maxSideLength1(mat [][]int, threshold int) int {
    m, n := len(mat), len(mat[0])
    prefix := make([][]int, m+1)
    for i := range prefix {
        prefix[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + mat[i-1][j-1]
        }
    }
    min := func (x, y int) int { if x < y { return x; }; return y; }
    getRect := func(x1, y1, x2, y2 int) int {
        return prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
    }
    res, r := 0, min(m, n)
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            for c := res + 1; c <= r; c++ {
                if i+c-1 <= m && j+c-1 <= n && getRect(i, j, i+c-1, j+c-1) <= threshold {
                    res = c
                } else {
                    break
                }
            }
        }
    }
    return res
}

func main() {
    // Example 1:
    // <img src="https://assets.leetcode.com/uploads/2019/12/05/e1.png" />
    // Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
    // Output: 2
    // Explanation: The maximum side length of square with sum less than 4 is 2 as shown.
    mat1 := [][]int{
        {1,1,3,2,4,3,2},
        {1,1,3,2,4,3,2},
        {1,1,3,2,4,3,2},
    }
    fmt.Println(maxSideLength(mat1, 4)) // 2
    // Example 2:
    // Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
    // Output: 0
    mat2 := [][]int{
        {2,2,2,2,2},
        {2,2,2,2,2},
        {2,2,2,2,2},
        {2,2,2,2,2},
        {2,2,2,2,2},
    }
    fmt.Println(maxSideLength(mat2, 1)) // 0

    fmt.Println(maxSideLength1(mat1, 4)) // 2
    fmt.Println(maxSideLength1(mat2, 1)) // 0
}