Find Pivot Index

+10

Se te proporciona un arreglo de enteros nums. Un índice de pivote es un índice donde la suma de los valores a su izquierda es igual a la suma de los valores a su derecha. El valor del propio pivote no pertenece a ninguno de los lados, y un lado sin valores suma 0.

Devuelve el índice de pivote más a la izquierda, o -1 si ningún índice es un pivote.

Función

pivotIndex(nums: integer-array) → integer

numsinteger-array: el arreglo de enteros que se debe equilibrar
Devuelveinteger: el índice del pivote más a la izquierda, o -1 si no hay ninguno

Restricciones

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Ejemplos

Entrada: nums = [3, 1, 5, 2, 2]
Salida: 2
Explicación: En el índice 2, el lado izquierdo es 3 + 1 = 4 y el lado derecho es 2 + 2 = 4. El índice 0 y el índice 1 no están equilibrados (izquierda 0 frente a 10, izquierda 3 frente a 9), así que 2 es el pivote más a la izquierda.

Entrada: nums = [1, 2, 3]
Salida: -1
Explicación: Los tres candidatos dan 0 frente a 5, 1 frente a 3 y 3 frente a 0. Ningún índice queda equilibrado, así que la respuesta es -1.

+17 pruebas ocultas al enviar

Para ir más allá

¿Puedes encontrar el pivote más a la izquierda leyendo cada valor una sola vez, sin sumar primero el total? ¿Cuánta memoria requiere eso?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Comprobar un índice requiere dos sumas, pero volver a calcularlas en cada índice hace que el trabajo crezca con el cuadrado de la longitud. La solución es dejar de volver a calcularlas: la suma de la izquierda aumenta en un valor en cada paso, y la suma de la derecha es lo que queda del total. Una pasada para calcular el total y una segunda pasada con una suma acumulada a la izquierda encuentran el pivote más a la izquierda, con dos números en memoria.

Suma ambos lados en cada índice

Correcto, pero no termina con las pruebas más grandes

Intuición

Sigue la definición. Para cada índice i, suma los valores anteriores, suma los valores posteriores y compara. El primer índice en el que las dos sumas coinciden es la respuesta, porque pruebas los índices de izquierda a derecha.

Los extremos se resuelven solos. En el índice 0, el bucle de la izquierda se ejecuta cero veces, así que la suma de la izquierda es 0; en el último índice, el bucle de la derecha se ejecuta cero veces. Por eso [4, -4, 9] devuelve 2.

El costo es el problema. Para cada índice se suman los otros n-1 valores, así que el trabajo total es de aproximadamente n² sumas. Con 10,000 valores, eso se acerca a 100 millones de sumas, y la mayoría repite sumas que ya calculaste para el índice anterior.

Algoritmo

Recorre con i todos los índices de nums.
Suma nums[0] hasta nums[i-1] como suma izquierda.
Suma nums[i+1] hasta el último valor como suma derecha.
Si las dos sumas son iguales, devuelve i.
Si ningún índice coincide, devuelve -1.

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left = 0
        for j in range(i):
            left += nums[j]
        right = 0
        for j in range(i + 1, n):
            right += nums[j]
        if left == right:
            return i
    return -1

Suma prefija de un arreglo

Intuición

La fuerza bruta sigue sumando los segmentos del arreglo. Un arreglo de sumas de prefijos hace ese trabajo una sola vez. Sea prefix[k] la suma de los primeros k valores, con prefix[0] = 0. Para [3, 1, 5, 2, 2], eso da [0, 3, 4, 9, 11, 13].

Ahora cualquier segmento es la diferencia entre dos elementos. El lado izquierdo del índice i son los primeros i valores, así que es prefix[i]. El lado derecho es todo lo que viene después de nums[i], es decir, prefix[n] - prefix[i+1]. En el índice 2, eso da 4 a la izquierda y 13 - 9 = 4 a la derecha: un pivote.

Construir el arreglo requiere una pasada y cada comprobación toma tiempo constante, así que toda la búsqueda es O(n). El costo es n+1 números adicionales en memoria.

Algoritmo

Crea prefix de longitud n+1 con prefix[0] = 0.
Complétalo: prefix[k+1] = prefix[k] + nums[k].
Para cada índice i, lee la suma de la izquierda como prefix[i] y la suma de la derecha como prefix[n] - prefix[i+1].
Devuelve el primer i donde sean iguales, o -1 después del bucle.

def pivotIndex(nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values.
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + nums[k]
    for i in range(n):
        left = prefix[i]
        right = prefix[n] - prefix[i + 1]
        if left == right:
            return i
    return -1

Suma total y suma acumulada por la izquierda

Intuición

Observa qué entradas del prefijo lee el enfoque anterior. En el índice i necesita prefix[i], prefix[i+1] y prefix[n]. La última es el total, que nunca cambia, y las otras dos son la suma acumulada que tendrías si recorrieras el arreglo una vez. Así que puedes mantener el total y una sola suma acumulada izquierda en lugar de todo el arreglo.

Cada valor está a la izquierda, en el pivote o a la derecha. Por lo tanto, la suma de la derecha es el total menos la suma de la izquierda menos nums[i]. Para [3, 1, 5, 2, 2], el total es 13. En el índice 0, la suma de la izquierda es 0 y la suma de la derecha es 13 - 0 - 3 = 10. En el índice 1, es 3 frente a 9. En el índice 2, es 4 frente a 13 - 4 - 5 = 4, así que devuelves 2.

El orden dentro del bucle importa. Compara primero y luego suma nums[i] a la suma de la izquierda, para que esta nunca incluya el valor del índice que estás comprobando. Devolver el resultado en la primera coincidencia te da el pivote más a la izquierda.

Lees el arreglo dos veces, una para el total y otra para el recorrido, así que el tiempo es O(n). Solo se almacenan dos números, así que el espacio adicional es O(1).

Algoritmo

Suma todos los valores en total.
Establece left en 0.
Para cada índice i, si left es igual a total - left - nums[i], devuelve i.
De lo contrario, suma nums[i] a left y continúa.
Si el bucle termina, devuelve -1.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, value in enumerate(nums):
        # Everything that is not on the left and not nums[i] is on the right.
        if left == total - left - value:
            return i
        left += value
    return -1

Errores comunes y casos límite

La mayoría de las respuestas incorrectas colocan el valor del pivote en uno de los lados o se saltan un índice del extremo.

Agregar nums[i] a la suma izquierda antes de la comparación. Entonces, el lado izquierdo incluye el valor del pivote, y [3, 1, 5, 2, 2] ya no encuentra el índice 2.
Calcular el lado derecho como total - left. Eso cuenta nums[i] en el lado derecho; réstalo también.
Saltarse el índice 0 o el último índice. Ambos pueden ser el pivote, porque la suma de un lado vacío es 0. [1, -1, 1] devuelve 0 y [4, -4, 9] devuelve 2.
Devolver la última coincidencia en lugar de la primera. En [0, 0, 0], todos los índices están equilibrados, y la respuesta es 0.
Usar dos punteros que se mueven hacia adentro desde ambos extremos y aumentan el lado más pequeño. Eso solo funciona cuando todos los valores son no negativos; aquí los valores llegan hasta -1000, así que un lado puede reducirse a medida que crece.
Olvidar que los arreglos de Lua y R empiezan en 1. Devuelve i-1 para que la respuesta sea un índice basado en 0.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Find Pivot Index?

La solución con el total y la suma acumulada se ejecuta en tiempo O(n): una pasada para sumar el array y otra para recorrerlo. Usa espacio adicional O(1). En cambio, volver a calcular ambos lados en cada índice requiere tiempo O(n²).

¿Por qué la suma de la derecha es igual al total menos la suma de la izquierda menos nums[i]?

Cada valor del arreglo está exactamente en uno de estos tres lugares: a la izquierda de i, en i o a la derecha de i. Sus sumas dan el total, así que la suma de la derecha es el total menos las otras dos partes. Eso te permite comprobar un índice sin tener que sumar nunca el lado derecho.

¿Se puede resolver Find Pivot Index con dos punteros?

No de forma fiable. Un recorrido con dos punteros que siempre amplía el lado más pequeño supone que añadir un valor hace que un lado sea mayor, lo cual deja de cumplirse en cuanto los valores pueden ser negativos: un lado puede reducirse mientras lo amplías, así que el recorrido puede mover un puntero más allá del pivote real. El método de suma acumulada no hace ninguna suposición sobre los signos y comprueba cada índice.

¿Cuál es el índice pivote de un arreglo con un elemento?

Es 0. Ambos lados del único elemento están vacíos, y un lado vacío suma 0, así que los dos lados son iguales. La solución de suma acumulada devuelve 0 en su primera comparación: el lado izquierdo es 0 y el total menos 0 menos el valor también es 0.

Python

def pivotIndex(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [3, 1, 5, 2, 2]

Esperado

Find Pivot Index

Función

Restricciones

Ejemplos

Pistas

Solución

Suma ambos lados en cada índice

Suma prefija de un arreglo

Suma total y suma acumulada por la izquierda

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares