Given two arrays arr1[] and arr2[] of size N and M (M < N) add all elements of arr2[] in all possible subarrays of arr1[] of size M exactly once. The task is to return the final array arr1[] after performing the above operations.
Examples:
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
Naive Approach: The problem can be solved using linear iteration based on the following idea:
Keep adding all elements of arr2[] in all possible subarrays of size M of arr1[]. There will be exactly N – M + 1 subarrays.
Follow the steps mentioned below to implement the idea:
 Iterate from i = 0 to NM+1:
 Iterate from j = 0 to M:
 Add arr2[j] with arr[i+j.
 Iterate from j = 0 to M:
 Return the final state of arr1[] as the required answer.
Below is the implementation of the above approach.
C++

2 3 4 3 2 20 21 22 23 24 12 11 10 9
Time Complexity: O(N * M)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
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, M1).
Sum from max(1, M – N + i) to min(i, M1) can be calculated using prefix sum in constant time.
Follow the steps below to solve the problem:
 Initializing prefix[] array which will be used to store the sum of all ranges of arr2[].
 Initializing L = max(1, M – N + i) and R = min(i, M).
 Traverse from 1 to N, Adding prefix[R] – prefix[L – 1] in arr[i – 1] .
 print the final array
Below is the implementation of the above approach.
C++

Time Complexity: O(N)
Auxiliary Space: O(M)
Related Articles: