BastterCode monthly Julho - 73. Set Matrix Zeroes
comentada em 24/08/2023 23:58

@icarocd tens razão !!

Pessoal, a mensagem era brincadeira mas favor considerar evitar O(mn) apenas em memória!!

Infelizmente eu não tenho poder de editar

@Giovanni dá uma editada aí.

@Giovanni ficou ótimo

Não consegui fazer em O(1) space ainda, até agora só consegui em worst-case O(n). Mas já é melhor tanto que O(mn) quanto que O(m + n), então é um ganho.

Tem uma implementação de stack em cima, mas foi totalmente desnecessário, coloquei só pra treinar mesmo. É o mesmo que ter usado um vetor direto na função "main".

static constexpr unsigned char ZERO = 0;

template<typename T>
class Stack {
private: 
    vector<T> stack{}; 
public: 
    auto getfromStack() {
        auto result = stack.back();
        stack.pop_back();
        return result;
    }

    void insert(T val) {
        stack.push_back(val);
    }
  
    bool isEmpty() {
        return stack.size() == ZERO;
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {       
        const size_t num_row = matrix.size();
        const size_t num_col = matrix[ZERO].size();
      
        Stack<unsigned char> clearCol{};
        
        for (auto row = ZERO; row < num_row; ++row) {
            bool clearRow = false;
            
            for (auto col = ZERO; col < num_col; ++col) {
                if (matrix[row][col] == ZERO) {
                    clearRow = true;
                    clearCol.insert(col);
                }
            }
          
            if (clearRow) 
                for (auto&& n : matrix[row]) n = ZERO;
        }
        
        while (clearCol.isEmpty() == false) {
            auto col = clearCol.getfromStack();
            
            for (auto row = ZERO; row < num_row; ++row) 
              matrix[row][col] = ZERO;
        }
    }
};?

Tive uma ideia agora de manhã. Como são no máximo 200 colunas (conforme as constraints do problema) e como consigo representar a posição das colunas com bits, então poderia representar a posição de todas as colunas em 200 / 8 = 25 bytes. Como cada char é 1 byte, é suficiente um array de 25 chars.

Na hora fiquei contente porque pensei que essa seria uma solução O(1) em space. Mas pensando melhor, percebi que o número de chars ainda é dependente do número de colunas. Usar os chars é apenas uma forma eficiente (em memória, não necessariamente em tempo) de O(n) em space.

Enfim, vou continuar pensando para ver se tenho alguma ideia durante o mês. Segue o código.

Ah, uma coisa interessante que descobri enquanto escrevia o código. Imagino que a maioria já saiba que mover os bits para a direita ou para a esquerda é equivalente a dividir ou multiplicar o número por uma potência de 2.

Se você move cada bit 1 posição para a esquerda, por exemplo, então cada bit na nova posição representa a potência de 2 imediatamente superior, o que é o mesmo que multiplicar todo o número por 2. Se o movimento fosse de 3 posições, então cada bit representaria a terceira potência de dois superior, ou seja, seria o mesmo que multiplicar o número por 2^3 = 8. O mesmo vale para mover os bits para a direita, que é equivalente a dividir o número por uma potência de dois.

O que eu descobri é o seguinte. Tirar o modulo do número, ou seja, o resto da divisão por outro número x, em que x é uma potência de 2, é equivalente a fazer um AND com x - 1.

Isso porque na divisão por potências de 2, eu estou apenas movendo os bits para a direita e o resto é o que é "desprezado" nesse movimento. Ou seja, aqueles bits lá no final do número que somem quando eu movo todos os bits para a direita.

Como x no caso é potência de 2, então x - 1 tem todos os bits ligados até o bit anterior ao que está ligado em x. É assim que a representação funciona em binário (e em qualquer base), você usa todos os algarismos nas casas anteriores antes de avançar de casa.

Então aí no código quando eu faço (col >> 3), estou pegando o resultado da divisão de col por 8. E quando eu faço (col & 7), estou pegando o resto da divisão de col por 8 (ou seja, col % 8).

Certamente o compilador já faz isso automaticamente, mas é uma curiosidade bem interessante, né?

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {   
        constexpr unsigned char zero = 0;

        const size_t num_row = matrix.size();
        const size_t num_col = matrix[zero].size();
      
        vector<unsigned char> clearCol(25,zero);
        
        for (auto row = zero; row < num_row; ++row) {
            bool clearRow = false;
            
            for (auto col = zero; col < num_col; ++col) {
                if (!(matrix[row][col])) {
                    clearRow = true;             
                    clearCol[col >> 3] |= (1 << (col & 7));     
                }               
            }
          
            if (clearRow) 
                for (auto&& n : matrix[row]) n = zero;
        }
        
        for (auto n = zero; n < 25; ++n) {
            if (!(clearCol[n])) continue;
            auto step = 1;
            
            for (auto i = zero; i < 8; ++i) {
              if (((step << i) & (clearCol[n])) == (step << i)) {
                auto col = (n << 3) + i;
            
                for (auto row = zero; row < num_row; ++row) 
                   matrix[row][col] = zero;
              }
            }
        }
    }
};?

@Giovanni não achei o link para o desafio agora na lateral, também não consegui configurar pra aparecer

@Bastter ah, blz. Valeu!

class Solution 
{
public:
    class vectorize_col
    {    
        struct iter
        {           
            int* ptr;
            int index;
            int col;
            int m;
            int n;
            std::vector<std::vector<int>>& matrix; 
                    
            iter(int pos, std::vector<std::vector<int>>& grid) : 
            ptr(&grid[0][pos]), index(0), col(pos), m(grid.size()), n(grid[0].size()), matrix(grid) {}
            
            iter(int* n, std::vector<std::vector<int>>& grid) : ptr(n), index{}, col{}, m{}, n{}, matrix{grid} {}
            
            ~iter() = default;
            iter(const iter& other) = default;
            iter(iter&& other) = default;
            
            Solution::vectorize_col::iter & operator=(const iter& other)
            {
                ptr = other.ptr;
                index = other.index;
                col = other.col;
                m = other.m;
                n = other.n;
                matrix = other.matrix;
                return *this;
            }
            
            Solution::vectorize_col::iter & operator=(iter&& other)
            {
                ptr = std::move(other.ptr);
                index = std::move(other.index);
                col = std::move(other.col);
                m = std::move(other.m);
                n = std::move(other.n);
                matrix = std::move(other.matrix);
                return *this;
            }
                   
            int& operator*()
            {
                return *ptr;
            }
            
            int* operator->()
            {
                return ptr;
            }
            
            iter& operator++()
            {
                ++index;
                if (index < m)
                    ptr = &(matrix[index][col]);
                else ptr = nullptr;
                return *this;
            }
            
            iter operator++(int)
            {
                auto temp = *this;
                ++(*this);
                return temp;
            }
            
            iter& operator+=(int inc)
            {
               index += inc;
               if (index < m)
                   ptr = &(matrix[index][col]);
               else ptr = nullptr;
               return *this;
            }
            
            friend iter operator+(iter fst, int sec)
            {
                return fst += sec;
            }
            
            friend bool operator==(const iter& a, const iter& b)
            {
                return a.ptr == b.ptr;
            }
            
            friend bool operator!=(const iter&a, const iter& b)
            {
                return a.ptr != b.ptr;
            }
        };
        
        iter col_iter;
        
        public:
        
        vectorize_col(std::vector<std::vector<int>>& grid, int pos) : col_iter(pos, grid) {}
        
        iter begin()
        {          
            return col_iter;
        }
        
        iter end()
        {
            return iter(nullptr, col_iter.matrix);
        }                 
    };
        
    auto setZeroes(vector<vector<int>>& matrix) 
    {
        
        auto nullify = [&] (const auto& pairs)
        {
            auto null_vector = [] (auto& v)
            {
                std::fill(v.begin(), v.end(), 0);               
            };
            
            std::for_each(pairs.begin(), pairs.end(), [&] (const auto& pos)
                          {
                              vectorize_col col(matrix, pos.second);
                              null_vector(matrix[pos.first]);
                              null_vector(col);
                          });        
        };
        
        auto find_zeroes = [] (const auto& v)
        {
            struct zeroes
            {
                std::vector<std::pair<int, int>> pairs{};
                
                auto operator()(int r, int c, int val)
                {
                    if (val == 0) 
                    {
                        std::pair<int, int> pos {r, c};
                        pairs.emplace_back(pos);
                    }
                }
            }; 
            
            zeroes values;
            
            std::for_each(v.begin(), v.end(), 
                          [&](auto& row)
                            {                                                          
                                const auto r = &row - &v[0];
                                std::for_each(row.begin(), row.end(), 
                                              [&](auto& val)
                                                {
                                                    const auto c = &val - &row[0];
                                                    values(r, c, val);
                                                });
                            });
            
            return values.pairs;
        };
        
        nullify(find_zeroes(matrix));      
    }
};