Самый частый элемент в объединении массивов

Задача

Найти, сколько раз встречается самый частый элемент в объединении двух отсортированных по возрастанию массивов. Элементы могут повторяться.

Пример

findMaxCount([1, 2, 9, 10], [2, 2, 10]); // => 3

Решение

Оптимальное решение

// Two Pointer Merge (Метод двух указателей)
// Frequency Counting (Подсчет частот)
 
// Временная сложность: O(n + m) - линейная
// Пространственная сложность: O(n + m) - массив merged + объект frequency
 
function findMaxCount(arr1, arr2) {
    // Шаг 1: Объединяем отсортированные массивы
    const merged = [];
    let i = 0,
        j = 0;
 
    while (i < arr1.length && j < arr2.length) { // O(min(n, m)) - где n длина arr1, m длина arr2
        if (arr1[i] <= arr2[j]) {
            merged.push(arr1[i++]);
        } else {
            merged.push(arr2[j++]);
        }
    }
 
    while (i < arr1.length) merged.push(arr1[i++]); // O(n - i) - оставшиеся элементы arr1
    while (j < arr2.length) merged.push(arr2[j++]); // O(m - j) - оставшиеся элементы arr2
    // Суммарно слияние: O(n + m)
 
    // Шаг 2: Подсчитываем частоты
    const frequency = {};
    let maxCount = 0;
 
    for (const num of merged) { // O(n + m) - итерации по объединённому массиву
        frequency[num] = (frequency[num] || 0) + 1;
        maxCount = Math.max(maxCount, frequency[num]);
    }
 
    return maxCount;
}

Альтернативное решение (concat + sort)

// Временная сложность: O((n + m) * log(n + m)) - доминирует операция sort
// Пространственная сложность: O(n + m) - массив merged
 
function findMaxCount(arr1, arr2) {
    // Шаг 1: Объединяем массивы
    const merged = arr1.concat(arr2); // O(n + m) - где n длина arr1, m длина arr2
 
    // Шаг 2: Сортируем
    merged.sort((a, b) => a - b); // O((n + m) * log(n + m)) - сортировка
 
    // Шаг 3: Подсчитываем частоту последовательных элементов
    let maxCount = 1;
    let currentCount = 1;
 
    for (let i = 1; i < merged.length; i++) { // O(n + m) - итерации по объединённому массиву
        if (merged[i] === merged[i - 1]) {
            currentCount++;
            maxCount = Math.max(maxCount, currentCount);
        } else {
            currentCount = 1;
        }
    }
 
    return maxCount;
}