977. Squares of a Sorted Array

Суть задачи в том ,чтобы возвести все числа входного массива в квадрат и вернуть их в отсортированном порядке. Задачу нужно решить за O(n) по времени.

Мне пришла интересная идея ,как ее решить. Классическое решение строится на базе 2 указателей ,но я решил иначе:

Возводя числа в квадрат я решил сохранять их в хешмапе ,где ключи - это сами числа ,а значения - кол-во раз ,сколько это число встречалось ,тк по условию могут быть дубликаты. Далее я делаю обход по хешмапе ,причем в JavaScript ключи итерируются по порядку возрастания их символьных кодов. Тк ключи представляют собой строки ,например ключ 10 - это совокупность 2 символов с кодами 49 и 48 соответственно для символов '1' и '0'. Таким образом перебирая ключи у объекта { 0: null, 1: null } я могу быть уверен ,что движок обойдет их по возрастанию ,и сначала будет 0 ,потом 1. Тоже верно для любых положительных чисел ,как мне кажется.

Получается 2 цикла ,где первый - O(n) ,а второй O(k) ,где k может быть меньше n при наличии дубликатов. Наличие 2 рядом стоящих циклов не влияет на класс сложности ,поэтому итоговую временную сложность можно оценить как O(n). По памяти будет тоже O(n) несмотря на то ,что я сохраняю 2 структуры. Берем снова одну с наибольшей оценкой ,а это O(n).

Посмотрев популярные решения ,не нашел такого ,что интересно. Но по сути решение это скорее специфичное может быть для языка. Я не знаю ,как на других языках происходит перебор ключей ,и работают ли там такие правила ,но например с Map такое бы уже не прокатило.

Эталонное решение подразумевает наличие 2 указателей. Я не сильно в нем разобрался ,сходу мне оно кажется даже странным и не очень понятным. Разберу его чуть позже.