Posts tagged as “matrix”

花花酱 LeetCode 1975. Maximum Matrix Sum

By zxi on December 31, 2021

You are given an n x n integer matrix. You can do the following operation any number of times:

Choose any two adjacent elements of matrix and multiply each of them by -1.

Two elements are considered adjacent if and only if they share a border.

Your goal is to maximize the summation of the matrix’s elements. Return the maximum sum of the matrix’s elements using the operation mentioned above.

Example 1:

Input: matrix = [[1,-1],[-1,1]]
Output: 4
Explanation: We can follow the following steps to reach sum equals 4:
- Multiply the 2 elements in the first row by -1.
- Multiply the 2 elements in the first column by -1.

Example 2:

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
Output: 16
Explanation: We can follow the following step to reach sum equals 16:
- Multiply the 2 last elements in the second row by -1.

Constraints:

n == matrix.length == matrix[i].length
2 <= n <= 250
-10⁵ <= matrix[i][j] <= 10⁵

Solution: Math

Count the number of negative numbers.
1. Even negatives, we can always flip all the negatives to positives. ans = sum(abs(matrix)).
2. Odd negatives, there will be one negative left, we found the smallest abs(element) and let it become negative. ans = sum(abs(matrix))) – 2 * min(abs(matrix))

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

C++

// Author: Huahua

class Solution {

public:

long long maxMatrixSum(vector<vector<int>>& matrix) {

const int n = matrix.size();

long long ans = 0;

int count = 0;

int lo = INT_MAX;

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

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

ans += abs(matrix[i][j]);

lo = min(lo, abs(matrix[i][j]));

count += matrix[i][j] < 0;

}

return ans - (count & 1) * 2 * lo;

}

};

花花酱 LeetCode 835. Image Overlap

By zxi on December 23, 2021

You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.

We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.

Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.

Return the largest possible overlap.

Example 1:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

The number of positions that have a 1 in both images is 3 (shown in red).

Example 2:

Input: img1 = [[1]], img2 = [[1]]
Output: 1

Example 3:

Input: img1 = [[0]], img2 = [[0]]
Output: 0

Constraints:

n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j] is either 0 or 1.
img2[i][j] is either 0 or 1.

Solution: Hashtable of offsets

Enumerate all pairs of 1 cells (x1, y1) (x2, y2), the key / offset will be ((x1-x2), (y1-y2)), i.e how should we shift the image to have those two cells overlapped. Use a counter to find the most common/best offset.

Time complexity: O(n⁴) Note: this is the same as brute force / simulation method if the matrix is dense.
Space complexity: O(n²)

C++

// Author: Huahua

class Solution {

public:

int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {

const int n = img1.size();

unordered_map<int, int> m;

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

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

if (img1[y1][x1])

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

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

if (img2[y2][x2])

++m[(x1 - x2) * 100 + (y1 - y2)];

int ans = 0;

for (const auto [key, count] : m)

ans = max(ans, count);

return ans;

}

};

花花酱 LeetCode 2022. Convert 1D Array Into 2D Array

By zxi on October 23, 2021

You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.

The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.

Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.

Example 1:

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation:
The constructed 2D array should contain 2 rows and 2 columns.
The first group of n=2 elements in original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in original, [3,4], becomes the second row in the constructed 2D array.

Example 2:

Input: original = [1,2,3], m = 1, n = 3
Output: [[1,2,3]]
Explanation:
The constructed 2D array should contain 1 row and 3 columns.
Put all three elements in original into the first row of the constructed 2D array.

Example 3:

Input: original = [1,2], m = 1, n = 1
Output: []
Explanation:
There are 2 elements in original.
It is impossible to fit 2 elements in a 1x1 2D array, so return an empty 2D array.

Example 4:

Input: original = [3], m = 1, n = 2
Output: []
Explanation:
There is 1 element in original.
It is impossible to make 1 element fill all the spots in a 1x2 2D array, so return an empty 2D array.

Constraints:

1 <= original.length <= 5 * 10⁴
1 <= original[i] <= 10⁵
1 <= m, n <= 4 * 10⁴

Solution: Brute Force

the i-th element in original array will have index (i//n, i % n) in the 2D array.

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

C++

class Solution {

public:

vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {

if (original.size() != m * n) return {};

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

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

ans[i / n][i % n] = original[i];

return ans;

}

};

花花酱 LeetCode 1886. Determine Whether Matrix Can Be Obtained By Rotation

By zxi on August 8, 2021

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

Example 1:

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise to make mat equal target.

Example 2:

Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
Output: false
Explanation: It is impossible to make mat equal to target by rotating mat.

Example 3:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise two times to make mat equal target.

Constraints:

n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] and target[i][j] are either 0 or 1.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {

const int n = mat.size();

auto rot = [n](vector<vector<int>>& mat) {

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

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

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

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

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

swap(mat[i][j], mat[n - i - 1][j]);

return mat;

};

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

if (rot(mat) == target) return true;

return false;

}

};

花花酱 LeetCode 1727. Largest Submatrix With Rearrangements

By zxi on January 17, 2021

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

Example 4:

Input: matrix = [[0,0],[0,0]]
Output: 0
Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] is 0 or 1.

Solution: DP + Sorting

Preprocess each column, for col j, matrix[i][j] := length consecutive ones of col j.

[0,0,1]    [0,0,1]
[1,1,1] => [1,1,2]
[1,0,1]    [2,0,3]

Then we enumerate ending row, for each ending row i, we sort row[i] in deceasing order

e.g. i = 2

[0,0,1]                  [-,-,-]
[1,1,2] sort by row 2 => [-,-,-]
[2,0,3]                  [3,2,0]

row[2][1] = 3, means there is a 3×1 all ones sub matrix, area = 3
row[2][2] = 2, means there is a 2×2 all ones sub matrix, area = 4.

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

C++

// Author: Huahua

class Solution {

public:

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

const int m = matrix.size();

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

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

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

if (matrix[i][j]) matrix[i][j] += matrix[i - 1][j];

int ans = 0;

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

sort(rbegin(matrix[i]), rend(matrix[i]));

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

ans = max(ans, (j + 1) * matrix[i][j]);

}

return ans;

}

};