Soma Máxima de Subarray (Questão 53)

O desafio consiste em encontrar a maior soma possível entre todos os subarrays contínuos de um array de inteiros. O foco aqui é garantir eficiência em termos de tempo, percorrendo o array apenas uma vez.

class Solution {
    public int maxSubArray(int[] elementos) {
        int somaGlobal = elementos[0];
        int somaLocal = 0;
        
        for (int item : elementos) {
            somaLocal += item;
            
            // Atualiza o máximo global antes de resetar o acumulador 
            // para lidar corretamente com arrays compostos apenas por números negativos.
            if (somaLocal > somaGlobal) {
                somaGlobal = somaLocal;
            }
            
            if (somaLocal < 0) {
                somaLocal = 0;
            }
        }
        return somaGlobal;
    }
}

Lógica Aplicada: Utilizamos uma variação do algoritmo de Kadane. A estratégia principal é descartar somas acumuladas que se tornam negativas, pois elas reduziriam o potencial de soma dos elementos subsequentes. A ordem da comparação garante que o maior valor individual seja retornado mesmo que todos os números sejam negativos.

Mesclagem de Intervalos (Questão 56)

Dada uma coleção de intervalos, o objetivo é combinar aqueles que se sobrepõem em um único intervalo contínuo.

class Solution {
    public int[][] merge(int[][] intervalos) {
        if (intervalos.length <= 1) return intervalos;

        // Ordenação baseada no ponto inicial de cada intervalo
        Arrays.sort(intervalos, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> listaMesclada = new ArrayList<>();
        int[] intervaloAtual = intervalos[0];
        listaMesclada.add(intervaloAtual);

        for (int[] proximo : intervalos) {
            int fimAtual = intervaloAtual[1];
            int inicioProximo = proximo[0];
            int fimProximo = proximo[1];

            if (inicioProximo <= fimAtual) {
                // Existe sobreposição, expande o fim do intervalo atual
                intervaloAtual[1] = Math.max(fimAtual, fimProximo);
            } else {
                // Sem sobreposição, move para o próximo intervalo
                intervaloAtual = proximo;
                listaMesclada.add(intervaloAtual);
            }
        }

        return listaMesclada.toArray(new int[listaMesclada.size()][]);
    }
}

Lógica Aplicada: O pré-requisito crucial é a ordenação. Uma vez ordenados pelo início, podemos comparar o fim do intervalo atual com o início do próximo. Se houver intersecção, fundimos os dois mantendo o maior valor de término.

Rotação de Array (Questão 189)

Este problema solicita o deslocamento dos elementos de um array k posições para a direita.

class Solution {
    public void rotate(int[] dados, int k) {
        int n = dados.length;
        k = k % n; // Ajuste para rotações maiores que o tamanho do array
        
        int[] espelho = new int[n];
        for (int i = 0; i < n; i++) {
            int novaPosicao = (i + k) % n;
            espelho[novaPosicao] = dados[i];
        }
        
        System.arraycopy(espelho, 0, dados, 0, n);
    }
}

Lógica Aplicada: Utilizamos o operador de módulo para mapear os novos índices. A criação de um array auxiliar facilita a transferência direta, evitando a perda de dados durante deslocamentos sequenciais complexos.

Produto do Array Exceto o Próprio Elemento (Questão 238)

O requisito é gerar um novo array onde cada posição i contenha o produto de todos os números do array original, exceto o valor presente na posição i, sem utilizar a operação de divisão.

class Solution {
    public int[] productExceptSelf(int[] entrada) {
        int tamanho = entrada.length;
        int[] resultado = new int[tamanho];
        
        // Passo 1: Calcular produtos à esquerda
        resultado[0] = 1;
        for (int i = 1; i < tamanho; i++) {
            resultado[i] = resultado[i - 1] * entrada[i - 1];
        }
        
        // Passo 2: Calcular produtos à direita e multiplicar pelo resultado atual
        int fatorDireita = 1;
        for (int i = tamanho - 1; i >= 0; i--) {
            resultado[i] = resultado[i] * fatorDireita;
            fatorDireita *= entrada[i];
        }
        
        return resultado;
    }
}

Lógica Aplicada: Dividimos o problema em duas passagesn. Na primeira, armazenamos o produto acumulado de todos os itens à esquerda de cada índice. Na segunda, percorermos de trás para frente multiplicando pelo produto acumulado à direita, otimizando o espaço para O(1) adicional além do array de saída.

Primeiro Inteiro Positivo Ausente (Questão 41)

O objetivo é encontrar o menor número inteiro positivo (maior que zero) que não está presente em um array não ordenado, respeitando o tempo O(n) e espaço constante.

class Solution {
    public int firstMissingPositive(int[] valores) {
        int n = valores.length;

        // Normalização: substituir valores irrelevantes
        for (int i = 0; i < n; i++) {
            if (valores[i] <= 0 || valores[i] > n) {
                valores[i] = n + 1;
            }
        }

        // Usar o array como uma Hash Map in-place através de sinalização negativa
        for (int i = 0; i < n; i++) {
            int num = Math.abs(valores[i]);
            if (num <= n) {
                int indice = num - 1;
                if (valores[indice] > 0) {
                    valores[indice] = -valores[indice];
                }
            }
        }

        // O primeiro índice com valor positivo indica o número ausente
        for (int i = 0; i < n; i++) {
            if (valores[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }
}

Lógica Aplicada: Como o primeiro positivo ausente deve estar entre 1 e n+1, usamos os próprios índices do array para marcar a presença de números. Convertemos os valores presentes em negativos nos índices correspondentes. O primeiro índice que permanecer positivo revela a ausência.