the first one in Weekly Contest 206.
Difficulty : Easy
Related Topics : Array
Given a
rows x cols
matrixmat
, wheremat[i][j]
is either0
or1
, return the number of special positions inmat
.A position
(i,j)
is called special ifmat[i][j] == 1
and all other elements in rowi
and columnj
are0
(rows and columns are 0-indexed).Input: mat = [[1,0,0], [0,0,1], [1,0,0]] Output: 1 Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.
Input: mat = [[1,0,0], [0,1,0], [0,0,1]] Output: 3 Explanation: (0,0), (1,1) and (2,2) are special positions.
Input: mat = [[0,0,0,1], [1,0,0,0], [0,1,1,0], [0,0,0,0]] Output: 2
Input: mat = [[0,0,0,0,0], [1,0,0,0,0], [0,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1]] Output: 3
rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j]
is0
or1
.
- mine
- Java
Runtime: 3 ms, faster than 25.00%, Memory Usage: 49.7 MB, less than 25.00% of Java online submissions
//O(R(R + 2C))time //O(1)space public int numSpecial(int[][] mat) { int r = mat.length; int c = mat[0].length; int res = 0; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ if(mat[i][j] == 1){ if(check(mat, i, j)) res++; break; } } } return res; } boolean check(int[][] mat, int i, int j){ int count = 0; for(int a = 0; a < mat[i].length; a++){ if(mat[i][a] == 1) count++; } for(int a = 0; a < mat.length; a++){ if(mat[a][j] == 1) count++; } return count == 2; }
- Java
- the most votes
Runtime: 3 ms, faster than 25.00%, Memory Usage: 39.4 MB, less than 100.00% of Java online submissions
// O(R * C)time // O(R + C)space public int numSpecial(int[][] mat) { int r = mat.length, c = mat[0].length; int[] row = new int[r], col = new int[c]; for(int i = 0; i < r; i++) { for(int j = 0; j < c; j++) { if(mat[i][j] == 1) { row[i]++; col[j]++; } } } int count = 0; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(mat[i][j] == 1 && row[i] == 1 && col[j] == 1) count++; return count; }