Introdução
Bem-vindos ao nosso 15º artigo na série Preparação para Entrevistas. Neste artigo estudaremos o seguinte problema: Squares of a Sorted Array. Este problema apresenta uma questão peculiar: como podemos eficientemente calcular os quadrados de um array ordenado de números, que podem ser tanto negativos quanto positivos, e ordená-los de forma ascendente?
Esta tarefa, aparentemente simples à primeira vista, esconde detalhes interessantes. A presença de números negativos ao lado de positivos adiciona uma camada extra de desafio, pois quando elevados ao quadrado, os números negativos podem se tornar maiores que os positivos originais. Portanto, um detalhe deste problema está em encontrar uma maneira eficaz de lidar com esta dualidade e alcançar uma solução que não só resolva a questão, mas também o faça de maneira otimizada.
Como de costume, vamos começar com uma compreensão clara do problema em questão.
Analisando o problema "Squares of a Sorted Array"
O objetivo deste problema é transformar um array ordenado de números inteiros, que podem ser negativos ou positivos, em um array onde cada elemento é o quadrado do número correspondente, e então, ordenar este novo array em ordem crescente. A dificuldade surge devido à presença de números negativos, pois, ao serem elevados ao quadrado, podem resultar em valores maiores que os quadrados dos números positivos.
Para compreender melhor o desafio proposto pelo problema ‘Squares of a Sorted Array’, vamos considerar alguns exemplos. Imagine um array de números inteiros como [-5, -2, 2, 4, 6]. Nossa tarefa é calcular o quadrado de cada elemento, resultando em [25, 4, 4, 16, 36], e depois ordenar estes valores de forma crescente, obtendo [4, 4, 16, 25, 36].
Este exemplo demonstra que o simples fato de o array de entrada está ordenado não é suficiente, pois os números negativos, quando elevados ao quadrado, podem resultar em valores maiores do que os números positivos originais. Portanto, a solução exige uma estratégia mais elaborada.
Soluções
Uma maneira simples de abordar o problema ‘Squares of a Sorted Array’ é calcular o quadrado de cada número no array e, em seguida, usar um algoritmo de ordenação padrão para organizar os elementos em ordem crescente. Apesar de ser uma solução correta, ela pode ser ineficiente, principalmente em casos com arrays grandes, devido à sua complexidade de tempo mais elevada.
A chave para uma solução mais eficiente é a técnica de dois ponteiros. Este método permite processar o array de maneira otimizada, identificando e colocando os quadrados dos números em suas posições corretas de uma forma mais rápida e direta.
A técnica de dois ponteiros não é apenas mais rápida, mas também mais elegante, aproveitando que o array já está ordenado. Com ela, é possível alcançar uma solução mais otimizada e adequada para arrays de qualquer tamanho.
Soluções em Java e Python para o Problema Squares of a Sorted Array
Agora, veremos na prática como implementar uma solução eficiente para o problema Squares of A Sorted Array utilizando a técnica de dois ponteiros(two pointers technique)
O conceito por trás dessa abordagem é começar pelas extremidades do array e usar dois índices para rastrear os elementos. Ao comparar os valores absolutos dos elementos nos extremos, podemos decidir qual quadrado será colocado na próxima posição do array de saída. Este método tira vantagem do fato de que os maiores quadrados, em um array ordenado, provêm dos valores absolutos mais altos, independentemente de serem positivos ou negativos.
import java.util.Arrays;
public class SquareSortedArray {
public static int[] squareArray(int[] numbers) {
int[] result = new int[numbers.length];
int left = 0;
int right = numbers.length - 1;
for (int i = numbers.length - 1; i >= 0; i--) {
if (Math.abs(numbers[left]) > Math.abs(numbers[right])) {
result[i] = numbers[left] * numbers[left];
left++;
} else {
result[i] = numbers[right] * numbers[right];
right--;
}
}
return result;
}
public static void main(String[] args) {
int[] numbers = {-5, -2, 2, 4, 6};
System.out.println(Arrays.toString(squareArray(numbers)));
}
}
def square_array(numbers):
result = [0] * len(numbers)
left, right = 0, len(numbers) - 1
for i in range(len(numbers) - 1, -1, -1):
if abs(numbers[left]) > abs(numbers[right]):
result[i] = numbers[left] ** 2
left += 1
else:
result[i] = numbers[right] ** 2
right -= 1
return result
# Exemplo de uso
numbers = [-7,-5, -2, 2, 4, 6]
print(square_array(numbers))
Explorando o Código: A Técnica de Dois Ponteiros em Ação
O código emprega a técnica de dois ponteiros para calcular e ordenar os quadrados de um array de inteiros. Inicializa-se com ponteiros left e right nas extremidades do array. Em um loop decrescente, comparam-se os valores absolutos dos elementos nas extremidades, e o maior é elevado ao quadrado e colocado na posição correta do array de resultado. Este processo é repetido até que todos os elementos sejam processados. Essa abordagem garante que o array resultante esteja ordenado e otimiza a comparação e ordenação dos elementos.
Análise de Complexidade: Entendendo a Eficiência em Tempo e Espaço
Complexidade de Tempo
O algoritmo percorre o array uma única vez, realizando um trabalho constante em cada iteração: comparar elementos, elevar ao quadrado e armazenar o resultado. Portanto, a complexidade de tempo é O(N), onde N é o número de elementos no array. Esta complexidade linear representa uma melhoria significativa em relação a uma abordagem mais simples que envolveria ordenar após o cálculo dos quadrados, geralmente O(N log N).
Complexidade de Espaço
Em termos de espaço, o algoritmo utiliza um array separado para armazenar os valores ao quadrado. Esse array tem o mesmo tamanho do array de entrada, resultando em uma complexidade de espaço O(N), que é proporcional ao tamanho da entrada.
Conclusão
Neste artigo, exploramos o desafio “Squares of a Sorted Array” e mostramos como é mais do que apenas mexer com números em um array. Usamos uma técnica chamada dois ponteiros para resolver o problema de forma rápida e eficiente, tanto em termos de tempo quanto de espaço. Isso mostra que mesmo problemas que parecem complicados podem ser solucionados de maneira fácil e eficaz. Esse exemplo nos ajuda a entender melhor como os algoritmos funcionam na prática e nos incentiva a continuar aprendendo e descobrindo mais sobre o fascinante mundo da programação.
E se você se interessou por esta técnica, temos outros artigos no blog que utilizam o método dos dois ponteiros para resolver diferentes problemas. Este artigos podem ser encontrados aqui.
Se você gostou deste artigo ou tem alguma dúvida, deixe um comentário abaixo. Adoraria ouvir suas experiências com entrevistas técnicas e como você abordou este problema específico. Além disso, não se esqueça de conferir os outros artigos desta série para mais insights e dicas.
Referências
Cracking the Coding Interview’ é um best-seller renomado e um favorito pessoal – um livro indispensável na preparação para entrevistas técnicas!
Designing Data-Intensive Applications: é uma referência para criar aplicações escaláveis, robustas e de alto desempenho!