Índice del punto de equilibrio
La misión
Problema
Dada una lista de números enteros, que pueden ser negativos, encuentra una posición en la que los valores estrictamente a su izquierda sumen el mismo total que los valores estrictamente a su derecha. Un lado vacío cuenta como cero. Devuelve el índice más a la izquierda que cumpla esto, o -1 si no hay ninguno.
Ejemplos
Input: values = [2, 7, 1, 5, 4]
Output: 2
Por qué: 2 + 7 = 9 a la izquierda del índice 2, y 5 + 4 = 9 a la derecha
Input: values = [1, 2, 3]
Output: -1
Por qué: ningún índice divide la lista en lados iguales
Input: values = [5]
Output: 0
Por qué: caso límite: los dos lados del único valor están vacíos y suman 0
Pistas
0 / 3
Sumar ambos lados desde cero en cada índice repite las mismas sumas una y otra vez, lo que vuelve cuadrática toda la comprobación.
Una vez que conoces el total de la lista completa, el lado derecho en cualquier índice se deduce del lado izquierdo y del valor en ese índice.
Suma la lista una vez. Luego recórrela con un total izquierdo acumulado: el total derecho es el total general menos el total izquierdo menos el valor actual. Devuelve el primer índice donde coincidan, y suma el valor actual al total izquierdo antes de seguir.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- values may be negative
Solución
Una pasada calcula el total general, y una segunda pasada lleva una suma acumulada de todo lo que ya se recorrió. En cada índice, el lado derecho es lo que queda del total después de quitar el lado izquierdo y el valor actual, así que cada comprobación es O(1) en lugar de O(n). Se devuelve la primera coincidencia, que por eso es la que está más a la izquierda. El tiempo es O(n), y el espacio extra es O(1).
def balance_point(values):
total = sum(values)
left = 0
for i, v in enumerate(values):
right = total - left - v # everything after index i
if left == right:
return i
left += v
return -1
print(balance_point([2, 7, 1, 5, 4])) # -> 2
print(balance_point([1, 2, 3])) # -> -1
print(balance_point([5])) # -> 0¿Lo que te frena es la idea y no el código? O(1) y O(n) lo explica.