Sponsored
Sponsored
This approach involves iterating through each element of the matrix and checking if it is '1'. For each such element, all other elements in its row and column are checked to ensure they are '0'. This approach is straightforward but can be optimized.
Time Complexity: O(m * n * (m + n)), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), since we use a constant amount of space.
1class Solution {
2 public int numSpecial(int[][] mat) {
3 int m = mat.length;
4 int n = mat[0].length;
5 int specialCount = 0;
6 for (int i = 0; i < m; i++) {
7 for (int j = 0; j < n; j++) {
8 if (mat[i][j] == 1) {
9 boolean isSpecial = true;
10 for (int k = 0; k < m; k++) {
11 if (k != i && mat[k][j] == 1) {
12 isSpecial = false;
13 break;
14 }
15 }
16 for (int k = 0; k < n; k++) {
17 if (k != j && mat[i][k] == 1) {
18 isSpecial = false;
19 break;
20 }
21 }
22 if (isSpecial) specialCount++;
23 }
24 }
25 }
26 return specialCount;
27 }
28}The Java solution uses nested loops to check each matrix position, identical in logic to the C and C++ implementations. It counts a position as special if no other '1' is found along its row or column.
In this approach, two auxiliary arrays are used to track the number of '1's in each row and column. The matrix is then iterated to find the positions where both the row and column contain exactly one '1'. This approach reduces the need for repeatedly checking rows and columns.
Time Complexity: O(m * n), because we only iterate through the matrix twice.
Space Complexity: O(m + n), for storing row and column counts.
1using namespace std;
class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<int> rowOnes(m, 0), colOnes(n, 0);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 1) {
rowOnes[i]++;
colOnes[j]++;
}
}
}
int specialCount = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 1 && rowOnes[i] == 1 && colOnes[j] == 1) {
specialCount++;
}
}
}
return specialCount;
}
};The C++ version uses vectors to store the number of '1's in each row and column. Positions are then checked for the special condition where only one '1' exists in the respective row and column.