Saltar al contenido

Cuadrados de una lista ordenada

Fácil#two-pointers#merge-from-back~15 min

La misión

Problema

Una lista de enteros está ordenada de forma no decreciente y puede contener valores negativos. Devuelve una lista nueva con el cuadrado de cada valor, también en orden no decreciente. Elevar al cuadrado y luego ordenar toma tiempo O(n log n); el objetivo es O(n) aprovechando el orden que ya tiene la entrada.

Ejemplos

Input:  nums = [-5, -2, 1, 3, 4]
Output: [1, 4, 9, 16, 25]
Por qué: -5 es el valor más pequeño, pero da el cuadrado más grande
Input:  nums = [-7, -3, -2]
Output: [4, 9, 49]
Por qué: todos son negativos, así que los cuadrados salen en orden inverso
Input:  nums = []
Output: []
Por qué: caso límite: no hay nada que elevar al cuadrado

Pistas

0 / 3

Tiempo objetivo
O(n)
Espacio objetivo
O(n)

Restricciones

  • nums is sorted in non-decreasing order
  • values may be negative
  • target O(n) time

¿Lo que te frena es la idea y no el código? Fusionar arrays ordenados lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio