The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Question

Given an array A, your task is to output an array B of the same length, by applying the following transformation:

 - For each i from 0 to N - 1 inclusive, B[i] = A[i - 1] + A[i] + A[i + 1].
 - If an element in the sum A[i - 1] + A[i] + A[i + 1] does not exist, use 0 in its place.
 - For instance, B[0] = 0 + A[0] + A[1].

N is the number of elements in the array.

Example:

For A = [4, 0, 1, -2, 3]:

 - B[0] = 0 + A[0] + A[1] = 0 + 4 + 0 = 4
 - B[1] = A[0] + A[1] + A[2] = 4 + 0 + 1 = 5
 - B[2] = A[1] + A[2] + A[3] = 0 + 1 + (-2) = -1
 - B[3] = A[2] + A[3] + A[4] = 1 + (-2) + 3 = 2
 - B[4] = A[3] + A[4] + 0 = (-2) + 3 + 0 = 1

So, the output should be solution(A) = [4, 5, -1, 2, 1].

Employ a time complexity of O(N) and a space complexity of O(N).

Note:

Consider the expression:

    A[i - 1] + A[i] + A[i + 1]

In the evaluation of, A[-1] + A[0] + A[1], the value A[-1] should not exist, because the index -1 is out of bounds.
In the evaluation of, A[N-2] + A[N-1] + A[N], the value A[N] should not exist, because the index N is out of bounds.

These are the only two edge cases.

Solution

Just apply the statement,

    B[i] = A[i - 1] + A[i] + A[i + 1]

in a for-loop, taking into consideration, the two edge cases above. The program is (read through the code and comments):

    #include <stdio.h> 

    int solution(int A[], int N) {
        int B[N];
        for (int i=0; i < N; i++) {
            B[i] = A[i];    //for A[i] 

            if (i > 0)    //to avoid A[-1]
                B[i] = B[i] + A[i - 1];

            if (i < N-1)    //to avoid A[N]
                B[i] = B[i] + A[i + 1];
        }
        
        //Output 
        for (int i=0; i < N; i++)
            printf("%i, ", B[i]);
        printf("\n");
    }

    int main() 
    { 
        int A[] = {4, 0, 1, -2, 3};
        int N = sizeof(A) / sizeof(A[0]);    //divide size of array by size of one (first) element

        solution(A, N);

        return 0; 
    }

The output is:

    4, 5, -1, 2, 1, 

The time complexity is O(N) for the first for-loop. The space complexity is actually O(2N) for the two arrays. However, the coefficient (multiplier) is always omitted, to quote O(N).