Розв’язуємо задачі на 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-каналі, кому цікаво — підписуйтесь. Дякую за увагу!