leetcodesolutions/code/1895.largest-magic-square.java at main · Raghuram42/leetcodesolutions · 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
class Solution {
    public int largestMagicSquare(int[][] grid) {
        int res= 1;
        int min = Math.min(grid.length, grid[0].length);
        int i=0;
        for(i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                for(int k=1;k<min;k++){
                    if(i+k < grid.length && j+k< grid[0].length && magicSquare(grid, i,j, k))
                        res = Math.max(k+1, res);
                }
            }
        }

        return res;
    }


    public boolean magicSquare(int[][] grid, int st, int end, int dis){
        dis += 1;
        long prevsum = Long.MIN_VALUE;
        long rowsum = 0;
        long colsum = 0;
        for(int i=st;i<st+dis;i++){
            for(int j=end;j<end+dis;j++){
                rowsum += grid[i][j];
            }
            // System.out.println(rowsum+" "+st+" r "+end+" "+dis);
            if(prevsum != Long.MIN_VALUE && (prevsum != rowsum ))
                return false;

            prevsum = rowsum;
            rowsum=0;
        }


        for(int i=end;i<end+dis;i++){
            for(int j=st;j<st+dis;j++){
                colsum += grid[j][i];
            }
            // System.out.println(colsum+" "+st+" c "+end+" "+dis+" "+prevsum);
            if(prevsum != colsum)
                return false;

            prevsum = colsum;
            colsum =0;
        }

        long diagsum = 0;
        long revdiagsum = 0;

        int i=st;
        int j=end;
        while(i<st+dis && j<end+dis){
            diagsum += grid[i][j];
            i++;
            j++;
        }
        i= st;
        j=end+dis-1;
        // System.out.println(diagsum+" "+st+" d "+end+" "+dis+" "+prevsum);
        if(diagsum != prevsum)
            return false;

        while(i<st+dis && j>=0){
            revdiagsum += grid[i][j];
            i++;
            j--;
        }
        // System.out.println(revdiagsum+" "+st+" rd "+end+" "+dis+" "+prevsum);
        if(revdiagsum != diagsum)
            return false;
        return true;

    }
}