Algorithms/LargestSquareOfOnes.java at main · byegates/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
//Determine the largest square of 1s in a binary matrix (a binary matrix only contains 0 and 1), return the length of the largest square.
//
//        Assumptions
//
//        The given matrix is not null and guaranteed to be of size N * N, N >= 0
//        Examples
//
//        { {0, 0, 0, 0},
//
//        {1, 1, 1, 1},
//
//        {0, 1, 1, 1},
//
//        {1, 0, 1, 1}}
//
//        the largest square of 1s has length of 2


public class LargestSquareOfOnes {

    public int largest(int[][] mx) { // TC: O(n^2), SC: O(n)
        int n = mx.length;
        if (n == 0) return 0;
        int m = mx[0].length;
        if (m == 0) return 0;


        int[] dp = new int[m];
        int res = 0;
        for (int j = 0; j < m; j++) {
            dp[j] = mx[0][j];
            if (dp[j] > res) res = dp[j];
        }

        for (int i = 1; i < n; i++) {
            int left = mx[i][0], corner = mx[i - 1][0];
            for (int j = 1; j < m; j++) {
                int nextCorner = dp[j];
                dp[j] =  mx[i][j] == 0 ? 0 : Math.min(Math.min(left, corner), dp[j]) + 1;
                if (dp[j] > res) res = dp[j];
                corner = nextCorner;
                left = dp[j];
            }
        }

        return res;
    }

    public int MByNSpace(int[][] mx) { // TC: O(m*n), SC: O(m*n)
        int n = mx.length;
        if (n == 0) return 0;
        int m = mx[0].length;
        if (m == 0) return 0;

        int[][] dp = new int[n][m];
        int res = 0;
        for (int j = 0; j < m; j++) res = largest(dp, 0, j, mx[0][j], res);
        for (int i = 0; i < n; i++) res = largest(dp, i, 0, mx[i][0], res);

        for (int j = 1; j < m; j++)
            for (int i = 1; i < n; i++)
                if (mx[i][j] == 0) dp[i][j] = 0;
                else
                    res = largest(dp, i, j, Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1, res);

        return res;
    }

    private int largest(int[][] dp, int i, int j, int val, int longest) {
        dp[i][j] = val;
        return Math.max(val, longest);
    }

    public static void main(String[] args) {
        LargestSquareOfOnes lso = new LargestSquareOfOnes();
        int[][] mx1 = new int[][]{
                {1, 1, 1, 1},
                {1, 1, 1, 1},
                {0, 1, 1, 1},
                {1, 1, 1, 1},
        };
        System.out.println(lso.MByNSpace(mx1)); // 3
        int[][] mx2 = new int[][]{
                {1, 0, 0},
                {0, 0, 0},
                {0, 0, 0},
        };
        System.out.println(lso.MByNSpace(mx2)); // 1
        int[][] mx3 = new int[][]{
                {0, 0, 1, 0, 0},
                {1, 1, 1, 1, 1},
                {0, 1, 1, 1, 1},
                {1, 0, 1, 1, 1},
        };
        System.out.println(lso.MByNSpace(mx3)); //3
        int[][] mx4 = new int[][]{
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
        };
        System.out.println(lso.largest(mx4)); // 5
    }
}