Transformación a Arreglo-Cero I
Sea un arreglo de enteros nums de longitud n y un arreglo 2D queries, donde
Para cada queries[i] :
- Selecciona un subconjunto de índices dentro del rango en
nums - Decrementa los valores en los índices seleccionados en 1
Un arreglo-cero es un arreglo donde todos los elementos son iguales a 0.
Devuelve true si es posible transformar nums a un arreglo-cero despues de procesar todas las consultas secuencialmente, de lo contrario devuelve false.
Ejemplos
Ejemplo 1:
Input: nums = [1,0,1], queries = [[0,2]] Output: true
Explicación:
Para i = 0:
Seleccionar el subconjunto de índices como [0, 2] y decrementar los valores de estos índices en 1.
El arreglo se conviertes [0, 0, 0], que es un arreglo-cero.
Ejemplo 2:
Input: nums = [4,3,2,1], queries = [[1,3],[0,2]] Output: false
Explicación:
Para i = 0:
Seleccionar el subconjunto de índices como [1, 2, 3] y decrementar los valores en estos índices en 1.
El arreglo se convierte en [4, 2, 1, 0].
Para i = 1:
Seleccionar el subconjunto de índices como [0, 1, 2] y decrementar los valores en estos índices en 1.
El array se convierte en [3, 1, 0, 0], que no es un Array Cero.
Soluciones
Python
class Solution:
def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
n = len(nums)
diff = [0] * (n + 1)
for start, end in queries:
diff[start] += 1
if end + 1 < n:
diff[end + 1] -= 1
current = 0
for i in range(n):
current += diff[i]
if current < nums[i]:
return False
return True