Fundamentos de Arrays e Operações In-Place
Revise indexação, mutação e as armadilhas mais comuns de entrevistas sobre arrays, como erros de limite e alterações em uma lista durante a iteração.
Fundamentos de Arrays e Operações In-Place é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Vetores como memória contígua
Internamente, uma lista do Python é implementada com um vetor dinâmico — um bloco contíguo de memória no qual os elementos são armazenados em endereços consecutivos. Esse layout fornece acesso aleatório O(1) por índice: o Python calcula address = base + index × element_size instantaneamente. Inserções ou remoções no meio exigem deslocar todos os elementos seguintes, com custo O(n). Essa assimetria está na origem da maioria das discussões sobre compromissos de vetores em entrevistas.
nums = [10, 20, 30, 40, 50]
# O(1) random access
print(nums[2]) # 30
print(nums[-1]) # 50
# O(1) append (amortised)
nums.append(60)
print(nums) # [10,20,30,40,50,60]
# O(n) insert at beginning
nums.insert(0, 0) # shifts all elements right
print(nums) # [0,10,20,30,40,50,60]Erro de deslocamento de uma posição: o bug clássico de vetores
Erros de deslocamento de uma posição são a fonte mais frequente de respostas incorretas em problemas com vetores. A indexação começando em 0 do Python significa que o último índice válido é len(arr) - 1. Ao escrever laços, decida se precisa de < ou <= verificando a condição de limite com a menor entrada válida (n=1 ou n=2). Sempre verifique seu limite com exemplos concretos antes de enviar a solução.
def find_max(nums):
# Use len(nums)-1 as last index
max_val = nums[0] # safe if n >= 1
for i in range(1, len(nums)): # start at 1, not 0
if nums[i] > max_val:
max_val = nums[i]
return max_val
print(find_max([3, 1, 4, 1, 5])) # 5
print(find_max([7])) # 7 (single element)
# Would crash if we accessed nums[len(nums)]Inversão no próprio local com dois ponteiros
Inverter um vetor no próprio local usa dois ponteiros que começam em extremidades opostas e trocam elementos avançando para o centro até se encontrarem. Isso exige O(1) de espaço extra e O(n) de tempo. A condição left < right (estritamente menor) garante a correção para comprimentos pares e ímpares — com um número ímpar de elementos, o elemento central permanece automaticamente no lugar.
def reverse_inplace(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# Space: O(1) Time: O(n)
a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a) # [5, 4, 3, 2, 1]
b = [1, 2, 3]
reverse_inplace(b)
print(b) # [3, 2, 1] middle element unchangedRotacionando um vetor no próprio local
É possível rotacionar um vetor para a direita em k posições no próprio local invertendo três segmentos: primeiro inverta o vetor inteiro, depois os primeiros k elementos e, por fim, os n-k elementos restantes. Isso alcança O(n) de tempo e O(1) de espaço — muito melhor que a abordagem que usa O(n) de espaço para fatiar e concatenar. Sempre reduza k módulo n para lidar com k ≥ n.
def rotate(nums, k):
n = len(nums)
k %= n # handle k >= n
def rev(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1; r -= 1
rev(0, n-1) # reverse all
rev(0, k-1) # reverse first k
rev(k, n-1) # reverse rest
a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a) # [5, 6, 7, 1, 2, 3, 4]Removendo elementos no próprio local
Remover duplicatas ou valores-alvo no próprio local usa um ponteiro de escrita que acompanha onde o próximo elemento válido deve ser escrito. O ponteiro de leitura avança; quando encontra um elemento válido, ele o copia para a posição de escrita e avança os dois ponteiros. Esse é o padrão central de problemas do LeetCode como «remover elemento», «remover duplicatas de vetor ordenado» e «mover zeros».
def remove_element(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write # new length
nums = [3, 2, 2, 3]
new_len = remove_element(nums, 3)
print(nums[:new_len]) # [2, 2]
nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
new_len2 = remove_element(nums2, 2)
print(nums2[:new_len2]) # [0, 1, 3, 0, 4]Mover os Zeros: Ponteiro de Leitura e Escrita
Mova todos os zeros para o final de um vetor, preservando a ordem dos elementos diferentes de zero. A abordagem do ponteiro de leitura e escrita coloca cada elemento diferente de zero na posição de escrita e depois preenche o final com zeros. Uma abordagem alternativa troca os zeros para movê-los para trás, preservando a ordem sem uma segunda passagem de preenchimento. Ambas têm complexidade de tempo O(n) e de espaço O(1).
def move_zeroes(nums):
write = 0
# Move all non-zeroes to front
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read]
write += 1
# Fill rest with zeroes
while write < len(nums):
nums[write] = 0
write += 1
a = [0, 1, 0, 3, 12]
move_zeroes(a)
print(a) # [1, 3, 12, 0, 0]Elevar ao Quadrado e Ordenar no Próprio Vetor
Dado um vetor ordenado de inteiros (possivelmente negativos), retorne um vetor com seus quadrados em ordem crescente. A abordagem ingênua eleva os elementos ao quadrado e depois os ordena: O(n log n). A abordagem ideal de dois ponteiros aproveita o fato de que os maiores quadrados vêm de uma das extremidades da entrada ordenada: compare os valores absolutos dos elementos mais à esquerda e mais à direita e preencha o resultado da direita para a esquerda em O(n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1 # fill from the right
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Encontrar o Pivô e Particionar
O problema da bandeira nacional holandesa particiona um vetor em três seções (menor que, igual ao e maior que o pivô) no próprio vetor, usando três ponteiros. Esta é a subetapa fundamental da ordenação rápida e a solução do LeetCode 'sort cores'. Manter a invariante de que os elementos antes do ponteiro inferior são < pivô e os elementos depois do ponteiro superior são > pivô orienta o algoritmo.
def sort_colors(nums):
# Dutch national flag: 0s, 1s, 2s
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # don't advance mid: new nums[mid] unexamined
a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a) # [0, 0, 1, 1, 2, 2]Modificar Elementos do Vetor Durante a Iteração
Você pode modificar os valores dos elementos com segurança (por exemplo, multiplicando por -1 para marcar elementos visitados) durante a iteração, mas nunca altere o comprimento de uma lista durante um laço de repetição. Uma técnica segura de codificação é codificar temporariamente dois valores em um único inteiro (por exemplo, usando o bit de sinal) para simular um booleano adicional por elemento sem alocar espaço extra. Isso aparece em problemas como encontrar todos os números que desapareceram em um vetor.
def find_disappeared(nums):
# Mark visited by negating the value at the index
for n in nums:
idx = abs(n) - 1
if nums[idx] > 0:
nums[idx] *= -1 # mark as seen
# Indices with positive values are missing
return [i + 1 for i, v in enumerate(nums) if v > 0]
print(find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))
# [5, 6] -- O(n) time, O(1) extra spaceLista de Verificação de Padrões de Vetores para Entrevistas
Antes de programar qualquer problema de vetores, percorra esta lista de verificação mental:
- O vetor está ordenado? (permite usar dois ponteiros e busca binária)
- Os elementos estão limitados (por exemplo, de 1 a n)? (permite técnicas baseadas em índices)
- É necessário trabalhar no próprio vetor? (ponteiro de leitura e escrita ou trocas)
- É necessário encontrar todos os pares ou apenas um? (determina se laços aninhados são aceitáveis)
- Casos extremos: vetor vazio, um único elemento, todos os valores iguais
def max_profit(prices):
# Pattern: single scan, track running minimum
# Time: O(n), Space: O(1)
if not prices: return 0 # edge case: empty
min_price = prices[0]
max_prof = 0
for price in prices[1:]: # start at index 1
max_prof = max(max_prof, price - min_price)
min_price = min(min_price, price)
return max_prof
print(max_profit([7, 1, 5, 3, 6, 4])) # 5
print(max_profit([7, 6, 4, 3, 1])) # 0Algoritmo de Kadane: Subvetor Máximo
O algoritmo de Kadane encontra o subvetor contíguo de soma máxima em O(n) e com espaço O(1). A cada etapa, decida se deve estender o subvetor atual ou iniciar um novo: current = max(num, current + num). Se current + num for menor que apenas num, o subvetor atual está reduzindo o resultado e devemos recomeçar. Acompanhe o máximo global durante todo o percurso.
def max_subarray(nums):
current = global_max = nums[0]
for n in nums[1:]:
current = max(n, current + n) # extend or restart
global_max = max(global_max, current)
return global_max
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6 (subarray [4, -1, 2, 1])
print(max_subarray([-1, -2, -3]))
# -1 (all negative: take the least negative)Verificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da Lição
Nesta lição, você aprendeu: os vetores oferecem acesso aleatório O(1), mas inserções e exclusões no meio custam O(n) — conhecer essa assimetria orienta a escolha do algoritmo, o padrão do ponteiro de leitura e escrita remove elementos ou move valores no próprio vetor em O(n), usando espaço O(1) e a codificação com bit de sinal e as técnicas de usar o índice como marcação permitem soluções com espaço O(1) para problemas que, de outro modo, exigiriam um vetor auxiliar. A seguir, exploraremos somas prefixadas e totais acumulados.
Perguntas Frequentes
A aula “Fundamentos de Arrays e Operações In-Place” é grátis?
Sim — o texto completo de “Fundamentos de Arrays e Operações In-Place” é 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Fundamentos de Arrays e Operações In-Place”?
Revise indexação, mutação e as armadilhas mais comuns de entrevistas sobre arrays, como erros de limite e alterações em uma lista durante a iteração. Você pratica DSA 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 DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA 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 1 de 4.
Quanto tempo leva a aula “Fundamentos de Arrays e Operações In-Place”?
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 DSA Interview Prep?
Sim. Cada aula de DSA 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
- Fundamentos de Arrays e Operações In-Place
- Somas de Prefixos e Totais Acumulados
- Dois Ponteiros: Extremidades Opostas
- Dois Ponteiros: Lento e Rápido