# Posts tagged as “matrix”

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

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.


Example 2:

Input: mat = [[1,0,0],
[0,1,0],
[0,0,1]]
Output: 3
Explanation: (0,0), (1,1) and (2,2) are special positions.


Example 3:

Input: mat = [[0,0,0,1],
[1,0,0,0],
[0,1,1,0],
[0,0,0,0]]
Output: 2


Example 4:

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


Constraints:

• rows == mat.length
• cols == mat[i].length
• 1 <= rows, cols <= 100
• mat[i][j] is 0 or 1.

## Solution: Sum for each row and column

Brute force:
Time complexity: O(R*C*(R+C))
Space complexity: O(1)

We can pre-compute the sums for each row and each column, ans = sum(mat[r][c] == 1 and rsum[r] == 1 and csum[c] == 1)

Time complexity: O(R*C)
Space complexity: O(R+C)

## C++

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Example 1:

Input: mat = [[1,2,3],
[4,5,6],
[7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.


Example 2:

Input: mat = [[1,1,1,1],
[1,1,1,1],
[1,1,1,1],
[1,1,1,1]]
Output: 8


Example 3:

Input: mat = [[5]]
Output: 5


Constraints:

• n == mat.length == mat[i].length
• 1 <= n <= 100
• 1 <= mat[i][j] <= 100

## Solution: Brute Force

Note: if n is odd, be careful not to double count the center one.

Time complexity: O(n)
Space complexity: O(1)

## C++

Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.

Example 1:

Input: mat = [[1,0,1],
[1,1,0],
[1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2.
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.


Example 2:

Input: mat = [[0,1,1,0],
[0,1,1,1],
[1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3.
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2.
There are 2 rectangles of side 3x1.
There is 1 rectangle of side 3x2.
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.


Example 3:

Input: mat = [[1,1,1,1,1,1]]
Output: 21


Example 4:

Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5


Constraints:

• 1 <= rows <= 150
• 1 <= columns <= 150
• 0 <= mat[i][j] <= 1

## Solution 1: Brute Force w/ Pruning

Time complexity: O(m^2*n^2)
Space complexity: O(1)

## C++

Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:

1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

• Updates all values with newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).

2. getValue(int row, int col)

• Returns the current value of the coordinate (row,col) from the rectangle.

Example 1:

Input
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
Output


[null,1,null,5,5,null,10,5]

Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]); // The initial rectangle (4×3) looks like: // 1 2 1 // 4 3 4 // 3 2 1 // 1 1 1 subrectangleQueries.getValue(0, 2); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 5 5 5 subrectangleQueries.getValue(0, 2); // return 5 subrectangleQueries.getValue(3, 1); // return 5 subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 10 10 10 subrectangleQueries.getValue(3, 1); // return 10 subrectangleQueries.getValue(0, 2); // return 5

Example 2:

Input
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
Output


[null,1,null,100,100,null,20]

Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]); subrectangleQueries.getValue(0, 0); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100); subrectangleQueries.getValue(0, 0); // return 100 subrectangleQueries.getValue(2, 2); // return 100 subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20); subrectangleQueries.getValue(2, 2); // return 20

Constraints:

• There will be at most 500 operations considering both methods: updateSubrectangle and getValue.
• 1 <= rows, cols <= 100
• rows == rectangle.length
• cols == rectangle[i].length
• 0 <= row1 <= row2 < rows
• 0 <= col1 <= col2 < cols
• 1 <= newValue, rectangle[i][j] <= 10^9
• 0 <= row < rows
• 0 <= col < cols

## Solution 1: Simulation

Update the matrix values.

Time complexity:
Update: O(m*n), where m*n is the area of the sub-rectangle.
Query: O(1)

Space complexity: O(rows*cols)

## Solution 2: Geometry

For each update remember the region and value.

Time complexity:
Update: O(1)
Query: O(|U|), where |U| is the number of updates so far.

Space complexity: O(|U|)

## C++

Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column


Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.


Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]


Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= n, m <= 50
• 1 <= matrix[i][j] <= 10^5.
• All elements in the matrix are distinct.

## Solution: Pre-processing

Two pass. First pass, record the min val of each row, and max val of each column.
Second pass, identify lucky numbers.

Time complexity: O(m * n)
Space complexity: O(m + n)