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


  • 10
    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!


Log in to reply
 

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