Sliding Window

O problema que faz a técnica nascer

Comece pelo pedido mais simples possível: dado o array [2, 3, 4, 5, 6, 7], qual é a maior soma de 3 elementos seguidos?

A solução óbvia é testar todas as janelas de tamanho 3:

def maior_soma_forca_bruta(nums, k):
    melhor = float("-inf")
    for i in range(len(nums) - k + 1):
        soma = 0
        for j in range(i, i + k):   # refaz a soma inteira, toda vez
            soma += nums[j]
        melhor = max(melhor, soma)
    return melhor

Funciona. E desperdiça um absurdo de trabalho. Olhe as duas primeiras janelas:

[2, 3, 4]  5, 6, 7      soma = 9
 2, [3, 4, 5]  6, 7     soma = 12

Elas compartilham o 3 e o 4. Você acabou de somar esses dois números e vai somá-los de novo. Com k = 3 são 2 somas jogadas fora por janela; com k = 100, são 99. O custo é (n - k + 1) * k, que para k proporcional a n vira O(n·k), ou seja, quadrático.

A pergunta que destrava a técnica é: se eu já sei a soma da janela anterior, quanto custa a próxima?

A intuição: o que entra e o que sai

Da primeira janela para a segunda, uma coisa saiu (o 2) e uma coisa entrou (o 5). Todo o resto ficou igual.

soma_nova = soma_velha - nums[esquerda] + nums[direita]
          =     9      -      2         +      5        = 12

Uma subtração e uma soma. Duas operações, não k. E o mais importante: esse custo não muda se k for 3, 100 ou 10.000.

Essa é a técnica inteira. O resto da página é aprender a reconhecer onde ela se aplica e como escrever o laço sem errar as bordas.

Rode os dois lado a lado no mesmo array. O contador da esquerda é a força bruta relendo a janela toda; o da direita é a janela mantendo a soma. Aumente o k para 6 e veja o que acontece com cada um.

Construindo a janela fixa

Quando o enunciado dá o tamanho (k = 3, "de 3 caracteres", "de tamanho k"), a janela tem tamanho travado: a cada passo entra um elemento pela direita e sai um pela esquerda.

O visualizador abaixo mostra exatamente isso, com o código acompanhando linha a linha. Rode uma vez inteiro e repare no painel de variáveis: a soma muda a cada passo, mas nenhum passo percorre a janela de novo. Depois edite o array e o k e veja que o número de operações não acompanha o k.

O laço tem uma sutileza que pega todo mundo na primeira vez: você precisa montar a primeira janela antes de começar a deslizar.

def maior_soma(nums, k):
    soma = sum(nums[:k])        # monta a primeira janela: k operações, uma vez só
    melhor = soma
    for direita in range(k, len(nums)):
        soma += nums[direita]           # entra o novo
        soma -= nums[direita - k]       # sai o que ficou para trás
        melhor = max(melhor, soma)
    return melhor

O índice direita - k é o que sai. Se direita está em 3 e k é 3, sai o índice 0. Erre isso por um e você tem uma janela de tamanho k + 1 sem perceber, com um resultado que parece quase certo.

Construindo a janela variável

Agora o caso mais comum em entrevista: o enunciado não dá o tamanho, ele dá uma condição, e pergunta qual é o maior (ou o menor) pedaço que a respeita.

"Qual o maior subarray com soma menor ou igual a 15?" Aqui o tamanho é a resposta, não a entrada.

A mecânica muda em um ponto só: a borda esquerda não anda junto com a direita. Ela só anda quando precisa.

• Cresça pela direita, sempre, incluindo nums[direita] no estado.
• Encolha pela esquerda, enquanto a janela estiver inválida, removendo nums[esquerda].
• Atualize a resposta quando a janela voltar a ser válida.

No visualizador abaixo a condição é soma <= k. Repare no comportamento que diferencia a janela variável: a esquerda fica parada por vários passos e depois anda várias casas de uma vez, quando a janela estoura.

Acompanhando à mão em [2, 3, 4, 5, 6, 7] com limite 15:

A resposta é 4, do passo 4. Note que depois do encolhimento a janela nunca mais alcançou esse tamanho, e é por isso que a resposta é atualizada a cada janela válida, não só no fim.

O padrão generalizado

Os dois casos são o mesmo template. Vale a pena decorar este esqueleto, porque ele resolve a maioria dos problemas de janela variável trocando só três pedaços:

def janela(nums):
    esquerda = 0
    estado = 0                       # 1. o que a janela guarda
    melhor = 0
    for direita in range(len(nums)):
        estado += nums[direita]      # 2. entra o elemento da direita
        while invalida(estado):      # 3. a condição do enunciado
            estado -= nums[esquerda] #    sai o elemento da esquerda
            esquerda += 1
        melhor = max(melhor, direita - esquerda + 1)   # 4. janela válida, atualiza
    return melhor

Os quatro encaixes:

1. O estado. Uma soma, uma contagem, um dicionário de frequências. É o que precisa ser atualizado em O(1) na entrada e na saída.
2. A entrada. Sempre acontece, sempre na direita.
3. A condição. É a tradução literal do enunciado. estado > k, len(vistos) > 2, zeros > 1.
4. A resposta. Para "a maior", atualize depois do while. Para "a menor", atualize dentro do while, porque é lá que a janela está apertada no limite.

Como reconhecer que é janela deslizante

Esta é a parte que mais economiza tempo numa prova. Existem pistas quase infalíveis no enunciado, e elas vêm em conjunto:

Se você ficou em dúvida entre os termos, vale a leitura de Subarray, Substring, Subsequence e Subset, que separa os quatro com exemplos.

Há também uma distinção fina que arruma a cabeça de vez:

No Two Pointers clássico (palíndromo, Two Sum em array ordenado), a decisão sai da comparação entre os dois extremos; o miolo não entra na conta. Na janela deslizante, o que decide se ela é válida é o agregado de todos os elementos de dentro, e é por isso que sempre existe um estado sendo mantido.

Complexidade

O argumento que garante o O(n) é curto e vale entender, porque ele aparece de novo em outras técnicas.

Olhando o código da janela variável, dá a impressão de ser O(n²): tem um while dentro de um for. Não é. Cada ponteiro só anda para a frente, e nenhum dos dois passa de n. A direita anda n vezes no total, e a esquerda anda no máximo n vezes somando todas as iterações do while. São no máximo 2n movimentos, ou seja, O(n).

Para a janela fixa, o número exato de janelas é n - k + 1, e o custo por janela é constante.

As armadilhas

Números negativos quebram a janela variável. Toda a lógica depende de "encolher pela esquerda só melhora". Com valores negativos, remover um elemento pode aumentar a soma, e uma janela maior pode ter soma menor que uma pequena. O while deixa de fazer sentido, porque encolher não garante voltar a ser válida. Nesse caso o caminho costuma ser Prefix Sum com hashmap.

Não ordene o array. É a armadilha mais cara desta técnica: ordenar destrói a adjacência, e subarray é definido por adjacência. Depois do sort, o pedaço que você achou não existe mais no array original. Ordenar é livre em problema de subset; é proibido em problema de subarray.

A resposta atualizada no lugar errado. Para "a maior janela válida", atualize depois do while. Para "a menor janela válida", atualize dentro. Trocar os dois dá um resultado plausível e errado, do tipo que passa nos exemplos do enunciado e falha no caso 47.

O estado que não é O(1) de manter. Se para saber se a janela é válida você precisa varrer o que está dentro dela, você não tem uma janela deslizante, tem uma força bruta com bordas móveis. O estado precisa ser atualizável só com quem entrou e quem saiu: soma, contagem, dicionário de frequências, tudo em O(1).

Esquecer o caso "nenhuma janela serve". Se nenhuma janela válida existe, o que se retorna? Zero, -1, string vazia? O enunciado quase sempre diz, e quase todo mundo pula essa linha.

Como praticar

Antes de ir para o LeetCode, use os visualizadores acima para prever e conferir. Faça assim: decida a resposta na sua cabeça primeiro, depois rode.

• Na janela fixa, ponha k igual ao tamanho do array. Quantos passos o laço dá? (Resposta: um, a janela nunca desliza.)
• Ainda na fixa, ponha k = 1. A janela vira o quê? (O próprio maior elemento.)
• Na variável, edite o array para todos os valores serem maiores que o limite. Nenhuma janela é válida: o que o visualizador devolve?
• Na variável, ponha um limite gigante. A esquerda chega a andar alguma vez?

Casos de borda que valem testar em qualquer solução sua:

Depois disso, resolva os problemas na ordem da lista abaixo. Os três primeiros são de janela fixa e servem para firmar as bordas; os seguintes são de janela variável, e o Minimum Window Substring é o clássico que junta janela com dicionário de frequências, o passo final da técnica.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 2:08:22.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Este tópico também tem página própria, fora deste roadmap: Sliding Window.