Busca Binária

A busca binária é um algoritmo fundamental para localizar elementos em estruturas ordenadas. O sucesso da implementação depende estritamente da definição dos limites do intervalo de busca. Podemos adotar a abordagem de intervalo totalmente fechado [inicio, fim] ou semiaberto [inicio, fim). Manter a consistência na escolha do intervalo e no cálculo do ponto médio previne erros clássicos de limite.

class Solution {
public:
    int search(std::vector<int>& nums, int alvo) {
        int inicio = 0;
        int fim = static_cast<int>(nums.size()) - 1;

        while (inicio <= fim) {
            int meio = inicio + (fim - inicio) / 2;
            if (nums[meio] == alvo) {
                return meio;
            } else if (nums[meio] > alvo) {
                fim = meio - 1;
            } else {
                inicio = meio + 1;
            }
        }
        return -1;
    }
};

Remoção de Elementos

Para eliminar ocorrências de um valor específico em um array sem alocar memória extra, a técnica de dois ponteiros é ideal. Um ponteiro percorre a estrutura original, enquanto o outro rastreia a posição de inserção dos elementos válidos. Isso resulta em complexidade temporal O(n) e espacial O(1).

class Solution {
public:
    int removeElement(std::vector<int>& nums, int valorRemover) {
        int posicaoEscrita = 0;
        for (int posicaoLeitura = 0; posicaoLeitura < nums.size(); ++posicaoLeitura) {
            if (nums[posicaoLeitura] != valorRemover) {
                nums[posicaoEscrita] = nums[posicaoLeitura];
                posicaoEscrita++;
            }
        }
        return posicaoEscrita;
    }
};

Quadrados de Array Ordenado

Elevar ao quadrado os elementos de um array ordenado que contém números negativos quebra a ordenação original. Em vez de recalcular e reordenar (o que custaria O(n log n)), podemos explorar o fato de que os maiores valores absolutos estão nas extremidades. Utilizando dois ponteiros nas pontas e preenchendo um array de resultado de trás para frente, alcançamos complexidade O(n).

class Solution {
public:
    std::vector<int> sortedSquares(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> resultado(n);
        int ponteiroEsq = 0;
        int ponteiroDir = n - 1;
        int idxResultado = n - 1;

        while (ponteiroEsq <= ponteiroDir) {
            int quadradoEsq = nums[ponteiroEsq] * nums[ponteiroEsq];
            int quadradoDir = nums[ponteiroDir] * nums[ponteiroDir];

            if (quadradoEsq > quadradoDir) {
                resultado[idxResultado] = quadradoEsq;
                ponteiroEsq++;
            } else {
                resultado[idxResultado] = quadradoDir;
                ponteiroDir--;
            }
            idxResultado--;
        }
        return resultado;
    }
};

Subarray de Soma Mínima

Para encontrar o menor subarray contíguo cuja soma atinja ou ultrapasse um valor meta, a técnica de janela deslizante (sliding window) é a mais eficiente. Expandimos a janela movendo o ponteiro direito e a contraímos movendo o ponteiro esquerdo sempre que a condição de soma é satisfeita, garantindo uma execução em tempo linear.

class Solution {
public:
    int minSubArrayLen(int meta, std::vector<int>& nums) {
        int tamanhoMinimo = nums.size() + 1;
        int somaAtual = 0;
        int inicioJanela = 0;

        for (int fimJanela = 0; fimJanela < nums.size(); ++fimJanela) {
            somaAtual += nums[fimJanela];

            while (somaAtual >= meta) {
                tamanhoMinimo = std::min(tamanhoMinimo, fimJanela - inicioJanela + 1);
                somaAtual -= nums[inicioJanela];
                inicioJanela++;
            }
        }
        return tamanhoMinimo == nums.size() + 1 ? 0 : tamanhoMinimo;
    }
};

Matriz Espiral

A geração de uma matriz preenchida em ordem espiral exige um controle rigoroso dos limites em cada iteração. Aplicando o conceito de invariante de loop, processsamos as bordas superior, direita, inferior e esquerda de forma consistente, ajustando os limites iniciais a cada camada completa para evitar sobreposições.

class Solution {
public:
    std::vector<std::vector<int>> generateMatrix(int n) {
        std::vector<std::vector<int>> matriz(n, std::vector<int>(n, 0));
        int limiteX = 0, limiteY = 0;
        int camadas = n / 2;
        int contador = 1;

        while (camadas--) {
            int linha = limiteX;
            int coluna = limiteY;

            for (; coluna < n - limiteY - 1; ++coluna) matriz[linha][coluna] = contador++;
            for (; linha < n - limiteX - 1; ++linha) matriz[linha][coluna] = contador++;
            for (; coluna > limiteY; --coluna) matriz[linha][coluna] = contador++;
            for (; linha > limiteX; --linha) matriz[linha][coluna] = contador++;

            limiteX++;
            limiteY++;
        }

        if (n % 2 != 0) {
            matriz[n / 2][n / 2] = n * n;
        }
        return matriz;
    }
};