BastterCode monthly Junho - 15. 3Sum
comentada em 04/07/2023 16:05

Esse foi o primeiro desafio de nível médio que eu fiz, faz 3 meses. Eu tinha acabado de começar a aprender a programar, estava nos primeiros desafios daqui do site.

Na época eu consegui resolver, mas tive um desempenho bem ruim, segue o código que eu fiz na época:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int m = nums.size()/2 + 1, e = m;
        map<int,int> freq;
        set<vector<int>> t;
        vector<vector<int>> trip{};
        
        for (int i = 0; i < m; i++) {
            if (freq.count(nums[i])) freq[nums[i]]++;
            else freq[nums[i]] = 1;
            if (e < nums.size()) {
                if (freq.count(nums[e])) freq[nums[e]]++;
                else freq[nums[e]] = 1;
                e++;
            }
        }
        
        if (freq.size() == 1 && !(freq.count(0))) return trip;
        
        ::map<int,int>::iterator itm;
        ::map<int,int>::reverse_iterator ritm;
        
        for (ritm = freq.rbegin(); ritm != freq.rend(); ritm++) {
            for (itm = freq.begin(); itm != freq.end(); itm++) {
                if (itm->first != ritm->first || (itm->first == 0 && itm->second >= 3))                 {
                    int min = itm->first;
                    int max = ritm->first;
                    int dif = 0 - (min + max);
            
                    if (freq.count(dif)) {
                        vector<int> in {min, dif, max};
                        if (dif == min && itm->second > 1) {
                            sort(in.begin(), in.end());
                            t.insert(in);
                        }
                        else
                            if (dif == max && ritm->second > 1) {
                            sort(in.begin(), in.end());
                            t.insert(in);
                        }
                        else 
                            if (dif != min && dif != max) {
                            sort(in.begin(), in.end());
                            t.insert(in);
                        }                    
                    }
                }
            }
        }
        
        ::set<vector<int>>::iterator its;
        
        for (its = t.begin(); its != t.end(); its++) {
            trip.push_back(*its);
        }
        
        return trip;
    }
};?

Não me pergunte o que o código faz, pois eu tenho até preguiça de tentar entender kkkk

Segue o desempenho que eu tive na época:

Hoje eu tentei fazer de novo, sem olhar a solução antiga. Para poder comparar e ver meu progresso, se é que houve algum kkk

Segue o código que eu fiz hoje. Embora melhor que o do código anterior, o desempenho ainda tá bem ruim. Vou pensar mais ao longo do mês para fazer algo melhor. 

class Solution {
public:
    bool iSearch(vector<int>& container, unsigned short& low, unsigned short& high, const int& n) {
        while (low <= high) {
            
            if (container[low] > n || container[high] < n) break;
            
            if (container[high] == container[low]) {
                if (container[high] != n) return false;
                else return true;
            } 
            
            unsigned short mid = low + ((n - container[low]) * (double)((high - low)) / (container[high] - container[low]));            
             
            if (container[mid] == n) return true;
            
            if (container[mid] < n) low = mid + 1;
            else high = mid - 1;
        }
        
        return false;
    }
    
    unsigned getHashValue(const int& n1, const int& n2, const int& n3) {
        int great = n1 >= n2 ? n1 : n2;
        great = great >= n3 ? great : n3;
        
        int less = n1 < n2 ? n1 : n2;
        less = less < n3 ? less : n3;
        
        const unsigned mult = 100000;
        unsigned hash = mult*great + less;
        
        return hash;
    }
    
    bool checkHash(unordered_set<unsigned>& set, const int& n1, const int& n2, const int& n3) {
        unsigned hash = getHashValue(n1, n2, n3);
        
        if (set.count(hash)) return true;
        
        return false;
    }
    
    void insertHash(unordered_set<unsigned>& set, const int& n1, const int& n2, const int& n3) {
        unsigned hash = getHashValue(n1, n2, n3); 
        
        set.insert(hash);
    }
  
    vector<vector<int>> threeSum(vector<int>& nums) {        
        vector<vector<int>> answer{};
        unordered_set<unsigned> no_dup{};
        
        const unsigned short target = 0;
        const unsigned short last = nums.size() - 1;
            
        sort(nums.begin(), nums.end());
        
        if (nums[0] > 0 || nums[last] < 0) return answer;
        if (nums[0] == nums[last]) return {{0,0,0}};
      
        for (int i = 0; i < last; ++i) {
            const int n1 = nums[i];
            
            if (n1 > 0) break;
            
            for (int j = i + 1; j < last; ++j) {
                const int n2 = nums[j];                  
                const int n3 = target - n1 - n2;
                
                if (n3 < n2) break;                
                
                if (checkHash(no_dup, n1, n2, n3)) continue;
                
                unsigned short low = j + 1, high = last;                
                
                if (iSearch(nums, low, high, n3)) {
                    insertHash(no_dup, n1, n2, n3);
                    answer.push_back({n1, n2, n3});
                }
            }
        }
        
        return answer;
    }
};?

 

Em resumo, ele faz um sort dos números e depois percorre o vetor em dois loops, fixando dois números distintos em ordem e fazendo uma busca para o terceiro no resto do vetor. Como os elementos estão sortidos, é possível:

1- fazer a busca do terceiro elemento de forma eficiente;

2- quebrar o primeiro loop quando o primeiro elemento é maior que 0 (pois os outros dois elementos são maiores que o primeiro e, portanto, a soma não poderia ser 0 nesse caso;

3- quebrar o segundo loop quando o terceiro elemento seria menor que o segundo, pois nesse caso é impossível encontrar o terceiro elemento (já que o vetor é percorrido da ordem do menor para o maior e, portanto, o terceiro elemento teria que ser maior ou igual ao segundo).

Para evitar duplicadas, usei uma hash table. O negócio é que são 3 números, que podem aparecer em qualquer ordem, ou seja, em um total de 3! = 6 combinações.

Inicialmente, eu pensei em usar um set de vector<int>, em que as 6 combinações dos números seriam passadas como vetores. Mas aí teria que checar e inserir 6 elementos a cada loop e, além disso, sets não são muito eficientes para acesso e inserção de chaves.

Depois pensei em usar unordered_sets, que são mais eficientes e permitem acesso e inserção em tempo constante amortizado. Mas o C++ não permite por padrão fazer unordered_sets de vetores, eu teria que criar minha própria função hash, coisa que ainda não sei fazer e que não queria pesquisar agora.

Então pensei em usar unordered_sets de inteiros, usando uma função hash simples que multiplica os elementos por um fator tal que evita colisão entre triplas diferentes de elementos. Mas isso exigiria usar long long int, pois cada elemento pode assumir valores entre -10^5 e 10^5, inclusive, então para usar os três elementos somando na criação do hash, eu teria que multiplicar um por 10^6 e outro por 10^12, podendo gerar uma chave com valor de até 10^17. Eu fiz isso, funcionou, mas ficou muito lento.

Em seguida pensei o seguinte. como os 3 elementos somam um mesmo valor, isto é, 0, então, uma vez que eu fixe dois desses números, o terceiro está unicamente determinado. Eu só precisaria fixar sempre os mesmos dois números não importa qual combinação apareça entre os três. Para isso eu poderia fixar o maior e o menor dentre os três, já que, não importa a combinação entre eles, o maior e o menor sempre serão os mesmos. Daí eu poderia multiplicar apenas um dos dois por um fator tal que, somando com o outro, a chave resultante seria unicamente determinada.

Daí eu pensei assim, como a soma dos 3 elementos é 0, então o maior sempre será maior ou igual a 0 e o menor sempre será menor ou igual a 0. Logo, o fator de multiplicação não precisa ser 10^6, pode ser 10^5, já que a única forma de haver colisão multiplicando por 10^5 seria se o maior número fosse 10^5 e o menor fosse 1, o que é impossível. Sendo o fator de multiplicação 10^5 e o maior elemento também assumindo valor de até 10^5, então o maior número resultante seria 10^10, que cabe em um int normal.

Por último, eu testei a busca binária para achar o terceiro elemento, mas depois parei pra pensar que, como o vetor tem no máximo 3000 elementos e cada elemento pode assumir valores entre -10^5 e 10^5, então, em uma distribuição aleatória, é muito provável que haja várias repetições.

Portanto, resolvi testar uma busca interpolada, que faz interpolação linear dos elementos para poder "pular" para uma região de maior probabilidade de encontrar o elemento desejado (supondo que os elementos não tenham uma distribuição muito discrepante, muito aleatória, o que é improvável nesse caso). Ela de fato teve um desempenho um pouco melhor, mesmo com mais operações aritméticas.

Hoje eu passei algumas horas tentando melhorar o código anterior.

Depois de alguma análise, observei que eu não preciso da hash table. Isso porque a única forma de repetir uma tripla é se os três elementos forem iguais.

Uma vez que o vetor esteja sortido do menor para o maior, se eu colocar uma condição para pular o laço do loop se o primeiro elemento for igual ao anterior e uma segunda condição equivalente para o segundo elemento, então eu garanto que dois dos elementos da tripla nunca serão iguais. Consequentemente o terceiro também não será, já que ele é unicamente determinado pela soma constante.

Assim, essas duas condições substituem totalmente a hash table.

Além disso, se eu implementar minha busca interpolada de forma a me retornar o índice do terceiro elemento, então eu posso usar esse índice para limitar o loop do segundo elemento. Isso porque, se o segundo elemento for igual a um terceiro elemento analisado anteriormente, mantendo o primeiro elemento constante, então eu só troquei o segundo e o terceiro elementos na análise (são os mesmos números), então posso quebrar o loop e avançar o primeiro elemento.

Fora isso, implementei algumas outras melhorias, tanto de otimização quanto para organizar o código. Por exemplo, quebrar o loop quando o primeiro elemento for maior que 0 ou o último for menor que o segundo.

Atualmente, o meu consumo de memória já está excelente, no 1% a 2% melhores. Mas meu tempo, embora tenha caído para a metade, ainda está abaixo da média.

Eu sinceramente não sei mais como posso melhorar esse tempo mais, o programa já está muito otimizado e qualquer ganho agora seria marginal.

Não tenho como eliminar a estrutura de dados de resposta, não consigo imaginar mais nenhuma forma de "pular" números do vetor de entrada, enfim, não sei mais o que poderia justificar a diferença de tempo tão grande para as demais respostas. Parece bruxaria kkkk

Vou passar o resto do mês ruminando isso até descobrir o segredo.

Segue meu código atual:

class Search {
public:

    unsigned short iSearch(const vector<int>& container, unsigned short& low, unsigned short& high, const int& n) {
        while (low <= high) {
            
            if (container[low] > n || container[high] < n) return 0;
            
            if (container[high] == container[low]) {
                if (container[high] != n) return 0;
                else return high;
            } 
            
            unsigned short mid = low + ((n - container[low]) * (double)(high - low)) / (container[high] - container[low]);            
             
            if (container[mid] == n) return mid;
            
            if (container[mid] < n) low = mid + 1;
            else high = mid - 1;
        }
        
        return 0;
    }
};
class Solution {
private:

    Search s;

public:

    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> answer{};
        const short target = 0, last = nums.size() - 1;

        sort(nums.begin(), nums.end());

        if (nums[0] > target || nums[last] < target) return answer;
        if (nums[0] == nums[last]) {
            if (nums[last] == target) return {{0,0,0}};
            else return answer;
        }

        for (int i = 0; i < last - 1; ++i) {
            const int n1 = nums[i];

            if (i > 0 && n1 == nums[i - 1]) continue;
            if (n1 > 0) break;

            unsigned short end = last;

            for (int j = i + 1; j < end; ++j) {
                const int n2 = nums[j];
                if (j > i + 1 && n2 == nums[j - 1]) continue;

                const int n3 = target - n1 - n2;
                if (n3 < n2) break;

                unsigned short low = j + 1, high = end;
                high = s.iSearch(nums, low, high, n3);

                if (high) {
                    answer.push_back({n1, n2, n3});
                    end = high;
                }
            }
        }

        return answer;
    }
};?

Ver mais

Eu disse ali em cima:

"Por último, eu testei a busca binária para achar o terceiro elemento, mas depois parei pra pensar que, como o vetor tem no máximo 3000 elementos e cada elemento pode assumir valores entre -10^5 e 10^5, então, em uma distribuição aleatória, é muito provável que haja várias repetições."

Na verdade, é o contrário. Há repetição quando poucos valores devem ser distribuídos em muitos elementos. De qualquer forma, na prática a busca interpolada de fato se mostrou mais eficiente.

Desde então, ainda estou investigando novas estratégias para lidar com o problema.

Tentei implementar eu mesmo um algoritmo de sort. Por alguma razão, heapsort se mostrou um pouco mais eficiente que o sort padrão da C++ STL. Eu esperava o oposto, que meu sort fosse pior. Mesmo assim, a diferença foi muito pequena e pode ser a variação normal da VM do leetcode.

Agora estou pensando em estratégias em três fronts: 1- aproveitar o sort/construção do heap para implementar alguma melhoria que exija a passagem pelos elementos do vetor; 2- criar uma solução recursiva, para ver se ganho algum insight novo que possa traduzir em um algoritmo iterado mais eficiente; e 3 - tentar eliminar o sort totalmente - o que só faz sentido se eu descobrir uma forma de pesquisa em O(1)  ou no máximo O(log n) que pode ser implementada num array não sortido. Estou pensando em um direct access array, mas ele exige O(m) para ser criado, em que m é o intervalo de valores dos elementos do vetor, ou seja, várias vezes maior que n, o tamanho do vetor.

A meta é conseguir melhorar o código até o fim do mês para ficar pelo menos entre os 50% melhores. Mas o trabalho apertou até lá, então não sei se conseguirei tempo para isso.

Depois de muita pirueta, muito estudo e muito pensar sobre o assunto, consegui finalmente obter um desempenho entre os 50% melhores. Entre os 48% melhores na verdade (yay!), no tempo, e entre os 1% melhores na memória.

A verdade é que eu esgotei meu conhecimento e minha criatividade com essa questão. Pelo menos por enquanto, não consigo nem imaginar onde posso melhorar o código.

Confesso que tô até ansioso para virar o mês e eu conferir os códigos mais eficientes. Não sei que bruxaria a galera fez.

O mais surpreendente é serem tantos, não é tipo um ou outro. É metade das soluções aceitas. O que me mostra que deve ter um jeito *certo* de fazer que eu simplesmente não consegui pegar, mas que provavelmente vou pensar "a-há!" quando vir. Sábado eu vejo

O código abaixo conseguiu 234ms de tempo e 23,9MB de memória.

Como dá pra ver, tem várias funções desnecessárias (tipo, somar uma unidade) e até variáveis constantes (calculadas em compile-time) que representam números como 0 ou 1. Isso foi eu atirando pra todo o lado kkkk

static constexpr char zero = 0;
static constexpr char one = 1;

class Algorithms {
private: 
    
    void swapElements(vector<int>& container, const short& first, const short& second) {
        const int temp = container[first];
        
        container[first] = container[second];
        container[second] = temp;
    }  
    
    void buildHeap(vector<int>& container, const short& n) {       
        for (short i = oneLess((n >> one)); i >= zero; dec(i))
            heapify(container, n, i);
    }
  
    constexpr short lft(const short& head) {
      return oneMore((head << one));
    }
  
    constexpr short rgt(const short& head) {
      return oneMore(lft(head));
    }
    
    void heapify(vector<int>& container, const short& n, const short& node) {
        short greater = node, head = -one;
        
        while (greater != head) {
            head = greater;
          
            const short left = lft(head), right = rgt(head);
            
            if (left < n && container[left] > container[greater]) 
                greater = left;
            if (right < n && container[right] > container[greater]) 
                greater = right;
             
                swapElements(container, head, greater);
        }
    }    
                   
public:
  
    Algorithms(vector<int>& container) {
        heapSort(container);
    }
  
     constexpr short oneMore(const short& n) {
      return n + one;
    }
  
    constexpr short oneLess(const short& n) {
      return n - one;
    }

    constexpr void inc(short& n) {
      ++n;
    }
  
    constexpr void dec(short& n) {
      --n;
    }
      
    const bool iSearch(const vector<int>& container, const short& base, short& high, const int& n) {
        short low = base;
      
        while (low <= high) {           
            if (container[low] > n || container[high] < n) 
                return zero;
            
            if (container[high] == container[low]) {
                if (container[high] != n) 
                    return zero;
                else {
                    high = low;
                    return one;
                } 
            } 
            
            short mid = low + ((n - container[low]) * (double)(high - low)) / (container[high] - container[low]);            
             
            if (container[mid] == n) {
                high = mid;
                return one;
            }
            
            if (container[mid] < n) 
                low = oneMore(mid);
            else 
                high = oneLess(mid);
        }
        
        return zero;
    }      
           
    void heapSort(vector<int>& container) {
        const short n = container.size();
        
        buildHeap(container, n);
        
        for (short i = oneLess(n); i >= zero; dec(i)) {
            swapElements(container, zero, i);
            
            heapify(container, i, zero);
        }
    }    
};
class Solution {  
public:   

    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> answer{};
        
        Algorithms alg(nums);
        
        static constexpr char target = zero;
        const short last = alg.oneLess(nums.size());
        const int least = -(nums[last] + nums[alg.oneLess(last)]);
        
        if (nums[zero] > target || nums[last] < target) 
            return answer;
      
        if (nums[zero] == nums[last]) {
            if (nums[last] != target) 
                return answer;
            else 
                return {{zero,zero,zero}};
        }
        
        for (short i = zero; i < alg.oneLess(last); alg.inc(i)) {
            const int n1 = nums[i];
            
            if (n1 < least) 
                continue;
            if (i > zero && n1 == nums[alg.oneLess(i)]) 
                continue;
            if (n1 > target) 
                break;
            
            short end = last;

            for (short j = alg.oneMore(i); j < end; alg.inc(j)) {
                const int n2 = nums[j];
                
                if (j > alg.oneMore(i) && n2 == nums[alg.oneLess(j)])
                    continue;
                
                const int n3 = target - (n1 + n2);
                
                if (n3 > nums[end]) 
                    continue;
                if (n3 < n2) 
                    break;                
                
                if (alg.iSearch(nums, alg.oneMore(j), end, n3)) 
                    answer.push_back({n1, n2, n3});                   
            }
        }

        return answer;
    }
};?

Hoje finalmente tive tempo de conferir algumas soluções mais eficientes que constam lá no leetcode para C++.

Nas soluções que vi, de fato há um tema em comum. Em resumo, em vez de fazer um sort de todos os itens de nums, a galera primeiro descobriu o maior e menor valores válidos, ou seja, os que estão dentro do intervalo entre -20 mil e +20 mil. Valores fora desse intervalo não são válidos porque não há dois números no intervalo da questão (-10 mil a +10 mil, inclusive dos dois lados) que, somados a um número fora desse intervalo, resulte em 0.

Depois, criaram um direct access array para verificar quais números desse intervalo efetivamente estão em nums, bem como a quantidade de cada um.

De posse dessa informação é que foi implementado um sort, que aí poderia ser em O(n) e não em O(nlogn) como geralmente é o caso para sorts em geral. Isso porque o direct access array funciona como estrutura intermediária que me informa quais elementos existem em nums, o que me permite "reposicioná-los" em ordem crescente em nums.

Vale dizer que o n aí é o tamanho do intervalo (que é o tamanho do direct access array), que é bem maior que o número de elementos em nums. Além disso, é preciso percorrer nums uma vez para construir o array para só então percorrer o array para "reconstruir" nums.

Como o intervalo de análise é no máximo de 40001 (-20 mil a 20 mil), enquanto nums tem size de 3000, então o intervalo de análise equivale a até 13,3n (n como tamanho de nums). Isso mais 1n para construir o array, dá 14n. Enquanto um sort de nlogn, para n <= 3000, seria de 11,5n (log(2)3000 = 11,5).

Ou seja, a vantagem desse método de sort não é realmente a redução da complexidade, mas o fato de que eu não apenas fiz o sort, como também contei quantos elementos de cada número tem em nums e armazenei essa informação em um array que me permite recuperá-la em O(1).

Isso significa que mais pra frente eu não preciso fazer um search pelo terceiro elemento da tripla, posso recuperar essa informação mais rapidamente. Mesmo um search eficiente de O(loglogn), como é o interpolated search (para números distribuídos uniformemente), ainda é bem pior que uma "pesquisa" em O(1). Mesmo considerando que o espaço de análise era reduzido a cada iteração do segundo elemento (para um mesmo primeiro elemento).

A partir daí, basta aplicar todas as técnicas de otimização que eu já tinha aplicado, para interromper ou continuar o programa quando os valores são inadequados e pronto, código mais eficiente.

Enfim, uma técnica realmente engenhosa e mais eficiente.

Eu vi várias soluções aplicando o mesmo algoritmo. Selecionei uma que também usa outras técnicas interessantes, como lambda expressions e funções que eu não conhecia da STD, para estudo futuro.

P.S.: uma outra vantagem dessa técnica é que, no sort de nums, eu elimino as repetições de cada número (já que elas já foram contadas no array e não são mais necessárias). Isso significa um vetor menor para passar na última parte do algoritmo, que tem complexidade O(n^2) e, portanto, sofre um impacto muito grande para cada pequeno aumento do n. Eu tinha feito uns workarounds, uns continues, para evitar passar por muitas repetições, mas o método aqui é bem melhor.

class Solution {
   public:
    std::vector<std::vector<int>> threeSum( std::vector<int>& nums ) {
        
        if ( std::all_of( nums.begin(), nums.end(), [&]( const int i ) { return i == 0; } ) && nums.size() > 2 ) {
            return {{0,0,0}};
        }
        if ( nums.size() < 3 )
             return {};
        
        int min = 200000, max = -200000;
        // if any values in nums is greater or less than 200000 AND -200000, then set min and max to them
        std::for_each( nums.begin(), nums.end(), [&]( const int i ) {
            min = std::min( min, i );
            max = std::max( max, i );
        } );
        // range is positive of min
        const int range = -min;
        // size of char store is distance between i and max + 1
        const size_t size = static_cast<size_t>( max - min + 1 );
        std::vector<char> store( size, 0 );
        // count up to 3 how many times a number is included in nums
        // by placing in the index calculated from adding the number to range variable which is negative of min
        for ( int i = 0; i < nums.size(); i++ )
            if ( store[nums[i] + range] < 3 )
                store[nums[i] + range]++;
        
        int len = 0;  // counts how many unique numbers are in nums
        for ( int i = 0, j = 0; i < size; i++ ) {
            if ( store[i] > 0 ) {
                // for the amount of unique numbers in nums, replace the first elements in nums
                // with the unique numbers in ascending order via deducing it through subtracting
                // range from index where it is found
                nums[j++] = i - range;
                len++;
            }
        }
        std::vector<int>& unique = nums;
        auto f = nums.begin();
        auto b = std::next( nums.begin(), len - 1 );
        if ( ( *f >= 0 && *b >= 0 ) || ( *f <= 0 && *b <= 0 ) ) {
            return {};
        }
        std::vector<std::vector<int>> ans;
        while ( *b >= 0 ) {
            while ( *f <= 0 ) {
                int needed = -( *f + *b );
                if ( needed < *f ) {
                    break;
                }
                if ( needed > *b ) {
                    ++f;
                    continue;
                }
                if ( ( ( needed == *f || needed == *b ) && store[needed + range] == 1 ) ||
                     ( ( needed == *f && needed == *b ) && store[needed + range] == 2 ) ) {
                    ++f;
                    continue;
                }
                if ( store[needed + range] ) {
                    ans.push_back( { *f, needed, *b } );
                    ++f;
                }
                else {
                    ++f;
                    continue;
                }
            }
            --b;
            f = nums.begin();
        }
        return ans;
    }
};?