leetcode/src/L764.java at master · prabhakar97/leetcode · 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
import java.util.Arrays;

class Solution764 {
    class Solution {
        /**
         * 764. Largest Plus Sign https://leetcode.com/problems/largest-plus-sign/description/
         *
         * @param N     int
         *              Size of the input grid
         * @param mines int[][]
         *              Location of mines in the input grid
         * @return Size of biggest +
         * @timeComplexity O(N ^ 2)
         * @spaceComplexity O(N ^ 2)
         */
        public int orderOfLargestPlusSign(int N, int[][] mines) {
            // Create the input grid and populate with 1s
            int[][] grid = new int[N][N];
            for (int i = 0; i < N; i++) {
                Arrays.fill(grid[i], 1);
            }

            // Place mines
            for (int i = 0; i < mines.length; i++) {
                grid[mines[i][0]][mines[i][1]] = 0;
            }

            // Aux array for caching best plus hand size seen at any cell
            int[][] aux = new int[N][N];
            int streak = 0;
            for (int i = 0; i < N; i++) {
                // Move left to right and update the aux with size of streak of 1s seen so far
                for (int j = 0; j < N; j++) {
                    if (grid[i][j] == 1) {
                        streak++;
                    } else {
                        streak = 0;
                    }
                    aux[i][j] = streak;
                }
                // Move right to left and update the aux with min of size of streak from left and size from right
                streak = 0;
                for (int j = N - 1; j >= 0; j--) {
                    if (grid[i][j] == 1) {
                        streak++;
                    } else {
                        streak = 0;
                    }
                    aux[i][j] = Math.min(aux[i][j], streak);
                }
                streak = 0;
            }
            for (int i = 0; i < N; i++) {
                // Move top to bottom and update the aux with min of size of streak in dp and current
                streak = 0;
                for (int j = 0; j < N; j++) {
                    if (grid[j][i] == 1) {
                        streak++;
                    } else {
                        streak = 0;
                    }
                    aux[j][i] = Math.min(aux[j][i], streak);
                }
                // Move from bottom to top and update the aux as earlier
                streak = 0;
                for (int j = N - 1; j >= 0; j--) {
                    if (grid[j][i] == 1) {
                        streak++;
                    } else {
                        streak = 0;
                    }
                    aux[j][i] = Math.min(aux[j][i], streak);
                }
            }
            // Return the longest streak
            int maxPlus = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    maxPlus = Math.max(maxPlus, aux[i][j]);
                }
            }
            return maxPlus;
        }
    }
}