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

Question

Given an vector A, your task is to output an vector 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 vector.

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):

fn solution(a: &[i32]) {
    let n = a.len();    //length of A
    let mut b = vec![0; n];

    for i in 0..n {
        b[i] = a[i];    //for A[i] 
        
        if i > 0 {    //to avoid A[-1]
            b[i] += a[i - 1];
        }
        
        if i < n - 1 {    //to avoid A[N]
            b[i] += a[i + 1];
        }
    }

    // Output
    for i in 0..n {
        print!("{}, ", b[i]);
    }
    println!();
}

fn main() {
    let a = vec![4, 0, 1, -2, 3];
    solution(&a);
}

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).