Добавить элементы одного массива во все подмассивы размера M другого массива

Даны два массива arr1[] и arr2[] размера N и M (M < N), добавьте все элементы массива arr2[] во все возможные подмассивы массива arr1[] размера M ровно один раз. Задача состоит в том, чтобы вернуть итоговый массив arr1[] после выполнения вышеуказанных операций.

Примеры:

Input: arr1[] = {1, 1, 1, 1, 1}, arr2[] = {1, 1, 1}
Output:  2 3 4 3 2
Explanation: There are exactly 3 subarrays of size M in arr1[] 
adding corresponding elements of arr2[] in first subarray from element 1 to 3. arr1[] becomes {2, 2, 2, 1, 1}
adding corresponding elements of arr2[] in second subarray from element 2 to 4. arr1[] becomes {2, 3, 3, 2, 1}
adding corresponding elements of arr2[] in the third subarray from elements 3 to 5. arr1[] becomes {2, 3, 4, 3, 2}

Input: arr1[] = {1, 2, 3, 4, 5}, arr2[] = {10}
Output: 11 12 13 14 15

Наивный подход: проблему можно решить с помощью линейной итерации, основанной на следующей идее:

Keep adding all elements of arr2[] in all possible subarrays of size M of arr1[]. There will be exactly N – M + 1 subarrays.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Итерация от i = 0 до N-M+1:
  • Итерация от j = 0 до M:
    • Добавьте arr2[j] с помощью arr[i+j.
• Верните конечное состояние arr1[] в качестве требуемого ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * M)
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход может быть оптимизирован на основе следующей идеи:

This can be observed every element i of arr1[] will have some range of elements from arr2[] that gets added.
For example.
in case of arr1[] = {0, 0, 0, 0, 0}, arr2[] = {1, 2, 3}
element 1 will have 1 in its sum. Range of elements that got added from arr2[] is [0, 0].
element 2 will have 1 and 2 in its sum. Range of elements that got added from arr2[] is [0, 1].
element 3 will have 1, 2, and 3 in its sum. Range of elements that got added from arr2[] is [0, 2].
element 4 will have 2 and 3 in its sum. Range of elements that got added of arr2[] is  [1, 2].
element 5 will have 3 in its sum. Range of elements that got added of arr2[] is  [2, 2].

Observation: every element ‘i’ will have sum of elements of arr2[] from max(0, M – N + i) to min(i, M-1).
Sum from max(1, M – N + i) to min(i, M-1) can be calculated using prefix sum in constant time. 

Выполните следующие шаги, чтобы решить проблему:

• Инициализация массива prefix[] , который будет использоваться для хранения суммы всех диапазонов arr2[].
• Инициализация L = max(1, M – N + i) и R = min(i, M).
• Переход от 1 к N, добавление префикса [R] – префикса [L – 1] в arr[i – 1] .
• распечатать окончательный массив

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(M)

Статьи по Теме:

• Введение в массивы — учебные пособия по структуре данных и алгоритмам
• Массив сумм префиксов — реализация и приложения в соревновательном программировании