Este artigo explora três problemas desafiadores frequentemente encontrados em entrevistas técnicas, abordando suas soluções através de algoritmos fundamentais: Programação Dinâmica, Abordagem com Pilha e Busca Binária.

Problema 1: Distância de Edição (LeetCode 72, Difícil)

Análise do Problema

Dadas duas strings, word1 e word2, determine o número mínimo de operações (inserir, deletar ou substituir um caractere) necessárias para transformar word1 em word2.

• Exemplo 1: word1 = "horse", word2 = "ros". Saída: 3 (horse → rorse → rose → ros).
• Exemplo 2: word1 = "intention", word2 = "execution". Saída: 5.
• Casos base: "", "" → 0; "a", "" → 1.

Estratégia de Solução (Programação Dinâmica)

Utilizamos programação dinâmica para calcular o número mínimo de operações para substrings. A transição de estado considera as três operações permitidas:

1. Definição do DP: dp[i][j] representa o número mínimo de operações para transformar os primeiros i caracteres de word1 nos primeiros j caracteres de word2.
2. Casos Base:
   • dp[i][0] = i: Remover todos os i caracteres de word1.
   • dp[0][j] = j: Inserir todos os j caracteres de word2 em uma string vazia.
3. Transição de Estado:
   • Se word1[i-1] == word2[j-1]: Nenhum custo adicional, dp[i][j] = dp[i-1][j-1].
   • Se forem diferentes: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1. Isso representa o custo mínimo entre substituir, deletar (de word1) ou inserir (em word1).

Código de Exemplo (Otimização de Espaço)

def calcular_distancia_edicao(palavra1: str, palavra2: str) -> int:
    m, n = len(palavra1), len(palavra2)
    # Otimização para O(n) de espaço usando um array 1D
    dp = [0] * (n + 1)

    # Inicializa a primeira linha (palavra1 vazia)
    for j in range(n + 1):
        dp[j] = j

    for i in range(1, m + 1):
        valor_anterior_diagonal = dp[0]  # Armazena dp[i-1][0]
        dp[0] = i  # Atualiza dp[i][0]
        for j in range(1, n + 1):
            valor_temporario = dp[j]  # Armazena dp[i-1][j] antes da atualização
            if palavra1[i-1] == palavra2[j-1]:
                dp[j] = valor_anterior_diagonal # Custo de dp[i-1][j-1]
            else:
                # Custo mínimo entre substituição (valor_anterior_diagonal),
                # deleção (dp[j]), e inserção (dp[j-1])
                dp[j] = min(valor_anterior_diagonal, dp[j], dp[j-1]) + 1
            valor_anterior_diagonal = valor_temporario # Prepara para a próxima iteração j

    return dp[n]

# Testes
print("Distância de Edição 1:", calcular_distancia_edicao("horse", "ros"))
print("Distância de Edição 2:", calcular_distancia_edicao("intention", "execution"))
print("Distância de Edição 3:", calcular_distancia_edicao("", ""))

Análise do Código

• Complexidade de Espaço: Otimizada para O(n) usando um array unidimensional.
• Complexidade de Tempo: O(mn) devido aos loops aninhados, que é a complexidade ótima.
• Aplicações: Verificação ortográfica, alinhamento de sequências de DNA.

Problema 2: Maior Retângulo (LeetCode 85, Difícil)

Análise do Problema

Dado uma matriz binária (0s e 1s), encontre a área do maior retângulo formado apenas por 1s.

• Exemplo: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]. Saída: 6.
• Outros exemplos: [["1","1","1"],["1","1","1"],["1","1","1"]] → 9; [["0"]] → 0.

Estratégia de Solução (Transformação + Pilha Monótona)

A estratégia envolve transformar o problema 2D em um problema 1D de encontrar a maior área em um histograma, linha por linha. A solução para o histograma utiliza uma pilha monótona.

1. Construção do Histograma por Linha: Para cada linha, criamos um array heights onde heights[col] representa a altura contínua de 1s acima dessa célula (incluindo a célula atual). Se a célula atual for 0, a altura é resetada para 0.
2. Pilha Monótona para Área Máxima: Para cada array heights gerado, usamos uma pilha para encontrar, para cada barra, as barras vizinhas mais baixas à esquerda e à direita. Isso permite calcular a área máxima possível com essa barra como altura.

Código de Exemplo

def maior_retangulo(matriz) -> int:
    if not matriz or not matriz[0]:
        return 0

    linhas, colunas = len(matriz), len(matriz[0])
    alturas = [0] * colunas
    max_area = 0

    def area_maxima_histograma(alturas_hist):
        """ Resolve o problema do maior retângulo em histograma (LeetCode 84) """
        # Adiciona sentinelas 0 nas extremidades para simplificar a lógica da pilha
        alturas_hist = [0] + alturas_hist + [0]
        pilha = []
        area = 0
        for indice_atual in range(len(alturas_hist)):
            # Enquanto a pilha não estiver vazia e a altura atual for menor que o topo da pilha
            while pilha and alturas_hist[indice_atual] < alturas_hist[pilha[-1]]:
                altura_barra = alturas_hist[pilha.pop()]
                largura_barra = indice_atual - pilha[-1] - 1
                area = max(area, altura_barra * largura_barra)
            pilha.append(indice_atual)
        return area

    # Processa cada linha
    for linha in range(linhas):
        # Atualiza as alturas para a linha atual
        for col in range(colunas):
            alturas[col] = alturas[col] + 1 if matriz[linha][col] == "1" else 0
        
        # Calcula a área máxima para o histograma desta linha
        area_atual = area_maxima_histograma(alturas)
        max_area = max(max_area, area_atual)

    return max_area

# Testes
matriz1 = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]
print("Maior Retângulo 1:", maior_retangulo(matriz1))

matriz2 = [["1","1","1"],["1","1","1"],["1","1","1"]]
print("Maior Retângulo 2:", maior_retangulo(matriz2))

Análise do Código

• Redução de Dimensionalidade: Transforma um problema 2D em múltiplos problemas 1D.
• Complexidade de Tempo: O(linhas * colunas), pois cada célula é visitada um número constante de vezes.
• Complexidade de Espaço: O(colunas) para armazenar as alturas e a pilha.

Problema 3: Mediana de Dois Arrays Ordenados (LeetCode 4, Difícil)

Análise do Problema

Dados dois arrays ordenados nums1 e nums2, encontre a mediana dos dois arrays combinados. O requisito é que a complexidade de tempo seja O(log(min(m, n))).

• Exemplo 1: nums1 = [1,3], nums2 = [2]. Saída: 2.0.
• Exemplo 2: nums1 = [1,2], nums2 = [3,4]. Saída: 2.5.
• Exemplo 3: nums1 = [0,0], nums2 = [0,0]. Saída: 0.0.

Estratégia de Solução (Busca Binária + Partição)

A chave é realizar uma busca binária em um dos arrays (preferencialmente o menor) para encontrar uma partição ideal. A partição divide os elementos em duas metades (esquerda e direita) de tal forma que todos os elementos na metade esquerda sejam menores ou iguais a todos os elementos na metade direita.

1. Garantir Array Menor para Busca: Se nums1 for maior que nums2, troque-os para garantir que a busca binária seja feita no array de tamanho menor.
2. Busca Binária da Partição:
   • A busca binária é realizada no índice de partição i de nums1 (variando de 0 a m).
   • O índice de partição j de nums2 é determinado por j = (m + n + 1) // 2 - i, onde (m + n + 1) // 2 é o número total de elementos na metade esquerda combinada.
   • A partição é válida se nums1[i-1] <= nums2[j] e nums2[j-1] <= nums1[i]. Ajustamos a busca binária (left/right) com base nessa condição.
3. Cálculo da Mediana:
   • Com a partição correta, a mediana é:
     • Se o total de elementos for ímpar: o maior elemento da metade esquerda (max(nums1[i-1], nums2[j-1])).
     • Se o total de elementos for par: a média do maior elemento da metade esquerda e do menor elemento da metade direita ((max(left) + min(right)) / 2).
   • Tratamos casos de borda (arrays vazios) usando -inf e +inf.

Código de Exemplo

import math

def encontrar_mediana_arrays_ordenados(nums1, nums2) -> float:
    # Garante que nums1 seja o array menor
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    ponta_esquerda, ponta_direita = 0, m
    total_elementos_esquerda = (m + n + 1) // 2 # Número total de elementos na metade esquerda

    while ponta_esquerda <= ponta_direita:
        # Calcula os índices de partição para ambos os arrays
        particao_nums1 = (ponta_esquerda + ponta_direita) // 2
        particao_nums2 = total_elementos_esquerda - particao_nums1

        # Obtém os elementos de fronteira das partições, tratando casos de borda
        max_esquerda_nums1 = nums1[particao_nums1 - 1] if particao_nums1 > 0 else -math.inf
        min_direita_nums1 = nums1[particao_nums1] if particao_nums1 < m else math.inf

        max_esquerda_nums2 = nums2[particao_nums2 - 1] if particao_nums2 > 0 else -math.inf
        min_direita_nums2 = nums2[particao_nums2] if particao_nums2 < n else math.inf

        # Verifica se a partição é válida
        if max_esquerda_nums1 <= min_direita_nums2 and max_esquerda_nums2 <= min_direita_nums1:
            # Partição válida encontrada, calcula a mediana
            max_geral_esquerda = max(max_esquerda_nums1, max_esquerda_nums2)

            if (m + n) % 2 == 1: # Total ímpar de elementos
                return float(max_geral_esquerda)
            else: # Total par de elementos
                min_geral_direita = min(min_direita_nums1, min_direita_nums2)
                return (max_geral_esquerda + min_geral_direita) / 2.0
        elif max_esquerda_nums1 > min_direita_nums2:
            # Necessário mover a partição de nums1 para a esquerda
            ponta_direita = particao_nums1 - 1
        else:
            # Necessário mover a partição de nums1 para a direita
            ponta_esquerda = particao_nums1 + 1

    # Caso não encontrado (não deve ocorrer para arrays válidos)
    raise ValueError("Entrada inválida")


# Testes
print("Mediana 1:", encontrar_mediana_arrays_ordenados([1,3], [2]))
print("Mediana 2:", encontrar_mediana_arrays_ordenados([1,2], [3,4]))
print("Mediana 3:", encontrar_mediana_arrays_ordenados([0,0], [0,0]))

Análise do Código

• Otimização de Tempo: O(log(min(m, n))) devido à busca binária no array menor.
• Estratégia de Partição: Abordagem unificada para casos ímpares e pares de contagem total de elementos.
• Robustez de Borda: Uso de -inf e +inf para lidar com partições nas extremidades dos arrays.

Estes três problemas são exemplos de desafios clássicos e de alto valor prático em entrevistas técnicas. Eles cobrem direções algorítmicas chave: programação dinâmica (distância de edição), transformação de problemas com pilhas (maior retângulo) e busca binária (mediana). A capacidade de transformar probleams e aplicar estruturas de dados eficientes é crucial para a otimização e modelagem de soluções.