1582. Special Positions in a Binary Matrix

Time: O(mn)

Space: O(m+n)

Approach

Precompute row and column sums; count cells that are 1 with row sum = col sum = 1.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Matrix

Matrix problems often involve BFS/DFS flood fill, dynamic programming on 2D grids, or spiral/diagonal traversal. For row × column DP, break it into 1D sub-problems column by column. Common pitfalls: boundary checks and modifying the input matrix in-place.

1582.cs

// Approach: Precompute row and column sums; count cells that are 1 with row sum = col sum = 1.
// Time: O(mn) Space: O(m+n)

public class Solution
{
    public int NumSpecial(int[][] mat)
    {
        int m = mat.Length;
        int n = mat[0].Length;
        int[] rowsCount = new int[m];
        int[] colsCount = new int[n];
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mat[i][j] == 1)
                {
                    rowsCount[i]++;
                    colsCount[j]++;
                }
            }
        }

        int count = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mat[i][j] == 1 && rowsCount[i] == 1 && colsCount[j] == 1)
                    count++;
            }
        }

        return count;
    }
}

Was this solution helpful?