LeetCodeSolutions/Java/SpecialPositionsinaBinaryMatrix.java at master · Akshaya-Amar/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
/*

Source: https://leetcode.com/problems/special-positions-in-a-binary-matrix/

Time: O(m * n), where m and n are the lengths of the rows and columns respectively
Space: O(1), in-place

*/

class Solution {
  public int numSpecial(int[][] mat) {

    int m = mat.length;
    int n = mat[0].length;
    int count = 0;

    for(int i = 0; i < m; ++i) {

      for(int j = 0; j < n; ++j) {

        if(mat[i][j] == 1) {

          if(isSpecial(mat, i, j, m, n)) {
            ++count;
          }

          break;
        }
      }
    }

    return count;
  }

  private boolean isSpecial(int[][] mat, int i, int j, int m, int n) {


    for(int k = i - 1; k >= 0; --k) {

      if(mat[k][j] == 1) {
        return false;
      }
    }

    for(int k = i + 1; k < m; ++k) {

      if(mat[k][j] == 1) {
        return false;
      }
    }

    for(int k = j + 1; k < n; ++k) {

      if(mat[i][k] == 1) {
        return false;
      }
    }

    return true;
  }
}