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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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.

Solution Implementation

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
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
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
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).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?


Recommended Readings


Got a question? Ask the Monster 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.


🪄