1582. Special Positions in a Binary Matrix


Problem Description

In this LeetCode problem, we're given a binary matrix mat, which is made up of only 0s and 1s. Our task is to count how many 'special positions' are in the matrix. A special position is defined as one where the value at that position is 1 and all other values in the same row and column are 0. Here, the matrix is indexed starting at (0,0) for the top-left element.

Intuition

The intuition behind the solution is to first count the number of 1s in each row and each column. If a position (i, j) has a 1, and the corresponding counts for row i and column j are both exactly 1, then the position (i, j) is a special position. Here's the breakdown:

  1. We initialize two lists, r and c, to keep track of the count of 1s in each row and each column, respectively.
  2. By double looping through the matrix, we update these counts.
  3. After populating r and c, we go through the matrix again, checking if a 1 is in a position (i, j) such that r[i] and c[j] are both exactly 1.
  4. If the condition from step 3 is met, we increment our ans variable, which holds the count of special positions.
  5. We return the value of ans as the final result.

This approach works because for a position with a 1 to be special, it must be the only 1 in its row and column. By counting the 1s in each row and column first, we have all the information we need to efficiently determine if a position is special during our second pass through the matrix.

Solution Approach

The solution approach follows a straightforward algorithmic pattern that is quite common in matrix-related problems, which includes the following steps:

  1. Initialize Count Arrays: The code initializes two arrays r and c with lengths equal to the number of rows m and columns n of the input matrix, respectively. These arrays are used to keep track of the sum of 1s in each row and column, hence initialized to all 0s.

  2. Populate Count Arrays: The solution uses a nested loop where i iterates over the rows and j iterates over the columns. For each cell in the matrix, if the value mat[i][j] is 1, the sum in the corresponding count arrays r[i] and c[j] are incremented by 1. This allows us to accumulate the number of 1s for each row and each column in their respective counters.

  3. Identify Special Positions: With the populated count arrays, we loop through the matrix for the second time. During this iteration, we check if the value at mat[i][j] is 1 and if r[i] and c[j] are both equal to 1. This condition verifies that the current position (i, j) is special as it is the only 1 in its row and column.

  4. Count Special Positions: If the condition in the previous step is satisfied, we increment the variable ans which is used to count the number of special positions.

  5. Return the Result: Once the entire matrix has been scanned during the second iteration, the ans variable contains the total count of special positions. This value is returned as the output.

The data structures used are quite simple and effective; we are using two one-dimensional arrays (r for rows and c for columns) to keep the sums. The algorithmic pattern employed is also straightforward, involving iterations and condition checking. This approach is efficient since each element in the matrix is processed a constant number of times, resulting in a time complexity of O(m*n), where m and n are the number of rows and columns in the matrix, respectively. The space complexity is O(m+n), which is required for the row and column sum arrays.

Example Walkthrough

Let's consider a 3x4 binary matrix mat for our example:

1mat = [
2  [1, 0, 0, 0],
3  [0, 0, 1, 0],
4  [0, 1, 0, 0]
5]

Following our algorithmic steps:

  1. Initialize Count Arrays: We initialize two arrays r with length 3 (number of rows) and c with length 4 (number of columns), to all 0s. So, r = [0, 0, 0] and c = [0, 0, 0, 0].

  2. Populate Count Arrays: We iterate through the matrix mat:

    • For i=0 (first row), we find mat[0][0] is 1, so we increment r[0] and c[0] by 1. Now, r = [1, 0, 0] and c = [1, 0, 0, 0].
    • For i=1 (second row), we find mat[1][2] is 1, so we increment r[1] and c[2] by 1. Now, r = [1, 1, 0] and c = [1, 0, 1, 0].
    • For i=2 (third row), we find mat[2][1] is 1, so we increment r[2] and c[1] by 1. Now, r = [1, 1, 1] and c = [1, 1, 1, 0].

    After populating the counts arrays, r and c now accurately reflect the number of 1s in each row and column.

  3. Identify Special Positions: With the count arrays set up, we go through the matrix once more:

    • Check position (0,0). Since mat[0][0] is 1 and both r[0] and c[0] are exactly 1, this is a special position.
    • Check position (1,2). Since mat[1][2] is 1 and both r[1] and c[2] are exactly 1, this is also a special position.
    • Check position (2,1). Since mat[2][1] is 1 and both r[2] and c[1] are exactly 1, this is a special position as well.

    Every 1 we encountered is indeed in a special position.

  4. Count Special Positions: We increment our variable ans for each special position identified. As we found 3 special positions, ans would be 3.

  5. Return the Result: Our function would return ans, the total count of special positions, which in this case is 3.

In this straightforward example, our methodical walk-through demonstrates that the provided binary matrix mat contains three special positions, as identified using the solution approach. The row and column counts help efficiently pinpoint the special positions in just two scans of the matrix.

Python Solution

1class Solution:
2    def numSpecial(self, mat: List[List[int]]) -> int:
3        # Get the number of rows 'm' and columns 'n' of the matrix
4        num_rows, num_cols = len(mat), len(mat[0])
5      
6        # Initialize row_sum and col_sum to keep track of the sum of each row and column
7        row_sum = [0] * num_rows
8        col_sum = [0] * num_cols
9      
10        # Calculate the sum of elements for each row and column
11        for i, row in enumerate(mat):
12            for j, value in enumerate(row):
13                row_sum[i] += value
14                col_sum[j] += value
15      
16        # Initialize variable 'special_count' to count special positions
17        special_count = 0
18      
19        # Check for special positions where the value is 1 
20        # and its row and column sums are both exactly 1
21        for i in range(num_rows):
22            for j in range(num_cols):
23                if mat[i][j] == 1 and row_sum[i] == 1 and col_sum[j] == 1:
24                    # Increment the count of special positions
25                    special_count += 1
26      
27        # Return the final count of special positions
28        return special_count
29

Java Solution

1class Solution {
2    public int numSpecial(int[][] mat) {
3        int numRows = mat.length, numCols = mat[0].length;
4        int[] rowCount = new int[numRows];
5        int[] colCount = new int[numCols];
6      
7        // Calculate the sum of each row and each column
8        for (int i = 0; i < numRows; ++i) {
9            for (int j = 0; j < numCols; ++j) {
10                rowCount[i] += mat[i][j];
11                colCount[j] += mat[i][j];
12            }
13        }
14      
15        int specialCount = 0;
16      
17        // Iterate through the matrix to find special elements
18        // A special element is defined as the element that is the only '1' in its row and column
19        for (int i = 0; i < numRows; ++i) {
20            for (int j = 0; j < numCols; ++j) {
21                // Check if the current element is '1' and its corresponding
22                // row and column sums are '1' which would mean it's a special element
23                if (mat[i][j] == 1 && rowCount[i] == 1 && colCount[j] == 1) {
24                    specialCount++;
25                }
26            }
27        }
28      
29        // Return the total count of special elements found in the matrix
30        return specialCount;
31    }
32}
33

C++ Solution

1class Solution {
2public:
3    // Function to count the number of special positions in a binary matrix.
4    // A position (i, j) is called special if mat[i][j] is 1 and all other elements in row i and column j are 0.
5    int numSpecial(vector<vector<int>>& mat) {
6        int numRows = mat.size();           // Number of rows in the matrix
7        int numCols = mat[0].size();       // Number of columns in the matrix
8        vector<int> rowCount(numRows, 0);   // Row count to store the sum of each row
9        vector<int> colCount(numCols, 0);   // Column count to store the sum of each column
10      
11        // Fill rowCount and colCount by summing the values in each row and column
12        for (int i = 0; i < numRows; ++i) {
13            for (int j = 0; j < numCols; ++j) {
14                rowCount[i] += mat[i][j];
15                colCount[j] += mat[i][j];
16            }
17        }
18      
19        int specialCount = 0;  // Variable to store the number of special positions found
20      
21        // Search for special positions. A position (i, j) is special if
22        // mat[i][j] is 1 and the sum of both row i and column j is 1.
23        for (int i = 0; i < numRows; ++i) {
24            for (int j = 0; j < numCols; ++j) {
25                if (mat[i][j] == 1 && rowCount[i] == 1 && colCount[j] == 1) {
26                    specialCount++;  // Increment count if a special position is found
27                }
28            }
29        }
30      
31        return specialCount;  // Return the total count of special positions
32    }
33};
34

Typescript Solution

1function countSpecialElements(matrix: number[][]): number {
2    // Get the number of rows and columns from the matrix
3    const rowCount = matrix.length;
4    const colCount = matrix[0].length;
5  
6    // Create arrays to store the sum of elements in each row and column,
7    // and initialize each element of the arrays to 0
8    const rowSums = new Array(rowCount).fill(0);
9    const colSums = new Array(colCount).fill(0);
10  
11    // First pass: Calculate the number of 1's in each row and column
12    for (let rowIndex = 0; rowIndex < rowCount; rowIndex++) {
13        for (let colIndex = 0; colIndex < colCount; colIndex++) {
14            // If the element at the current position is 1, increment
15            // the corresponding row and column sums
16            if (matrix[rowIndex][colIndex] === 1) {
17                rowSums[rowIndex]++;
18                colSums[colIndex]++;
19            }
20        }
21    }
22
23    // Initialize the result variable which will hold the count of special elements
24    let specialCount = 0;
25
26    // Second pass: Check for special elements, which are the elements
27    // that are the only 1 in their row and column
28    for (let rowIndex = 0; rowIndex < rowCount; rowIndex++) {
29        for (let colIndex = 0; colIndex < colCount; colIndex++) {
30            // Check if the current element is 1 and if it's the only one
31            // in its row and column, if so increment the specialCount
32            if (matrix[rowIndex][colIndex] === 1 && rowSums[rowIndex] === 1 && colSums[colIndex] === 1) {
33                specialCount++;
34            }
35        }
36    }
37
38    // Return the count of special elements
39    return specialCount;
40}
41

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed by looking at the number of nested loops and the operations within them.

  • The code first initializes the row and column count arrays r and c, which is O(m) and O(n) respectively, where m is the number of rows and n is the number of columns in the input mat.
  • The first nested for loop iterates through all elements of the matrix to populate r and c, which will be O(m * n) since every element is visited once.
  • The second nested for loop also iterates through the entire matrix to count the number of special elements based on the conditions that rely on the previous computations stored in r and c. This is also O(m * n).

Hence, the overall time complexity is O(m * n) because this dominates the overall performance of the code.

Space Complexity

The space complexity of the code includes the space used for the input and any auxiliary space used:

  • The input matrix itself does not count towards auxiliary space complexity as it is given.
  • Two arrays r and c of length m and n are created to keep track of the sum of each row and column, which gives us O(m + n).

Therefore, the auxiliary space complexity is O(m + n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫