Product of Array Except Self

Last updated Aug 16, 2023 Edit Source

• Programming
• Interviewprep
• Leetcode

Es un problema bastante sencillo de solucionar, sin embargo, necesita que entiendas bien la estructura de como se define un producto de un elemento.

Las constraints son algo que complica mucho este problema. El problema diec asi:

Dado un array de numeros nums retorna otro array en el cual en la posicion ith se encuentre la multiplicacion de todos los demas elementos del array excepto el que se encuentra en la ith posicion. Por ejemplo, dado el array [1,2,3,4] el resultado esperado seria [24,12,8,4]. Contraint: Resolverlo en un algoritmo de O(n).

Una de las claves mas importantes este problema seria recordar que un algoritmo O(n) puede iterar la cantidad de veces que sea necesaria sobre el array de longitud n

Para solucionar este problema tenemos una muy buena alternativa utilizando una logica inteligente de prefijos y postfijos. Esto viene dado en la naturaleza misma del numero que se espera como resultado.

Analicemos un poco, ¿como se forma un numero (por ejemplo, el 12) en una ejecucion del algoritmo? Este se constituye de dos partes importantes:

• Todos los numeros multiplicados entre si que se encuentran antes de el
• Todos los numeros multiplicados entre si que se encuentran despues de el Dados estos datos, podriamos considerar que cada numero en el array de respuesta esta formado por la multiplicacion de todos los que le preceden (prefijo) y la multiplicacion de todos los que le proceden (postfijo).

Con esto en mente, una solucion sencilla para este problema podria ser:

1. Inicializar un array de longitud N (el resultado) con numeros 1 para que los prefijos y sufijos se puedan inicializar bien.
2. Inicializar una variable de prefijo con el valor del primer elemento en la izquierda, en esta se ira guardara el valor de prefijo hasta el indice que se encuentre la iteracion
3. Iterar sobre el el array nums de izquierda a derecha a partir del segundo elemento (debido a que el primero no tiene prefijo).
4. En cada iteracion, actualizar el array results en la posicion ith actual, con el resultado de multiplicar el valor actual en results por el prefijo
5. Actualizar tambien ademas el prefijo con el resultado de la multiplicacion del prefijo actual por el valor actual, este sera el prefijo del siguiente numero
6. Una vez finalizada la iteracion, inicializar otra variable de postfijo, con el valor del ultimo elemento en la derecha (debido a que esta no tiene postfijo), en este se guardaran los valores postfijos
7. Iterar sobre el array nums de derecha izquierda empezando por el penultimo elemento.
8. En cada iteracion actualizar el array results en la posicion actual con el resultaod de multiplicar el valor existente en dicho indice por el postfijo acumulado
9. Actualizar nuevamente el psotfijo con el resultado de multiplicar el postfijo actual por el valor actual, este sera el postfijo del siguiente numero
10. Una vez finalziadas las dos iteraciones, el array results tendra la multiplicacion de los prefijos con los postfijos.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

function productExceptSelf(nums: number[]): number[] {
	const results: number[] = Array.from({ length: nums.length }. () => 1);

	let prefix = nums[0];
	for (let i = 1; i < nums.length; i++) {
		results[i] *= prefix;
		prefix *= nums[i];
	}

	let postfix = nums[nums.length - 1];
	for (let i = nums.length - 2; i >= 0; i--) {
		results[i] *= postfix;
		postfix *= nums[i];
	}

	return results;
}