Как избавиться от использования HashMap в решении задачи, сохранив сложность по памяти O(1)

Что проверяют

Умеете ли вы видеть, откуда в решении берётся дополнительная память, и знаете ли приёмы, которые без неё обходятся. Следом почти всегда спрашивают, чем вы заплатили за экономию: временем, порчей входных данных или ограничением на диапазон значений.

Как отвечать

Начните с уточнения: какие значения лежат во входе, можно ли менять массив, насколько важна скорость. От этого зависит приём:

• массив фиксированного размера: если ключи из заранее известного небольшого набора, например латинские буквы, IntArray(26) с индексом c - 'a' заменяет HashMap<Char, Int>. Это O(1) по памяти только потому, что размер алфавита не зависит от длины входа;
• битовая маска: для признака «встречалось или нет» хватит одного Int или Long, mask or (1 shl (c - 'a'));
• разметка во входном массиве: если числа лежат в диапазоне от 1 до n, посещённый индекс помечают сменой знака у элемента. Работает за O(n) без дополнительной памяти, но портит вход;
• XOR: единственный непарный элемент находится, если прогнать xor по всему массиву, пары взаимно гасятся;
• алгоритм Флойда (черепаха и заяц): поиск повторяющегося числа в массиве из n + 1 элементов со значениями от 1 до n, когда массив трогать нельзя;
• сортировка на месте и два указателя: универсальный вариант, но время растёт до O(n log n).

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

Где спотыкаются

Называют массив размером n или размером «максимальный ключ» решением с O(1). Это O(n) или O(K), константой он становится, только когда размер не зависит от входа.

Предлагают SparseArray или SparseIntArray как замену ради памяти. Они экономят на боксинге и объектах записей по сравнению с HashMap, но память всё равно растёт линейно, асимптотика та же.

Молча портят входной массив знаками или сортировкой. Об этом нужно спросить заранее: в реальном коде массив может переиспользоваться дальше, и такой побочный эффект станет багом.