Розв’язуємо задачі на LeetCode. Припущення та оптимізація рішень

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

Усім привіт, мене звати Олексій Михняк, я Software Developer. У цій статті хочу розглянути та разом з читачами розібрати, як можна розв’язувати типові задачі на LeetCode. Беремось за задачу Intersection of Multiple Arrays:

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums sorted in ascending order.

Example 1:

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation:
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation:
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints:

— 1 <= nums.length <= 1000
— 1 <= sum(nums[i].length) <= 1000
— 1 <= nums[i][j] <= 1000
— All the values of nums[i] are unique.

1. Перші припущення

Якщо взагалі не знайомі з підходами до розв’язання задач, то можна спробувати використати Brute Force алгоритм, тобто повний перебір всіх можливих варіантів. Це може бути дуже просто, але він не завжди є оптимальним (таким чином можна розв’язати більшість простих та частину середніх задач).

public class Solution {
   public IList<int> Intersection(int[][] nums) {
       var result = new List<int>();
       // Вибираємо за еталонний перший масив, але можна було б вибрати будь-який інший.
       // Можна спробувати вибрати масив з найменшою кількістю елементів,
       // але в найгіршому випадку всі масиви будуть мати рівну кількість елементів.
       var etalon = nums[0];
       // Перебираємо всі елементи еталонного масиву
       // Якщо в нас існує багато вкладених циклів, то краще винести їх в окремі методи, оскільки не можемо ефективно використовувати break/continue/return statements
       foreach(var n in etalon)
       {
           // Перевіряємо чи елемент існує в кожному масиві
           if(ContainsInAll(nums, n))
           {
               result.Add(n);
           }
       }
      
       // Сортуємо та повертаємо результат
       result.Sort();
       return result;
   }
  
   // Цей метод повертає true, якщо масив масивів array[][] містить елемент n
   private bool ContainsInAll(int[][] array, int n)
   {
       // Перебираємо всі масиви
       foreach(var a in array)
       {
           // Якщо ми не знайшли елемент n в поточному масиві, то повертаємо false
           if(!a.Contains(n))
           {
               return false;
           }
       }
      
       // Якщо ми перебрали всі масиви і в кожному з них знайшли елемент n, то повертаємо true
       return true;
   }
}

Результат за посиланням на LeetCode.

Аналіз

  • Часова складність: O(M×N) + O(K×log(K)), де M — кількість елементів в масиві з мінімальною довжиною, N — загальна кількість всіх елементів в усіх масивах, K — кількість елементів, які містяться в кожному масиві. Оскільки час сортування O(K×log(K)) менший за час перебору елементів O(M×N), то в кінцевому результаті ми отримуємо O(M×N).
  • Пам’яткова складність: O(K), якщо ми не враховуємо вхідні дані, а K — кількість елементів, які містяться в кожному масиві.

2. Оптимізація

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

All the values of nums[i] are unique

то можемо порахувати кількість кожного елементу в кожному масиві і використовувати цю інформацію для вирішення задачі.

public class Solution {
   public IList<int> Intersection(int[][] nums) {
       var result = new List<int>();
       // в C# є Dictionary, який реалізовує структуру даних Map (хеш-таблиця)
       var counter = new Dictionary<int, int>();
      
       // проходимось мо всім значенням в усіх масивах
       foreach(var array in nums)
       {
           foreach(var n in array)
           {
               // C# повертає KeyNotFoundException помилку, якщо намагаємось отримати ключ, якого немає в хеш-таблиці
               // в інших мовах програмування цей запис може виглядати як:
               // counter[n] = counter[n] + 1; or counter[n] += 1; or counter[n]++;
               counter[n] = counter.GetValueOrDefault(n, 0) + 1;
           }
       }
      
       foreach(var pair in counter)
       {
           if(pair.Value == nums.Length)
           {
               result.Add(pair.Key);
           }
       }
      
       // Сортуємо, оскільки хеш-таблиця не гарантує результат у відсортованому виді та повертаємо результат
       result.Sort();
       return result;
   }
}

Результат за посиланням на LeetCode.

Аналіз

  • Часова складність: O(N) + O(K×log(K)) -> O(N×N) + O(K×log(K)), де N — кількість елементів у всіх масивах, K — кількість елементів, які містяться в кожному масиві. Час вставки елемента в хеш-таблицю O(1), але в найгіршому випадку може бути O(N), тому час за який ми проходимо всі елементи може коливатися від O(N) до O(N×N).
  • Пам’яткова складність: O(L) + O(K), де L — кількість унікальних елементів у всіх масивах, K — кількість елементів, які містяться в кожному масиві. Якщо взяти найгірший випадок, коли всі елементи унікальні, то L = N, та в нас всього один масив, K = N, тоді пам’яткова складність буде O(N) + O(N) = 2×O(N) = O(N). де N — кількість елементів у всіх масивах.

2. Оптимізуємо далі

Ми вже змогли оптимізувати часову складність (для найкращого результату) з квадратної залежності в лінійну, але збільшили пам’яткову складність. Завжди потрібно уважно передивлятися початкові умови задачі, вони можуть підказати, як можна змінити алгоритм:

— 1 <= nums.length <= 1000
— 1 <= sum(nums[i].length) <= 1000
— 1 <= nums[i][j] <= 1000

Оскільки ми маємо обмеження на кількість елементів (1000 — це дуже мале значення, яке можна зберігати в пам’яті), та обмеження на значення самих елементів, особливо зверніть увагу що всі значення > 0, зазвичай це свідчить, що їх можна використовувати як індекси масиву. Тому ми можемо використовувати масив замість хеш-таблиці для зберігання кількості кожного елемента, а потім пройтися по ньому і знайти елементи, які містяться у всіх масивах.

public class Solution {
   public IList<int> Intersection(int[][] nums) {
        var result = new List<int>();
        // в C# масиви заповнюються нулями, тому нам не потрібно про це турбуватися
        var counter = new int[1000]; // 1 <= nums[i][j] <= 1000
        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = 0; j < nums[i].Length; j++)
            {
                var value = nums[i][j];
                var index = value - 1; // щоб не зберігати нульовий пустий елемент, перетворюємо значення в індекс
                counter[index] = counter[index] + 1;
            }
        }
       
        for (int i = 0; i < counter.Length; i++)
        {
            if (counter[i] == nums.Length)
            {
                result.Add(i + 1); // перетворюємо індекс назад в значення
                // оскільки ми проходимо всі значення від 0 до 1000 то вони будуть додані у відсортованому порядку
            }
        }        
       
        return result;
   }
}

Результат за посиланням на LeetCode.

Аналіз

  • Часова складність: O(N) + O(1000) = O(N) + O(1) = O(N), де N — кількість елементів у всіх масивах.
  • Пам’яткова складність: O(1000) = O(1), оскільки ми завжди будемо мати масив з фіксованою кількістю елементів, оскільки ми залежимо не від довжини масивів, а від обмеження на значення елементів.

Це типове рішення з використанням лічильника, зазвичай використовуються в задачах на пошук унікального елементу або символів в рядку. Лайфхак: якщо використовуються тільки латинські літери, то як лічильник можна використовувати Int32 або ж Int64 за необхідності та працювати з бітовими масками — це дозволить максимально оптимізувати пам’яткову складність.

Що робити якщо в кожному масиві можуть бути дублікати

Знаючи існуюче рішення, можна умову підігнати під нього, тобто типовою є ситуація, коли перед вирішенням задачі відбувається «очистка» даних за O(N). Знаходимо дублікати за допомогою хеш-таблиці або ж окремого лічильника, і якщо хочемо економити пам’ять, то змінюємо вхідні дані, наприклад, замінюючи дублікати на 0, і потім не враховуємо 0 в рішенні.

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

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

Ще пишу технічні новини у своєму Telegram-каналі, кому цікаво — підписуйтесь. Дякую за увагу!

👍ПодобаєтьсяСподобалось8
До обраногоВ обраному8
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Літкод трохи палиться отими обмеженнями типу

1 <= nums[i][j] <= 1000

. Я, коли таке бачу, то перше, що думаю, що треба було б масив зробити на кожну цифру з цього діапазану. Далі автоматично виникає питання «а що б такого в цей масив покласти?» — ну і часто задача на цьому вже і вирішена.

так дуже важливо дивитися на обмеження, вони допомагають. Але якщо ти перший раз розв’язуєш задічі типу таких, то все здається складним, а просто потрібно набити руку і далі все піде :)

На контестах дуже часто від обмежень і починають шукати алгоритм, наприклад
N <= 100_000 — скоріше за все щось типу O(N*logN) наприклад сортування
N <= 1000, M <= 1000 — скоріше за все O(N*M) наприклад динаміка

О, я то даю на інтерв’ю. Коли на проді в кожному з масивів навіть по 100,000 записів і ще й алгоритм порівняння складний, то різниця в часі виконання може становити пару хвилин проти декількох годин в наївному рішенні.

Якось так на С++ , 3мс та 11.3Мб памяті. Але літкод цікаво міряє, раз 3 мс, раз 8; так само і по памяті ±200кб при різних замірах(
imgur.com/Ml3mZwn

так, мені це теж не подобається, в C# там взагалі скакає, особливо по пам’яті один раз ти кращий за 100%, наступний запуск і вже 40% (це умовні цифри)

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

Доречі сподобався твій варіант, щоб використати вхідний масив для відповіді, це теж один з прийомів по оптимізації та вирішенню задач на LeetCode

Дякую за вашу статтю. Буде цікаво подивитися розвязок інших задачок.

можна було б залишити перший елемент нульовим (розмір [1001]), тоді не доведеться кожен раз виконувати віднімання для отримання індексу.

нашо ви leetcode пiарите дурнi

а в чому проблема з

leetcode

?

Задача цікава своєю простотою, аж покодити трохи захотілося :)

Знаходимо дублікати за допомогою хеш-таблиці або ж окремого лічильника

Що саме маєте на увазі під окремим лічильником? Мені ось таке рішення спадає на думку — leetcode.com/...​ys/submissions/890859113

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

Можна і без хеш-таблиці — відсортувати всі масиви, зробити ітератор на кожний, і потім йти рекурсивно через список ітераторів порівнюючи поточні елементи. Без сортувань складність буде лінійна і при цьому використовується мінімум додаткової пам’яті якщо правильно реалізувати. Дублікати теж прибирає. Сортування, звісно, додають багато складності, але я пару бенчмарків зробив на рандомнії матриці 1000×1000 — працює трохи шивдше за хеш-таблицю. Тим не менш, думаю в едж-кейсах через сортування буде працювати гірше за хеш — якщо буде натхнення, ще пограюсь. Ось бігла реалізація ідеї, її явно можна покращити -
leetcode.com/...​ys/submissions/890870561

Результати бенчмарків ось такі виходять:

|                      Method |       Mean |      Error |     StdDev |     Gen0 |  Allocated |
|---------------------------- |-----------:|-----------:|-----------:|---------:|-----------:|
|      IntersectionBruteforce | 206.390 ms | 12.6671 ms | 18.9595 ms |        - |    8.56 KB |
|      IntersectionDictionary |  16.195 ms |  0.3250 ms |  0.4661 ms |        - |   79.71 KB |
|          IntersectionLinear |   1.938 ms |  0.0312 ms |  0.0448 ms |   3.9063 |   12.16 KB |
| IntersectionLinearAdvanced  |   1.858 ms |  0.0583 ms |  0.0873 ms | 328.1250 | 1011.16 KB |
|       IntersectionRecursive |  14.366 ms |  0.2361 ms |  0.3386 ms |        - |   47.34 KB |
Що саме маєте на увазі під окремим лічильником?

так як в посиланні і мав на увазі, що можна створити загальний лічильник

var counter = new int[1000]
та окремо створювати на кожний масив:
var tempCounter = new int[1000]
тут вже потрібно дивитися що краще і які можуть бути вхідні масиви, якщо сказано що кількість масивів дуже велика, а їхній різмір маленький, то можна подумати і про хеш сет для знаходження дублікатів, а масив для пошуку шаблонів після очистки очистки від дублікатів, або ж проходитись по тимчасовим лічильника і очищувати їх, щоб не виділяти багато пам’яті.

якщо це реальна практична задача, то тут метод научного тику покаже що буде працювати краще, а якщо для співбесіди, то головне це порозмірковувати коли що буде краще :)

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

ми ж розуміюємо що тут головне описати складність алгоритму, а для сорвування це мінімум N*Log(N), а вставка в хеш таблицю O(1), але оскільки ми ще читаємо перед цим то час вичитки різниться від O(1) до O(N) якщо буде багато ключів з однаковим хешем. Оскільки в нас обмежений діапазон і це цілі числа те що всі хеші будуть однакові дуже малоймовірно, тому ріст буде O(N) для запису (з попередньою вичиткою) для всіх значень що менше N*Log(N).

Те що O(N) краща складність за N*Log(N) не дає нам гарантії що O(N) працюватиме швидше, це говорить що після досягнення якоїсь критичної точки цей алгорим буде працювати швидше.

Якщо буде час, можеш збільшити кількість елементів до 1_000_000? а діапазон залишити як зараз 1000 і глянемо як зміниться бенчмарка. Якщо що можна писати в телеграм (в статті є посилання)

ще додай в Dictionary відразу довжину 1000 (можна окремим методом для бенчмарки), це прибере непотрібні перебалансування при додаванні нових елементів і тоді час вставки і вичитки буде завжди O(1)

var counter = new Dictionary<int, int>(1000);

Коментар порушує правила спільноти і видалений модераторами.

дуже дякую за статтю. на майбутнє було б цікаво почитати розбір інших алго задач.
єдине питання, у прикладі рішення з хеш-мапою, Space complexity хіба не буде зводитись теж до O(1000) -> O(1)? так як в мапі ми будемо зберігати тільки унікальні елементи, а за умовою їх у нас до 1000

Я так розумію це про ось цю частину:

Пам’яткова складність: O(L) + O(K), де L — кількість унікальних елементів у всіх масивах, K — кількість елементів, які містяться в кожному масиві. Якщо взяти найгірший випадок, коли всі елементи унікальні, то L = N, та в нас всього один масив, K = N, тоді пам’яткова складність буде O(N) + O(N) = 2×O(N) = O(N). де N — кількість елементів у всіх масивах.

Я тут показую зазвий якою буде пам’яткова складність для хеш-мапи, якщо не звернути увагу на те що ми маємо унікальні значення в межах до 1000 тоді дійсно буде O(N), але врахуючи що в нас тільки 1000 унікальних елементів тоді, так це зводиться до O(1000) = O(1).

Типово що для хеш-мапи це O(N) а для масиву (чи просто int32/int64) це О(1).

Дякую що звернув увагу, це потрібно підкреслити.

на майбутнє було б цікаво почитати розбір інших алго задач.

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

Підписатись на коментарі