Posts tagged as “matrix”

花花酱 LeetCode 1351. Count Negative Numbers in a Sorted Matrix

By zxi on February 16, 2020

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.

Return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

Solution 1: Brute Force

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

C++

// Author: Huahua, 16 ms, 10.4 MB

class Solution {

public:

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

int ans = 0;

for (const auto& row : grid)

for (const auto x : row)

ans += x < 0;

return ans;

}

};

Solution 2: Find the frontier

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

C++

// Author: Huahua, 16 ms, 10.4 MB

class Solution {

public:

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

int ans = 0;

int m = grid.size();

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

int r = m - 1;

int c = 0;

while (r >= 0 && c < n) {

if (grid[r][c] < 0) {

ans += n - c;

--r;

} else {

++c;

}

return ans;

}

};

花花酱 LeetCode 1329. Sort the Matrix Diagonally

By zxi on January 26, 2020

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

Example 1:

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

Constraints:

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

Solution: HashTable

Collect each diagonal’s (keyed by i – j) elements into an array and sort it separately.
If we offset the key by n, e.g. i – j + n, we can use an array instead of a hashtable.

Time complexity: O(m*n + (m+n) * (m+n) * log(m + n))) = (n^2*logn)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

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

const int m = mat.size();

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

vector<deque<int>> qs(m + n);

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

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

qs[i - j + n].push_back(mat[i][j]);

for (auto& q : qs)

sort(begin(q), end(q));

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

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

mat[i][j] = qs[i - j + n].front();

qs[i - j + n].pop_front();

}

return mat;

}

};

花花酱 LeetCode 1314. Matrix Block Sum

By zxi on January 11, 2020

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

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

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100

Solution: 2D range query

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

C++

// Author: Huahua, 20 ms

class Solution {

public:

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {

const int n = mat.size();

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

vector<vector<int>> dp(n + 1, vector<int>(m + 1));

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

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

dp[y][x] = dp[y - 1][x] + dp[y][x - 1] + mat[y - 1][x - 1] - dp[y - 1][x - 1];

auto ans = mat;

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

for (int x = 1; x <= m; ++x) {

int x1 = max(1, x - K);

int x2 = min(m, x + K);

int y1 = max(1, y - K);

int y2 = min(n, y + K);

ans[y - 1][x - 1] = dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1];

}

return ans;

}

};

花花酱 LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

By zxi on December 17, 2019

Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

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

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

Constraints:

1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5

Solution: DP + Brute Force

Precompute the sums of sub-matrixes whose left-top corner is at (0,0).

Try all possible left-top corner and sizes.

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

C++

// Author: Huahua, 148 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

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

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

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

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

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

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

for (int k = 0; y + k <= m && x + k <= n; ++k) {

if (rangeSum(x, y, x + k, y + k) > threshold) break;

ans = max(ans, k + 1);

}

return ans;

}

};

Solution 2: Binary Search

Search for the smallest size k that is greater than the threshold, ans = k – 1.

C++

// Author: Huahua, 116 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

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

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

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

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

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

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

int l = 0;

int r = min(m - y, n - x) + 1;

while (l < r) {

int m = l + (r - l) / 2;

// Find smllest l that > threshold, ans = (l + 1) - 1

if (rangeSum(x, y, x + m, y + m) > threshold)

r = m;

else

l = m + 1;

}

ans = max(ans, (l + 1) - 1);

}

return ans;

}

};

Solution 3: Bounded Search

Time complexity: O(m*n + min(m,n))

C++

// Author: Huahua, 148 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

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

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

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

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

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

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

for (int k = ans; y + k <= m && x + k <= n; ++k) {

if (rangeSum(x, y, x + k, y + k) > threshold) break;

ans = max(ans, k + 1);

}

return ans;

}

};

花花酱 LeetCode 48. Rotate Image

By zxi on October 2, 2019

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Solution: 2 Passes

First pass: mirror around diagonal
Second pass: mirror around y axis

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

C++

// Author: Huahua

class Solution {

public:

void rotate(vector<vector<int>>& matrix) {

const int n = matrix.size();

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

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

swap(matrix[i][j], matrix[j][i]);

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

reverse(begin(matrix[i]), end(matrix[i]));

}

};