Posts tagged as “matrix”

花花酱 LeetCode 1672. Richest Customer Wealth

By zxi on November 29, 2020

You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the i^th customer has in the j^th bank. Return the wealth that the richest customer has.

A customer’s wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

Example 1:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

Example 2:

Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation: 
1st customer has wealth = 6
2nd customer has wealth = 10 
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.

Example 3:

Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17

Constraints:

m == accounts.length
n == accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100

Solution: Sum each row up

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

C++

// Author: Huahua

class Solution {

public:

int maximumWealth(vector<vector<int>>& accounts) {

int ans = 0;

for (const vector<int>& row : accounts)

ans = max(ans, accumulate(begin(row), end(row), 0));

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def maximumWealth(self, accounts: List[List[int]]) -> int:

return max(sum(account) for account in accounts)

花花酱 LeetCode 1632. Rank Transform of a Matrix

By zxi on October 28, 2020

Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].

The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:

The rank is an integer starting from 1.
If two elements p and q are in the same row or column, then:
- If p < q then rank(p) < rank(q)
- If p == q then rank(p) == rank(q)
- If p > q then rank(p) > rank(q)
The rank should be as small as possible.

It is guaranteed that answer is unique under the given rules.

Example 1:

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.

Example 2:

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

Example 3:

Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

Example 4:

Input: matrix = [[7,3,6],[1,4,5],[9,8,2]]
Output: [[5,1,4],[1,2,3],[6,3,1]]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-10⁹ <= matrix[row][col] <= 10⁹

Solution: Union Find

Group cells by their values, process groups (cells that have the same value) in ascending order (smaller number has smaller rank).

For cells that are in the same row and same cols union them using union find, they should have the same rank which equals to max(max_rank_x[cols], max_rank_y[rows]) + 1.

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

C++

// Author: Huahua

class DSU {

public:

DSU(int n): p_(n, -1) {}

int find(int x) {

return p_[x] == -1 ? x : p_[x] = find(p_[x]);

}

void merge(int x, int y) {

x = find(x), y = find(y);

if (x != y) p_[x] = y;

}

private:

vector<int> p_;

};

class Solution {

public:

vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

vector<vector<int>> ans(m, vector<int>(n));

map<int, vector<pair<int, int>>> mp; // val -> {positions}

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x)

mp[matrix[y][x]].emplace_back(x, y);

vector<int> rx(n), ry(m);

for (const auto& [val, ps]: mp) {

DSU dsu(n + m);

vector<vector<pair<int, int>>> cc(n + m); // val -> {positions}

for (const auto& [x, y]: ps)

dsu.merge(x, y + n);

for (const auto& [x, y]: ps)

cc[dsu.find(x)].emplace_back(x, y);

for (const auto& ps: cc) {

int rank = 1;

for (const auto& [x, y]: ps)

rank = max(rank, max(rx[x], ry[y]) + 1);

for (const auto& [x, y]: ps)

rx[x] = ry[y] = ans[y][x] = rank;

}

return ans;

}

};

花花酱 LeetCode 1605. Find Valid Matrix Given Row and Column Sums

By zxi on October 3, 2020

You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the i^th row and colSum[j] is the sum of the elements of the j^th column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.

Find any matrix of non-negative integers of size rowSum.length x colSum.length that satisfies the rowSum and colSum requirements.

Return a 2D array representing any matrix that fulfills the requirements. It’s guaranteed that at least one matrix that fulfills the requirements exists.

Example 1:

Input: rowSum = [3,8], colSum = [4,7]
Output: [[3,0],
         [1,7]]
Explanation:
0th row: 3 + 0 = 0 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2],
                             [3,5]]

Example 2:

Input: rowSum = [5,7,10], colSum = [8,6,8]
Output: [[0,5,0],
         [6,1,0],
         [2,0,8]]

Example 3:

Input: rowSum = [14,9], colSum = [6,9,8]
Output: [[0,9,5],
         [6,0,3]]

Example 4:

Input: rowSum = [1,0], colSum = [1]
Output: [[1],
         [0]]

Example 5:

Input: rowSum = [0], colSum = [0]
Output: [[0]]

Constraints:

1 <= rowSum.length, colSum.length <= 500
0 <= rowSum[i], colSum[i] <= 10⁸
sum(rows) == sum(columns)

Solution: Greedy

Let a = min(row[i], col[j]), m[i][j] = a, row[i] -= a, col[j] -=a

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {

const int m = rowSum.size();

const int n = colSum.size();

vector<vector<int>> ans(m, vector<int>(n));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

ans[i][j] = min(rowSum[i], colSum[j]);

rowSum[i] -= ans[i][j];

colSum[j] -= ans[i][j];

}

return ans;

}

};

花花酱 LeetCode 1594. Maximum Non Negative Product in a Matrix

By zxi on September 21, 2020

You are given a rows x cols matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.

Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (rows - 1, cols - 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.

Return the maximum non-negative product modulo 10⁹ + 7. If the maximum product is negative return -1.

Notice that the modulo is performed after getting the maximum product.

Example 1:

Input: grid = [[-1,-2,-3],
               [-2,-3,-3],
               [-3,-3,-2]]
Output: -1
Explanation: It's not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.

Example 2:

Input: grid = [[1,-2,1],
               [1,-2,1],
               [3,-4,1]]
Output: 8
Explanation: Maximum non-negative product is in bold (1 * 1 * -2 * -4 * 1 = 8).

Example 3:

Input: grid = [[1, 3],
               [0,-4]]
Output: 0
Explanation: Maximum non-negative product is in bold (1 * 0 * -4 = 0).

Example 4:

Input: grid = [[ 1, 4,4,0],
               [-2, 0,0,1],
               [ 1,-1,1,1]]
Output: 2
Explanation: Maximum non-negative product is in bold (1 * -2 * 1 * -1 * 1 * 1 = 2).

Constraints:

1 <= rows, cols <= 15
-4 <= grid[i][j] <= 4

Solution: DP

Use two dp arrays,

dp_max[i][j] := max product of matrix[0~i][0~j]
dp_min[i][j] := min product of matrix[0~i][0~j]

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

C++

// Author: Huahua

class Solution {

public:

int maxProductPath(vector<vector<int>>& grid) {

constexpr int kMod = 1e9 + 7;

const int m = grid.size();

const int n = grid[0].size();

vector<vector<long>> dp_max(m, vector<long>(n));

vector<vector<long>> dp_min(m, vector<long>(n));

dp_max[0][0] = dp_min[0][0] = grid[0][0];

for (int i = 1; i < m; ++i)

dp_max[i][0] = dp_min[i][0] = dp_min[i - 1][0] * grid[i][0];

for (int j = 1; j < n; ++j)

dp_max[0][j] = dp_min[0][j] = dp_min[0][j - 1] * grid[0][j];

for (int i = 1; i < m; ++i)

for (int j = 1; j < n; ++j) {

if (grid[i][j] >= 0) {

dp_max[i][j] = max(dp_max[i - 1][j], dp_max[i][j - 1]) * grid[i][j];

dp_min[i][j] = min(dp_min[i - 1][j], dp_min[i][j - 1]) * grid[i][j];

} else {

dp_max[i][j] = min(dp_min[i - 1][j], dp_min[i][j - 1]) * grid[i][j];

dp_min[i][j] = max(dp_max[i - 1][j], dp_max[i][j - 1]) * grid[i][j];

}

return dp_max[m - 1][n - 1] >= 0 ? dp_max[m - 1][n - 1] % kMod : -1;

}

};

花花酱 LeetCode 1582. Special Positions in a Binary Matrix

By zxi on September 12, 2020

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++

class Solution {

public:

int numSpecial(vector<vector<int>>& mat) {

const int rows = mat.size();

const int cols = mat[0].size();

vector<int> rs(rows);

vector<int> cs(cols);

for (int r = 0; r < rows; ++r)

for (int c = 0; c < cols; ++c) {

rs[r] += mat[r][c];

cs[c] += mat[r][c];

}

int ans = 0;

for (int r = 0; r < rows; ++r)

for (int c = 0; c < cols; ++c)

ans += mat[r][c] && rs[r] == 1 && cs[c] == 1;

return ans;

}

};