C++ O(1) space using "game of life" idea


  • 12
    J

    Derived from StefanPochmann's idea in "game of life": the board has ints in [0, 255], hence only 8-bit is used, we can use the middle 8-bit to store the new state (average value), replace the old state with the new state by shifting all values 8 bits to the right.

        vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
            int m = M.size(), n = M[0].size();
            if (m == 0 || n == 0) return {{}};
            vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{1,1},{-1,1},{1,-1}};
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int sum = M[i][j], cnt = 1;
                    for (int k = 0; k < dirs.size(); k++) {
                        int x = i + dirs[k][0], y = j + dirs[k][1];
                        if (x < 0 || x > m - 1 || y < 0 || y > n - 1) continue;
                        sum += (M[x][y] & 0xFF);
                        cnt++;
                    }
                    M[i][j] |= ((sum / cnt) << 8);
                }
            }
             for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    M[i][j] >>= 8;
                }
             }
            return M;
        }
    
    

  • 0
    A

    good idea!!!


  • 0
    M

    @jeanmuu could you or someone please explain why & 0xFF is needed in line
    sum += (M[x][y] & 0xFF);

    if numbers are always between [0,255], why do we need to do this?


  • 2
    T

    @mmmtm Because the surrounding M[x][y] who is before M[i][j] has been modified in former calculation, only last 8 bits can been used.


  • 0
    M

    @tornmy ahhh makes sense... thank you so much!


  • 0
    A

    Can help to explain why this is O(1) instead of O(m*n) extra space? is it because m,n < 150?


  • 0
    D

    @alanzorro I think it is because the result only use the high bits of M. no other space.


  • 0
    O

    @alanzorro indeed, this elegant solution doesn't use extra memory than what was given to the function call. The initial information only uses one third of the available space in the matrix, so we can leverage that to avoid creating another matrix :-)


  • 0
    X

    brilliant idea!
    Java version:

    public class Solution {    
    	public int[][] imageSmoother(int[][] M) {
    		// in-place solution
    		int m = M.length, n = M[0].length;
    		if (m == 0 || n == 0)
    			return new int[0][0];
    		int[][] dirs = {{-1,-1},{-1,0},{-1,1}, {0, -1}, {0, 1},{1,-1}, {1,0},{1,1}};
    		for (int i = 0; i < m; ++i)
    			for (int j = 0; j < n; ++j) {
    				int sum = M[i][j], cnt = 1;
    				for (int k = 0; k < dirs.length; ++k) {
    					int x = i + dirs[k][0], y = j + dirs[k][1];
    					if (x < 0 || x > m - 1 || y < 0 || y > n - 1)
    						continue;
    					sum += (M[x][y] & 0xFF);
    					cnt++;
    				}
    				M[i][j] |= ((sum / cnt) << 8);
    			}
    		
    		for (int i = 0; i < m; ++i)
    			for (int j = 0; j < n; ++j)
    				M[i][j] >>= 8;
    		return M;
    	}
    }
    

Log in to reply
 

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