Java Memory limit exceeded на олимпиадном программировании?

Одномерный массив и есть своеобразный словарь где индекс - ключ. То что он у тебя фиксированный и будет на 2ккк размера суть не страшно. В этом плане можешь посмотреть на свой же второй способ. По поводу не сильно эффективней, я ещё когда давал ответ на коленке собирал твой первый способ и заменив мапу и объекты на массив с примитивами, даже без дополнительных манипуляций с убиранием стримов, решил проблему OOME (ошибка падает на строчке с new ArrayList<>(eachCount.entrySet()), но конечно смотри сам.