Количество одинаковых элементов в массиве JS

Короткий ответ. Словарь частот хранит каждое значение и число его появлений, а строит его один проход. Он нужен, когда в условии есть «сколько раз», «самый частый», «дубликат», «анаграмма» или «уникальный». Время O(n), память O(k) для k разных значений. Когда счётчик упал до нуля, ключ надо удалить.

Сигналы

Тянись за ним, когда в условии есть что-то из этого.

«Сколько раз», «самый частый», «дубликат», «анаграмма», «уникальный», «не меньше k вхождений».

Всё это про количества, а не про позиции. Вот и признак.

Нет порядка в вопросе, обычно нет его и в ответе.

Четыре задачи, которые он закрывает

Анаграммы. Две строки анаграммы, когда их счётчики совпадают. По проходу на каждую, потом сравнение.

O(n) и без сортировки.

Первый неповторяющийся символ. Посчитал за один проход. Прошёл строку снова и вернул первый со счётчиком 1.

Два прохода. Порядок возвращается на втором.

Top-k самых частых. Посчитал, потом взял k наибольших счётчиков кучей. Подсчёт O(n), куча n log k.

Мажоритарный элемент. Посчитал, проверил, есть ли счётчик больше n/2.

Красивое решение за константную память существует, это голосование Бойера-Мура. Версию со счётчиками всё равно пиши первой.

Вариант на массиве

Маленький известный алфавит не нуждается в словаре. Выбрасывай его.

Строчные латинские буквы это 26 ячеек.

Массив по коду символа обгоняет словарь и по скорости, и по памяти. Память становится O(1).

Массив обгоняет словарь и для цифр, и для значений до 10⁶. Какой вариант разрешён, скажут ограничения.

Счётчики внутри окна

Паттерн становится куда полезнее, как только счётчики двигаются.

Ведёшь окно по строке. Добавляешь входящий символ, убираешь выходящий.

Словарь описывает только текущее окно.

«Самая длинная подстрока не более чем с 2 разными символами» становится одним проходом.

Рядом держишь одно число. Сколько сейчас разных ключей в словаре.

Число разных ключей проверяет условие цикла.

Баг, который пишут все

Окно сжимается, ты уменьшаешь счётчик. Он дошёл до нуля, а ключ остался.

Словарь говорит «3 разных символа», хотя их 2. Условие цикла тихо неверное.

На коротких тестах всё проходит. Это худшая часть.

Счётчик упал до нуля, удаляй ключ. Каждый раз.

Ещё два момента.

Отсутствующий ключ читается как undefined, а не 0. Значение по умолчанию пиши явно.

Обычный объект в JavaScript превращает ключи в строки. Числа и строки сталкиваются. У Map этого нет.

Сколько это стоит

Время O(n), один проход. Память O(k), где k это число разных значений.

Про память скажи вслух на собеседовании.

Подсчёт выглядит бесплатным. На большом входе это копия всех разных значений.

Где это в треке

В AlgoPath словарь частот стоит на шаге 18. Дальше два указателя и скользящее окно, оба на него опираются.

Почему словарь, а не массив, разобрано в статье множество, словарь или массив, а что под ним внутри в как работает хеш-таблица.

Первые 33 шага бесплатные.