Leetcode/src/main/java/com/fishercoder/solutions/_764.java at master · sksaini908/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
package com.fishercoder.solutions;

import java.util.HashSet;
import java.util.Set;

public class _764 {
    public static class Solution1 {
        /**
         * Brute force
         * <p>
         * Time: O(N^3)
         * Space: O(mines.length)
         */
        public int orderOfLargestPlusSign(int N, int[][] mines) {
            Set<Integer> banned = new HashSet<>();
            for (int[] mine : mines) {
                banned.add(mine[0] * N + mine[1]);
            }
            int result = 0;
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < N; col++) {
                    int k = 0;
                    while (k <= row && row < N - k && k <= col && col < N - k
                            && !banned.contains((row - k) * N + col)
                            && !banned.contains((row + k) * N + col)
                            && !banned.contains(row * N + col - k)
                            && !banned.contains(row * N + col + k)) {
                        k++;
                    }
                    result = Math.max(result, k);
                }
            }
            return result;
        }
    }

    public static class Solution2 {
        /**
         * Dp
         * <p>
         * Time: O(N^2)
         * Space: O(N^2)
         * Credit: https://leetcode.com/articles/largest-plus-sign/
         */
        public int orderOfLargestPlusSign(int N, int[][] mines) {
            Set<Integer> banned = new HashSet<>();
            for (int[] mine : mines) {
                banned.add(mine[0] * N + mine[1]);
            }

            int[][] dp = new int[N][N];

            for (int row = 0; row < N; row++) {
                int count = 0;
                for (int col = 0; col < N; col++) {
                    count = banned.contains(row * N + col) ? 0 : count + 1;
                    dp[row][col] = count;
                }

                count = 0;
                for (int col = N - 1; col >= 0; col--) {
                    count = banned.contains(row * N + col) ? 0 : count + 1;
                    dp[row][col] = Math.min(dp[row][col], count);
                }
            }

            int result = 0;
            for (int col = 0; col < N; col++) {
                int count = 0;
                for (int row = 0; row < N; row++) {
                    count = banned.contains(row * N + col) ? 0 : count + 1;
                    dp[row][col] = Math.min(dp[row][col], count);
                }

                count = 0;
                for (int row = N - 1; row >= 0; row--) {
                    count = banned.contains(row * N + col) ? 0 : count + 1;
                    dp[row][col] = Math.min(dp[row][col], count);
                    result = Math.max(result, dp[row][col]);
                }
            }
            return result;
        }
    }
}