Press "Enter" to skip to content

Posts tagged as “matrix”

花花酱 LeetCode 2373. Largest Local Values in a Matrix

You are given an n x n integer matrix grid.

Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:

  • maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.

In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.

Return the generated matrix.

Example 1:

Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
Output: [[9,9],[8,6]]
Explanation: The diagram above shows the original matrix and the generated matrix.
Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.

Example 2:

Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
Output: [[2,2,2],[2,2,2],[2,2,2]]
Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.

Constraints:

  • n == grid.length == grid[i].length
  • 3 <= n <= 100
  • 1 <= grid[i][j] <= 100

Solution: Brute Force

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

C++

花花酱 LeetCode 2125. Number of Laser Beams in a Bank

Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of the bank, which is an m x n 2D matrix. bank[i] represents the ith row, consisting of '0's and '1's. '0' means the cell is empty, while'1' means the cell has a security device.

There is one laser beam between any two security devices if both conditions are met:

  • The two devices are located on two different rowsr1 and r2, where r1 < r2.
  • For each row i where r1 < i < r2, there are no security devices in the ith row.

Laser beams are independent, i.e., one beam does not interfere nor join with another.

Return the total number of laser beams in the bank.

Example 1:

Input: bank = ["011001","000000","010100","001000"]
Output: 8
Explanation: Between each of the following device pairs, there is one beam. In total, there are 8 beams:
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
Note that there is no beam between any device on the 0th row with any on the 3rd row.
This is because the 2nd row contains security devices, which breaks the second condition.

Example 2:

Input: bank = ["000","111","000"]
Output: 0
Explanation: There does not exist two devices located on two different rows.

Constraints:

  • m == bank.length
  • n == bank[i].length
  • 1 <= m, n <= 500
  • bank[i][j] is either '0' or '1'.

Solution: Rule of product

Just need to remember the # of devices of prev non-empty row.
# of beams between two non-empty row equals to row[i] * row[j]
ans += prev * curr

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

C++

Python3

花花酱 LeetCode 1975. Maximum Matrix Sum

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
  • -105 <= matrix[i][j] <= 105

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(n2)
Space complexity: O(1)

C++

花花酱 LeetCode 835. Image Overlap

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(n4) Note: this is the same as brute force / simulation method if the matrix is dense.
Space complexity: O(n2)

C++

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

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 * 104
  • 1 <= original[i] <= 105
  • 1 <= m, n <= 4 * 104

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