Matrix Strategies Flashcards
Make Columns and Rows Zeros
Given a two-dimensional array, if any element within is zero, make its whole row and column zero.
O(m*n) runtime complexity, where m is number of rows and n is number of columns. Memory Complexity of O(m + n).
One naive solution which may come to the mind is to do a scan of the 2D matrix and upon seeing a zero, make that whole column and row zero. But that is not correct; even if there is only 1 zero in the matrix, this will make the whole matrix zero.
We will, instead, do a scan of the 2D array and identify all the rows and columns that have a zero in them and store them in two sets.
Search in a Matrix
We are given a 2D array where all elements in any individual row or column are sorted. In such a matrix, we have to search or find the position of, a given key. The following example further elaborates on this problem.
Linear, O(m+n) runtime where ‘m’ is number of rows and ‘n’ is number of columns.
Constant, O(1) Memory
One simple solution is to scan the whole 2D array for the key in O(mn) time. However, there are better solutions with less time complexity that use the sorted property of matrix. We can use a binary search on each row to find if the key exists in a row or not. The time complexity of this solution is O(m * log n). Though it looks good, we have an even better solution.
Here is the algorithm that we are going to use. We start from the upper right corner of the matrix and compare its value with the key. If they are equal, we have found the position of the key. If the key is smaller than the current element, we move one position to the left. If the key is larger than the current element, we move one position down. The reason for doing so is because the matrix is sorted, moving left would result in lower values than the current value and moving down would result in higher values than the current value. We continue this process until either we find the element or go out of the boundary of the matrix (which indicates that the key does not exist). This solution will visit m + n elements at most in the matrix, giving us a time complexity of O(m + n). Also note that we cannot do our searching procedure from the top left or the bottom right corner since in both cases, the keys at either side of that corner are increasing or decreasing respectively. Note that we can start the search from the bottom left corner as well, which would result in similar results as starting from the top right.
Closest Meeting Point
Given N people on an MxM grid, find the point that requires the least total distance covered by all people to meet at that point.
Consider a 5x5 grid with 3 people; one at X(1,2), Y(3,3) and Z(4,2).
Linear, O(n) runtime, Here ‘n’ is the number of people on the grid.
Linear, O(n) Memory Complexity. Here ‘n’ is the number of people on the grid.
The solution uses the ‘centroid’ to find the minimum distance travelled point.
The centroid of a two-dimensional region is the arithmetic mean or average position of all the points. We can calculate the centroid of all the points with people on the grid and that will be the minimum distance travelled point. It can be calculated as follows:
centroid=( (x1+x2+x3+…+xn)/n, (y1+y2+y3+…+yn)/n )
It is the average of x-coordinates and y-coordinates.
In most cases, the centroid is the correct answer but, in some cases, the centroid gives the point closest to the correct point. So, to handle this case, we’ll first find the centroid and then check its surrounding 8 points for possible minimum distance travelled point. If any of those points has a distance less than the distance at the centroid, then that point will be the minimum distance travelled point.
The reason why the centroid sometimes gives an incorrect point is that we basically take the average of the all the points and then round off the value, irrespective of the minimum distance covered by all points. This will definitely return a point lying in the middle of all the points, which in most cases will be correct. But in some cases, the closest point may lie at any of the input points, which we will never be able to get using the Centroid formula. So, we double-check the neighbors of the “closest point” to handle this scenario.
Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1
Input: [[ 1, 2, 3],
[4, 5, 6],
[7, 8, 9] ]
Output: [1,2,3,6,9,8,7,4,5]
Example 2
Input: [[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12] ]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
The answer will be all the elements in clockwise order from the first-outer layer, followed by the elements from the second-outer layer, and so on.
We define the k-th outer layer of a matrix as all elements that have minimum distance to some border equal to k.
For each outer layer, we want to iterate through its elements in clockwise order starting from the top left corner. Suppose the current outer layer has top-left coordinates (r1, c1) and bottom-right coordinates (r2, c2).
Then, the top row is the set of elements (r1, c) for c = c1,…,c2, in that order. The rest of the right side is the set of elements (r, c2) for r = r1+1,…,r2, in that order. Then, if there are four sides to this layer (ie., r1
Time Complexity: O(N), where N is the total number of elements in the input matrix. We add every element in the matrix to our final answer.
Space Complexity: O(N), the information stored in ans.
Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:Our s
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] ]
Our strategy is to split a given matrix in four rectangles and reduce the initial problem to the rotation of these rectangles.
Time complexity: O(N2) is a complexity given by two inserted loops.
Space complexity: O(1) since we do a rotation in place.
Toeplitz Matrix
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element. Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
The first approach, group by category, has O(m*n) runtime complexity and O(m + n) memory complexity.
The second approach, Compare with top-left neighbor, has similar runtime complexity, but constant memory. For each diagonal with elements in order a1, a2, a3, …, ak, we can check a1=a2, a2=a3,…,ak-1=ak. The matrix is Toeplitz if and only if all of these conditions are true for all (top-left to bottom-right) diagonals.
