Задача Яндекса.
Достаточно старая задача, но сейчас стала набирать обороты.

Задача: Дается массив целых и уникальных чисел, ваша задача сжать этот массив, например был у вас массив
-3, -10, 1, -2, 2, 3, 5
то после сжатия ваш массив превращается в
[-10], [-3, -2], [1, 3], [5].
(Я думаю на примере можно понять что просят сделать)
Вывод может быть необязательно в отсортированном виде, то есть вывод
[-3, -2], [1, 3], [-10], [5] тоже считается корректным.

Решение: (если подумал отсортировать массив то лучше посмотреть разбор)


Конечно легче всего массив отсортировать и дальше двумя указателями решить. Такой алгоритм будет работать за n*logn. Такое решение не примут на собесе.

И вот как решать за O(n).
Пройдемся по массиву и запишем их всех в словарь. То есть ключом будет элемент в массиве, а значением 1.

Теперь будем делать следующий алгоритм пока словарь не станет пустым.

Пусть зафиксировали ключ key. Мы как и в двух указателей будем искать такие максимальные r, l, что все числа [key-l, key+r] есть в словаре. Опять таки l, r ищутся очень просто. Вы делаете l=r=0, дальше смотрите есть ли в словаре ключ key+r, если есть то увеличиваете r, иначе останавливаетесь, аналогично для l.
Числа которые нашли стоит удалить из словаря и повторить алгоритм заново.

Время работы алгоритмы O(n).

Если наберет много реакций сегодня выложу код.