Вирішуємо задачу з Leetcode: Top K Frequent Elements

Привіт! Мене звати Данило Толмачов, я Full-Stack розробник і Team Lead у Techstack. Думаю, багато хто з нас розв’язує задачі на Leetcode: для розваги, розвитку або щоб потрапити на роботу в FAANG. Завдань різної складності на Leetcode дуже багато. У цій статті я покажу декілька варіантів розв’язання задачі Top K Frequent Elements.

Стаття буде корисною тим, хто вивчає алгоритми, розвиває логічне мислення або готується до співбесіди на позицію будь-якого рівня.

У чому суть задачі

Top K Frequent Elements — це універсальна базова алгоритмічна задача, яка відзначена на Leetcode середнім рівнем складності. Гадаю, вона буде корисною багатьом, оскільки майже всі працюють з масивами і знають, що таке хешмеп. Подивімось докладніше, у чому її суть.

Задача: 347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than Θ(n log(n)), where n is the array’s size.

Підхід до розв’язання

Перш ніж переходити до розв’язання, розберемось, як логічно підходити до роботи з такими завданнями, з чого починати і як діяти:

Крок 1: Розберіться, яке перед вами завдання. Для цього починаємо з читання вимог. Що в нас є з умов:

1) integer array nums на вході та integer k — звичайне, недробове, число. Це найчастіше зустрічаються елементи на вході.

2) Відповідь може бути дана в будь-якому порядку.

Крок 2: Вивчіть приклади. Вони допоможуть зрозуміти, що конкретно потрібно зробити. У цій задачі прикладів два:

Example 1:

Input: nums = [1,1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

З прикладів та умови стає зрозуміло, що у нас є масив nums, і нам потрібно знайти два найпопулярніші елементи в ньому.

Крок 3: Не пропускайте обмеження задачі. Це часта помилка, яка призводить або до неправильних, або до неоптимальних рішень. Конкретно в цьому завданні у нас є обмеження на розмір і значення вхідних та вихідних даних, а також розмір масиву і кількість необхідних елементів:

1 <= nums.length <= 10⁵

-10⁴ <= nums[i] <= 10⁴

k is in the range [1, the number of unique elements in the array].

It is guaranteed that the answer is unique.

Звідси робимо висновок, що значення елементів можуть бути як від’ємними, так і додатними, а також — що відповідь завжди унікальна.

Як мислити, щоб розв’язати цю задачу

Перш ніж перекладати розв’язання мовою програмування, потрібно зрозуміти, як мислити загалом. Краще один раз добре подумати, ніж багато разів рефакторити і переписувати код. Тому раджу спочатку виробити алгоритм, а потім братися за написання коду.

Не забувайте, що мова — це просто інструмент, який не вирішує за вас, а допомагає донести комп’ютеру ваше рішення.

Як можна діяти в цьому випадку? Починаємо розбирати алгоритм для першого прикладу:

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Запитайте себе, які елементи зустрічаються найчастіше. Відповідь: 1 і 2. Як ми до цього прийшли? Розкладаємо своє мислення на атомарні операції, які можна перекласти мовою програмування.

Уявімо, що в нас є блокнот, куди ми записуємо кожен елемент, проходячи масивом. Звертаємо увагу, скільки разів кожен із них зустрічався. Наприклад, дивимося на перший елемент. Це цифра один — записуємо, що одиниця зустрілася один раз. Переходимо до другого елемента: знову одиниця — збільшуємо лічильник цифри один та ін. І тоді наша таблиця з нотатками має такий фінальний вигляд: одиниці трапляються тричі, двійки — двічі, трійки — один раз.

За умовами з цього списку потрібно вибрати топ n-елементів (ті, які зустрічаються найчастіше). У цьому випадку це k, і k=2.

Потрібно розуміти, що як приклад подано найпростіші речі. Умови, які даватимуться потім, не обов’язково з’являтимуться в тому ж порядку і кількості. В іншому масиві тих самих трійок могло бути більше, а двійок менше, або цей масив міг би розширитися і всіх елементів стало б більше. Тоді ми б напевно не знали, що саме потрібно брати як топ n-елементів. Звідси з’являється потреба відсортувати масив.

Закінчивши розбиратися з алгоритмом, переходимо до перетворення його на код. Готовий алгоритм можна написати будь-якою мовою. І навіть усередині однієї мови існує безліч варіацій кінцевої реалізації. Я буду використовувати JavaScript, і покажу два варіанти рішення, розуміючи, що вони не є єдиними.

Розв’язання 1

Перш ніж переходити безпосередньо до розв’язання, хочу зазначити, що воно навмисно було розраховане без урахування follow up — тієї частини завдання, яку часто не беруть до уваги. Без неї ми зможемо спочатку отримати рішення, що працює, а потім перейдемо до оптимізації, враховуючи follow up.

Отже, перше розв’язання:

const map = {}
nums.forEach(n => {
  map[n] = map[n] ? ++map[n] : 1
})

const keysSorted = Object.keys(map).sort((a,b) => {return map[b]-map[a]})

return keysSorted.slice(0, k).map(key => parseInt(key))

Тепер давайте покроково розбиратися, як працює це рішення.

1. Наповнюємо map

В основі розв’язання лежить змінна map, яка є об’єктом. Після створення map ми запускаємо цикл по масиву вхідних цифр nums. Так ми починаємо підрахунок кількості цифр, що зустрічаються. Ім’я кожної властивості об’єкта — це цифра, а значення цієї властивості — кількість разів, скільки ця цифра зустрілася нам на шляху. Усе це ми присвоюємо в map.

2. Переходимо до сортування ключів (keysSorted)

Наступним етапом оголошуємо змінну keysSorted. За підсумком проходження масивом ми повинні отримати всі ключі об’єкта map, які в ньому записані. Після чого починаємо сортування ключів від більшого до меншого залежно від їхніх значень.

Зрештою отримуємо відсортований масив keysSorted, який міститиме імена всіх ключів, відсортованих за частотою їхньої появи в оригінальному масиві nums: [«1», «2», «3»].

Є безліч хороших сортувань, але оптимальні з них у середньому показують результат за time complexity: Θ(n log(n)). Це лінійно-логорифмічна залежність.

3. Проводимо слайс масиву

На наступному етапі потрібно зробити слайс масиву і відрізати k-елементи, а потім привести їх до parseInt. Це пов’язано з тим, що всі ключі в JS обробляються як рядки, а нам потрібно привести результат до цифр. Так у нас запускається другий цикл за k-елементами, які були відрізані.

4. Оцінюємо складність цього алгоритму

Для цього попрацюємо з Big O notation, який добре допомагає з оцінкою складності, зокрема, time complexity та space complexity. Big O notation вказує на те, що якщо в алгоритмі є цикл по всіх елементах вхідного масиву, то це пряма залежність від об’єму вхідних даних і складність O(n). Відповідно, хоча б один раз ми точно відвідаємо цей елемент, а O дорівнюватиме O(n). Звідси випливає, що n-раз ми точно пройдемося по кожному з елементів.

Перший цикл: O(n)

Другий цикл (за сортуванням): Θ(n log(n))

Третій цикл: O(k)

Далі залучаємо математику й оцінку складності розв’язання:

O(n) + O(n log n) + O(k) => O(n log n)

Що цікавого в розв’язанні 1

У ньому n — це довжина вхідних даних. У нашому випадку довжина nums — шість, але кількість ключів, які ми сортуємо, — три, тому що це унікальні цифри.

Це дуже простий приклад. Ми повинні розуміти, що в гіршому варіанті можна отримати цілий масив унікальних чисел. Відповідно, розмір map буде набагато більшим.

Що за результатами

Перший сабмішн виконано за 85 мс і 43 мб пам’яті, а це на 98% краще за інші рішення.

Розв’язання 2

Здавалося б, усе вже вийшло чудово, але є одна важлива деталь — під час першого розв’язання ми не врахували follow up:

«Your algorithm’s time complexity must be better than Θ(n log(n)), where n is the array’s size».

Розв’язання, яке ми отримали, не відповідає follow up, тому що базується на Θ(n log(n)), тоді як воно має бути кращим. Відповідно, виникає питання, як зробити розв’язання кращим, ніж Θ(n log(n))?

Оцінка складності попереднього розв’язання показала, що його слабким місцем було сортування. Отже, у новому розв’язанні його потрібно переглянути. Ми не будемо відмовлятися від підходу зі створенням map, але змінимо підхід до сортування цифр.

Яку логіку тут можна використовувати? Пропоную виходити з того, що у нас є масив із шести елементів. Зробимо додатковий «список» рівним довжині оригінального масиву (nums): тобто, виходячи з першого прикладу, nums.length = 6. Відповідно, список частот міститиме цифри від одного до 6.

У цьому підході індекси відповідатимуть за частоту появи цифр, а значення, які зберігаються за цими індексами — це цифри. Виходячи з цього, заповнимо «список» частот: ми бачимо одиницю і бачимо, що її частота 3 — ставимо її в трійку; бачимо двійку — ставимо в двійку; бачимо трійку — ставимо в одиницю.

Принцип роботи тут — від зворотного: коли потрібно видавати топ k-елементів, ми будемо звертати увагу на частоту.

Після заповнення «списку» з частотами, справа залишилася за малим — потрібно дістати з нього k найпопулярніших елементів. Проходимося масивом частот у зворотному порядку і дістаємо значення з нього, зберігаючи їх у наш результуючий масив доти, доки розмір фінального масиву не дорівнюватиме k. Тепер наш result aray = k. На цьому можна закінчувати вправу.

Переносимо цю логіку в код і отримуємо:

const map = {}
nums.forEach(n => {
  map[n] = map[n] ? ++map[n] : 1
})

let result = []
const frequencies = []
for (const [digit, appearance] of Object.entries(map)) {
  if (frequencies[appearance]) {
    frequencies[appearance].push(parseInt(digit))
  } else {
    frequencies[appearance] = [parseInt(digit)]
  }
}

for(let i = nums.length; result.length < k; i--) {
  result = result.concat(frequencies[i] || [])
}

return result

Перша частина із заповненням об’єкта map не змінилася, переносимо з минулого рішення.

Новий підхід замість сортування, як було раніше, створюємо масив frequencies, і, проходячи по об’єкту map в циклі, заповнюємо частоти відповідними значеннями.

Тепер нам потрібно забрати всі елементи з frequencies array. Для цього знову перевіряємо масив: переходимо в 6 — нічого немає, йдемо далі. Ініціалізуємо змінну індексів з максимальним розміром nums. Потім дістаємо цифри з частотного масиву, доти, доки їх не буде k штук. Ми рухаємося у зворотному порядку, щоб забрати ті, що зустрічаються найчастіше. У гіршому випадку, якщо всі діджити унікальні і k = length array, нам потрібно буде пройти по всьому frequence array.

За допомогою такого розв’язання ми отримуємо результат за 100 мс з використанням 48 мб пам’яті.

Якщо вірити умовам задачі, ми повинні були отримати ефективніше рішення. Звідси запитання:

Якщо складність цього алгоритму дорівнює o(n), а попередня складність Θ(n log(n)), то чому o(n), що мала б бути простішою і швидшою за перший, виявилася повільнішою?

Можливо, останній код неоптимальний і виконує надлишкові операції. Що думаєте з цього приводу? Обговорюймо в коментарях.

Що маємо в підсумку

Наостанок хочу тільки ще раз нагадати, що будь-яке завдання часто має кілька варіантів розв’язання: більш/ менш складні, більш/ менш ефективні. Важливо те, яку мету ви переслідуєте в пошуку рішення. Тому я б радив починати з уточнення цілей.

Запитайте інтерв’юера на співбесіді або клієнта під час виконання завдань, чого вам потрібно досягти в підсумку. Так ви зможете уникнути надмірного ускладнення або, навпаки, спрощення. Оверінжиніринг нікого не вразить, якщо досягти тієї самої мети можна простішим способом.

Друге, що хочеться ще раз проговорити, — уважно читайте реквайерменти. Найчастіше в них уже відразу прописано все, що потрібно для вашого рішення. Прочитайте все, що вам дано, і враховуйте це при побудові рішення.

І останнє — не недооцінюйте алгоритми. Вони допомагають підтримувати жвавість розуму і помічати патерни, які допоможуть у розв’язанні складніших завдань. Алгоритми лежать в основі будь-якої програми. Що краще ви розумітимете основи, то кращим буде ваш код.

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті