Posts tagged as “matrix”

花花酱 LeetCode 889. Spiral Matrix III

By zxi on August 13, 2018

Problem

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Note:

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

Solution: Simulation

We can find out the moving sequence is ESWWNNEEESSSWWWWNNNN.

The pattern is 1,1,2,2,3,3,4,4,… steps in one direction, and turn right for 90 degrees.

directions are E,S,W,N,E,S,W,N…

Time complexity: O(max(R,C)^2)

Space complexity: O(1) or O(RC) if ans included.

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

int k = 0;

int dirs[][2]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // ESWN

int d = 0; // E

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

while (++k) {

for (int i = 0; i < 2; ++i) {

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

c0 += dirs[d][0];

r0 += dirs[d][1];

if (c0 < 0 || c0 >= C || r0 < 0 || r0 >= R) continue;

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

}

d = (d + 1) % 4;

}

return {};

}

};

花花酱 LeetCode 542. 01 Matrix

By zxi on July 14, 2018

Problem

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

Solution 1: DP

Two passes:

down, right
up, left

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Running time: 132 ms

class Solution {

public:

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

int m = matrix.size();

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

vector<vector<int>> ans(m, vector<int>(n, INT_MAX - m * n));

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

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

if (matrix[i][j]) {

if (i > 0) ans[i][j] = min(ans[i][j], ans[i - 1][j] + 1);

if (j > 0) ans[i][j] = min(ans[i][j], ans[i][j - 1] + 1);

} else {

ans[i][j] = 0;

}

for (int i = m - 1; i >= 0; --i)

for (int j = n - 1; j >= 0; --j) {

if (i < m - 1) ans[i][j] = min(ans[i][j], ans[i + 1][j] + 1);

if (j < n - 1) ans[i][j] = min(ans[i][j], ans[i][j + 1] + 1);

}

return ans;

}

};

Solution 2: BFS

Start from all 0 cells and find shortest paths to rest of the cells.

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Running time: 136 ms

class Solution {

public:

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

const int m = matrix.size();

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

queue<pair<int, int>> q;

vector<vector<int>> seen(m, vector<int>(n, 0));

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

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

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

if (matrix[i][j] == 0) {

q.push({i, j});

seen[i][j] = 1;

}

vector<int> dirs{0, -1, 0, 1, 0};

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto pair = q.front(); q.pop();

int i = pair.first;

int j = pair.second;

ans[i][j] = steps;

for (int k = 0; k < 4; ++k) {

int x = j + dirs[k];

int y = i + dirs[k + 1];

if (x < 0 || x >= n || y < 0 || y >= m || seen[y][x]) continue;

seen[y][x] = 1;

q.push({y, x});

}

++steps;

}

return ans;

}

};

花花酱 LeetCode 840. Magic Squares In Grid

By zxi on July 8, 2018

Problem

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

Solution

Time complexity: O(m*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

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

int m = grid.size();

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

int ans = 0;

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

for (int j = 0; j < n - 2; ++j)

ans += magic(grid, j, i);

return ans;

}

private:

int magic(const vector<vector<int>>& grid, int x, int y) {

vector<int> rows(3);

vector<int> cols(3);

vector<int> exps{15, 15, 15};

int dig = 0;

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

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

int v = grid[y + i][x + j];

if (v <= 0 || v > 9) return 0; // must between 1 and 9

rows[i] += v;

cols[j] += v;

if (i == j) dig += v;

}

return rows == exps && cols == exps && dig == 15;

}

};

花花酱 LeetCode 867. Transpose Matrix

By zxi on July 8, 2018

Given a matrix A, return the transpose of A.

The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

Example 1:

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

Example 2:

Input: [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]

Note:

1 <= A.length <= 1000
1 <= A[0].length <= 1000

Solution: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<vector<int>> transpose(vector<vector<int>>& A) {

int m = A.size();

int n = A[0].size();

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

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

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

ans[j][i] = A[i][j];

return ans;

}

};

花花酱 LeetCode 598. Range Addition II

By zxi on March 20, 2018

Problem

https://leetcode.com/problems/range-addition-ii/description/

Given an m * n matrix M initialized with all 0‘s and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positiveintegers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

The range of m and n is [1,40000].
The range of a is [1,m], and the range of b is [1,n].
The range of operations size won’t exceed 10,000.

Solution:

Time Complexity: O(n)

Space Complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int maxCount(int m, int n, vector<vector<int>>& ops) {

for (const auto& range : ops) {

m = min(m, range[0]);

n = min(n, range[1]);

}

return m * n;

}

};