Easy Understand O(1) Space Accepted Java Solution with Idea Explained


  • -2
    M

    The difficulty of this problem is once we set the row and column all to be zero, we can not distinguish the original zeros and new-set zeros.

    My basic idea to handle this is to find a really unique value that is not contained in the matrix. Then we begin scanning the whole matrix. Once we find a zero, set all its column and row to that unique value first. Then when the scan is completed, all elements need to be zero are now changed to that unique value. Finally a easy fully scan can change all unique value to zero.Mission accomplished!
    However, if the matrix contains all integer values, this solution would fall into infinite loop trying to find that unique value.
    This is not a clever solution though, but it worked and acceptable.

    public void setZeroes(int[][] matrix) {
    	int unique = 1;
    	int height = matrix.length;
    	int width = matrix[0].length;
     // find the unique value one by one
    	while (true) {
    		boolean hasCopy = false;
    		a: for (int i = 0; i < height; i++) {
    
    			for (int j = 0; j < width; j++)
    				if (matrix[i][j] == unique) {
    					hasCopy = true;
    					break a;
    				}
    		}
    		if (hasCopy)
    			unique++;
    		else
    			break;
    	}
    
    	for (int i = 0; i < height; i++)
    		for (int j = 0; j < width; j++) {
    			if (matrix[i][j] == 0) {
    				for (int k = 0; k < height; k++)
    					if (matrix[k][j] != 0)
    						matrix[k][j] = unique;
    
    				for (int k = 0; k < width; k++)
    					if (matrix[i][k] != 0)
    						matrix[i][k] = unique;
    				matrix[i][j] = unique;
    			}
    		}
    
    	for (int i = 0; i < height; i++)
    		for (int j = 0; j < width; j++)
    			if (matrix[i][j] == unique)
    				matrix[i][j] = 0;
    
    }

  • 0
    T

    That looks like a big constant multiplier for O(n*m), I think a random from the full Integer range can be faster on OJ, thought that may never find a value IRL.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.