# Matrix
###### tags: `Study_aboard`
## Spiral Matrix
```cpp
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int border_up=-1, border_down=matrix.size(), border_left=-1, border_right=matrix[0].size();
vector <int> res;
char direction = 'r';
int cur_x=0, cur_y=0;
while(res.size()<(matrix.size()*matrix[0].size()) ){
res.push_back(matrix[cur_x][cur_y]);
if(direction == 'r'){
if(cur_y+1 < border_right){
cur_y = cur_y+1;
}
else{
direction = 'd';
border_up++;
cur_x = cur_x+1;
}
}
else if(direction == 'd'){
if(cur_x+1 < border_down){
cur_x = cur_x+1;
}
else{
direction = 'l';
border_right--;
cur_y = cur_y-1;
}
}
else if(direction == 'l'){
if(cur_y-1 > border_left){
cur_y = cur_y-1;
}
else{
direction = 'u';
border_down--;
cur_x --;
}
}
else if(direction == 'u'){
if(cur_x-1 > border_up){
cur_x = cur_x-1;
}
else{
direction = 'r';
border_left++;
cur_y = cur_y+1;
}
}
}
return res;
}
};
```
## Search a 2d Matrix
easy
sorted array -> use binary search
see https://hackmd.io/@chentzj/SkNIsGDpu binary search
```cpp
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty())
return false;
int left = 0, right = matrix.size();
// row use binary search II - search the first number that is greater or equal to the target
while (left < right) {
int mid = (left + right) / 2;
if (matrix[mid][0] == target) return true;
if (matrix[mid][0] < target) left = mid + 1;
else right = mid;
}
// right-1 will be the row we want
int tmp = (right > 0) ? (right - 1) : right;
left = 0;
right = matrix[tmp].size();
// binary search I
while (left < right) {
int mid = (left + right) / 2;
if (matrix[tmp][mid] == target) return true;
if (matrix[tmp][mid] < target) left = mid + 1;
else right = mid;
}
return false;
}
};
```
## Search a 2d Matrix II
要能夠search，需要先找出一致性。
觀察左下角與右上角，發現其邊有一致性，以左下角為例，其上方都是小於它的數字，而右方都是大於它的數字
```cpp
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if (matrix.empty() || matrix[0].empty())
return false;
if (target < matrix[0][0] || target > matrix.back().back())
return false;
int x = matrix.size() - 1, y = 0;
// x is row, y is col
while (true) {
if (matrix[x][y] > target)
--x;
else if (matrix[x][y] < target)
++y;
else return true;
if (x < 0 || y >= matrix[0].size())
break;
}
return false;
}
};
```
## Maximum Number of Points with Cost
Initial : divide and conquer
problem: TLE time complexity O(m * n * n)
solution: find same computation to reduce complexity
original version
```cpp
class Solution {
public:
long long maxPoints(vector<vector<int>>& points) {
long long int m = points.size(), n=points[0].size();
vector<vector<long long int>> dp(m, vector<long long int>(n, 0));
for(int i=0;i<n;i++){
dp[0][i] = points[0][i];
}
// i is row, j is col
for(int i=1;i<m;i++){
for(int j=0;j<n;j++){
long long int Max = INT_MIN;
for(int k=0;k<n;k++){
Max = max(Max,points[i][j]+dp[i-1][k]-abs(j-k));
}
dp[i][j] = Max;
}
}
long long int res=0;
for(int i=0;i<n;i++){
res = max(dp[m-1][i], res);
}
return res;
}
};
```
Initial:
Sol:若將abs(j-k)區分為 j-k (j>k) & k-j (k>j)，==則j與k之間並沒有關係==，可以==獨立拆出==而不須在j loop中執行k。
```cpp
class Solution {
public:
long long maxPoints(vector<vector<int>>& points) {
vector<vector<long long>> dp(points.size(), vector<long long>(points[0].size(), -1));
for (int i = 0; i < points[0].size(); ++i) {
dp[0][i] = points[0][i];
}
for (int i = 1; i < points.size(); ++i) {
vector<long long> left_dp(points[i].size(), -1);
vector<long long> right_dp(points[i].size(), -1);
// left_dp : the maximum value of dp[i-1][k'] from 0~k
// right_dp : the maximum value of dp[i-1][k'] from k~size()-1
left_dp[0] = dp[i - 1][0];
for (int k = 1; k < points[i].size(); ++k) {
left_dp[k] = max(left_dp[k - 1], dp[i - 1][k] + k);
}
right_dp.back() = dp[i - 1].back() - points[i].size() + 1;
for (int k = points[i].size() - 2; k >= 0; --k) {
right_dp[k] = max(right_dp[k + 1], dp[i - 1][k] - k);
}
for (int j = 0; j < points[i].size(); ++j) {
dp[i][j] = max(left_dp[j] - j, right_dp[j] + j) + points[i][j];
}
}
long long max_ans = -1;
for (const auto v : dp.back()) {
max_ans = max(max_ans, v);
}
return max_ans;
}
};
```
## Longest Increasing Path in a Matrix
1. DFS
```cpp
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
int res = 0;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
res = max(res,dfs(i,j,dp, matrix)) ;
}
}
return res;
}
int dfs(int i, int j, vector<vector<int>>& dp,vector<vector<int>>& matrix){
int mx = 1;
int len = 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
for (auto a : dirs) {
int x = i + a[0], y = j + a[1];
if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j])
continue;
if (dp[x][y]){
len = 1 + dp[x][y];
}
else{
len = 1 + dfs(x, y,dp, matrix);
}
mx = max(mx, len);
}
dp[i][j] = mx;
return mx;
}
};
```
## Sparse Matrix ==Facebook, google==
Nothing sepcial
```cpp
class Solution {
public:
/**
* @param A: a sparse matrix
* @param B: a sparse matrix
* @return: the result of A * B
*/
vector<vector<int>> multiply(vector<vector<int>> &A, vector<vector<int>> &B) {
vector< vector<int> > AB;
AB.clear();
int rowA = A.size(), columnA = A[0].size();
int rowB = B.size(), columnB = B[0].size();
// AB为 rowA * columnB 大小的矩阵
for (int i = 0; i < rowA; i++){
vector<int> tmp;
tmp.clear();
for (int j = 0; j < columnB; j++){
// 求出每一项
int sum = 0;
for (int k = 0; k < columnA; k++){
sum += A[i][k] * B[k][j];
}
tmp.push_back(sum);
}
AB.push_back(tmp);
}
return AB;
}
};
```
## Best meeting point ==Hard==
good problem
==Hint simplify the question first!!!==
```cpp
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
vector<int> rows, cols;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (grid[i][j] == 1) {
rows.push_back(i);
cols.push_back(j);
}
}
}
return minTotalDistance(rows) + minTotalDistance(cols);
}
int minTotalDistance(vector<int> v) {
int res = 0;
sort(v.begin(), v.end());
int i = 0, j = v.size() - 1;
while (i < j) res += v[j--] - v[i++];
return res;
}
};
```
## Minimum Garden Perimeter to Collect Enough Apples
Perimeter i = Perimeter i-1 + additional items
Additional items:
- 最外面上下左右四點 + 在x軸與y軸上的四點 = $2n*4 + n*4$ = $12*n$
- 4 \* (在x軸到右上方的點n + 右上方到y軸上n) = $2n*(n-1)*4$
- 4 \* (在x軸到右上方的點1~n + 右上方到y軸上1~n) = $n*(n-1)*4$
Sum = $12*n^2$
```cpp
class Solution {
public:
long long minimumPerimeter(long long neededApples) {
long long old_val=0, new_val=0;
for(int i=1; ;i++){
new_val = old_val + 12 * pow(i,2);
if(new_val>=neededApples) return i*2*4;
else old_val = new_val;
}
return new_val;
}
};
```
## Walls and Gates
Initial: do BFS for each empty room until reach the gate
If we reach a room that we are already done, we can return cur path + room path
Sol: start from empty gates may be faster !!
```cpp
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
queue<pair<int, int>> q;// bfs queue for row and col
vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // bfs children
for (int i = 0; i < rooms.size(); ++i) {
for (int j = 0; j < rooms[i].size(); ++j) {
if (rooms[i][j] == 0) q.push({i, j});
}
}
while (!q.empty()) {
int i = q.front().first, j = q.front().second;
q.pop();
for (int k = 0; k < dirs.size(); ++k) {
int x = i + dirs[k][0], y = j + dirs[k][1];
/* child does not exist
// rooms[x][y] < rooms[i][j] + 1
// 1. rooms[x][y] = -1
// 2. rooms[x][y] already walk through by a smaller distance gate
*/
if (x < 0 || x >= rooms.size() || y < 0 || y >= rooms[0].size() || rooms[x][y] < rooms[i][j] + 1) continue;
rooms[x][y] = rooms[i][j] + 1;
q.push({x, y});
}
}
}
};
```
## Shortest Distance from all buildings
初始想法:BFS算出每個building的distane map，加總取最小值
dist: temporary distane map
sum: sum of each temporary distance map
bfs: implement by queue
visit: bfs需要記得已走過的位置，因此將做完後的grid--來達成。而下一輪==的val也要--。此處有可能有疑問，可能有上一個building無法走到的empty space而導致仍為0，但下一個building是能夠通過的。但由於題目規定need to reach all buildings，因此此empty space也不能作為路徑。
```cpp
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int res = INT_MAX, val = 0, m = grid.size(), n = grid[0].size();
vector<vector<int>> sum = grid;
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (grid[i][j] == 1) {
res = INT_MAX;
vector<vector<int>> dist = grid;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
int a = q.front().first, b = q.front().second; q.pop();
for (int k = 0; k < dirs.size(); ++k) {
int x = a + dirs[k][0], y = b + dirs[k][1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == val) {
--grid[x][y];
dist[x][y] = dist[a][b] + 1;
sum[x][y] += dist[x][y] - 1;
q.push({x, y});
res = min(res, sum[x][y]);
}
}
}
--val;
}
}
}
return res == INT_MAX ? -1 : res;
}
};
```
Sign in with Wallet
Connect another wallet