When there are less than 1% non-zero elements in matrix, we call this matrix sparse matrix. Because there are so many 0s in matrix. An efficient way to store sparse matrix is to use three tuple data structure. It stores each non-zero element in matrix. A tuple shows a matrix[i][j]’s value in matrix. public class Tuple { int… Read More »
This problem is from G4G: http://www.geeksforgeeks.org/find-k-such-that-all-elements-in-kth-row-are-0-and-kth-column-are-1-in-a-boolean-matrix/ The problem ask us to find a number k, where the kth row of is all 0, kth column is all 1 too. The value of [k, k] can be either 0 or 1. Take below array as example: The kth row/column should be 3: The trick of this problem is… Read More »
This problem is given by junmin: determines whether a 2d m*n integer array contains duplicate values within k indices of each other. For example: 1 2 3 4 k = 1 Outout: no 1 1 3 4 k=0 Output: no 1 1 3 4 k=1 Output: Yes 1 2 3 3 4 1 k=3 Output: Yes… Read More »
This is eveolved from 1D problem – find local min. I would say this is a interesting problem and hvae great solution. The definition of “local” is near elements, ans in same row or column. There is junmin’s implementation, link , which is similar to mine. And another very clear material from mit, link. package… Read More »