0Pricing
Coding Interview Prep · Aula

Encontrando lacunas em uma sequência

Detecte valores ausentes e o início e o fim de cada lacuna.

Encontrando lacunas em uma sequência é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.

Agora vamos procurar as lacunas

Até aqui, agrupamos linhas em ilhas. A pergunta espelhada comum em entrevistas é: quais valores estão faltando? Os entrevistadores podem formulá-la como “encontre as lacunas nesta sequência de ID”, “quais números de fatura foram pulados” ou “em quais dias não houve atividade”.

As lacunas são os espaços vazios entre as ilhas. A principal percepção é que normalmente você não precisa listar cada valor ausente; basta informar o início e o fim de cada intervalo de lacuna, que é muito mais compacto e corresponde ao que os entrevistadores esperam.

O conjunto de dados de exemplo com lacunas

Reutilize os valores presentes 1, 2, 3, 7, 8, 10 da tabela seq(n). As lacunas a informar são:

  • De 4 a 6 (após a primeira ilha e antes de 7)
  • De 9 a 9 (entre 8 e 10)

Observe que descrevemos uma lacuna como um intervalo: início da lacuna = último valor presente + 1, fim da lacuna = próximo valor presente - 1. Essa forma compacta é o objetivo da técnica principal a seguir.

CREATE TABLE seq (n INT);
INSERT INTO seq VALUES (1),(2),(3),(7),(8),(10);

A abordagem LEAD para lacunas

O detector de lacunas mais simples compara cada linha com a próxima usando LEAD. Se o próximo valor for mais de 1 maior que o valor atual, haverá uma lacuna entre eles.

Para cada linha desse tipo, a lacuna começa em n + 1 e termina em next_n - 1. Primeiro, observe o resultado bruto de LEAD:

SELECT
  n,
  LEAD(n) OVER (ORDER BY n) AS next_n
FROM seq
ORDER BY n;

Informando intervalos de lacunas

Coloque o resultado de LEAD em uma CTE e mantenha apenas as linhas em que o salto para o próximo valor excede 1. Essas linhas indicam lacunas:

Isso retorna exatamente a lacuna 4-6 e a lacuna 9-9. A expressão next_n - n - 1 também fornece a quantidade de valores ausentes em cada lacuna, uma pergunta complementar frequente.

WITH stepped AS (
  SELECT n, LEAD(n) OVER (ORDER BY n) AS next_n
  FROM seq
)
SELECT
  n + 1            AS gap_start,
  next_n - 1       AS gap_end,
  next_n - n - 1   AS missing_count
FROM stepped
WHERE next_n - n > 1
ORDER BY gap_start;

A variante simétrica com LAG

Você também pode detectar essas mesmas lacunas olhando para trás com LAG. Existe uma lacuna antes da linha atual quando o valor anterior é mais de 1 menor que o valor atual.

As duas abordagens são totalmente equivalentes; escolha a que parecer mais natural para a pergunta. Alguns entrevistadores preferem LEAD porque a lacuna é descrita em relação à linha que a precede, acompanhando a forma como as pessoas costumam falar.

WITH stepped AS (
  SELECT n, LAG(n) OVER (ORDER BY n) AS prev_n
  FROM seq
)
SELECT prev_n + 1 AS gap_start,
       n - 1       AS gap_end
FROM stepped
WHERE n - prev_n > 1
ORDER BY gap_start;

Listando todos os valores ausentes

Às vezes, o entrevistador realmente quer a lista completa dos números ausentes, e não apenas os intervalos. A abordagem robusta é gerar a sequência completa esperada e fazer uma junção anti com o que existe. No Postgres, generate_series cria o intervalo completo:

Cada inteiro do intervalo esperado que não esteja presente em seq é um valor ausente. Isso também trata lacunas nas extremidades, caso você conheça o mínimo e o máximo pretendidos.

SELECT g.n AS missing_value
FROM generate_series(
       (SELECT MIN(n) FROM seq),
       (SELECT MAX(n) FROM seq)
     ) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL
ORDER BY g.n;

Geração de séries entre dialetos

Nem todo mecanismo oferece generate_series. Conheça as alternativas:

  • Postgres: generate_series(1, 100).
  • SQL Server: uma CTE recursiva ou uma tabela de números/contagem.
  • MySQL 8: uma CTE recursiva que conte até o máximo.

Uma CTE recursiva é a alternativa de reserva portátil. Ela produz a mesma sequência esperada para fazer a junção anti.

WITH RECURSIVE nums AS (
  SELECT (SELECT MIN(n) FROM seq) AS n
  UNION ALL
  SELECT n + 1 FROM nums
  WHERE n + 1 <= (SELECT MAX(n) FROM seq)
)
SELECT nums.n AS missing_value
FROM nums
LEFT JOIN seq s ON s.n = nums.n
WHERE s.n IS NULL;

Lacunas em datas do calendário

Para datas ausentes, gere um calendário completo com passo diário e faça uma junção anti. Esta é a consulta padrão para descobrir “quais dias não tiveram pedidos”:

Combine-a com a técnica de intervalos aplicando LEAD às datas reais para informar períodos de datas ausentes em vez de dias individuais, usando + INTERVAL '1 day' nos limites.

SELECT d::date AS missing_day
FROM generate_series(
       DATE '2026-01-01', DATE '2026-01-31',
       INTERVAL '1 day') AS d
LEFT JOIN daily_logins l ON l.login_date = d::date
WHERE l.login_date IS NULL
ORDER BY missing_day;

Lacunas nas extremidades além dos dados

Uma armadilha sutil: LEAD/LAG só encontra lacunas entre valores presentes. Se faltar um número antes do menor valor ou depois do maior valor presente, a abordagem de janela não conseguirá identificá-lo, pois não existe uma linha vizinha.

Se o entrevistador definir um intervalo completo esperado (por exemplo, IDs de 1 a 100) e seus dados começarem em 5, você deverá usar a junção anti para gerar a série, limitada pelo intervalo declarado, e não pelo mínimo e máximo dos próprios dados. Sempre confirme se os limites esperados são fixos.

SELECT g.n AS missing_value
FROM generate_series(1, 100) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL;

Detecção de lacunas por grupo

Para encontrar lacunas por usuário, particione LEAD/LAG pela coluna do grupo, para que uma lacuna nunca seja informada entre os fluxos de dois usuários diferentes:

Os intervalos ausentes de cada usuário são calculados de forma independente. Assim como acontece com as ilhas, esquecer a partição mescla usuários silenciosamente e produz lacunas fantasmas entre linhas sem relação.

WITH stepped AS (
  SELECT user_id, n,
    LEAD(n) OVER (PARTITION BY user_id ORDER BY n) AS next_n
  FROM seq_per_user
)
SELECT user_id, n + 1 AS gap_start, next_n - 1 AS gap_end
FROM stepped
WHERE next_n - n > 1
ORDER BY user_id, gap_start;

Escolhendo o método certo para lacunas

Guia de decisão para a entrevista:

  • Você quer intervalos compactos e apenas lacunas internas? Use LEAD/LAG, filtrando quando o passo exceder 1.
  • Você quer cada valor ausente individualmente ou lacunas além das extremidades dos dados? Use uma junção anti para gerar a série contra o intervalo completo declarado.

Mencionar as duas opções e quando cada uma se aplica demonstra profundidade. O método LEAD é mais barato; o método da série é mais completo.

Verificação rápida

Delimite a armadilha dos casos-limite.

Recapitulando: encontrando lacunas

Detecção de lacunas, consolidada:

  • Informe as lacunas como intervalos: início da lacuna = valor + 1, fim da lacuna = próximo valor - 1.
  • LEAD (ou o LAG simétrico), filtrado quando o passo exceder 1, encontra lacunas internas com baixo custo.
  • A junção anti para gerar a série lista todos os valores ausentes e identifica lacunas nas extremidades com base em um intervalo declarado.
  • CTEs recursivas geram a série quando generate_series não está disponível.
  • Para encontrar lacunas por usuário, faça a partição pela coluna do grupo.
  • Sempre confirme os limites esperados.

Por fim, abordaremos a variante mais rica: ilhas definidas por data e mudanças de estado.

Perguntas Frequentes

A aula “Encontrando lacunas em uma sequência” é grátis?

Sim — o texto completo de “Encontrando lacunas em uma sequência” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.

O que vou aprender em “Encontrando lacunas em uma sequência”?

Detecte valores ausentes e o início e o fim de cada lacuna. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Coding Interview Prep?

Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.

Quanto tempo leva a aula “Encontrando lacunas em uma sequência”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Coding Interview Prep?

Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Reconhecendo um problema de lacunas e ilhas
  2. O truque da diferença de números de linha
  3. Encontrando lacunas em uma sequência
  4. Ilhas com mudanças de data e status
← Voltar para Coding Interview Prep