Arrays: Given an array, move all the negative number to the end by preserving the relative order.

Problem Statement:

You are given an array, you need to find the prefix sum of the array.

Prefix sum array is a new array of same size of original array, such that prefixSum[i] = arr[0] + arr[1] + … arr[i]

Example:

Input: arr = [1, 2, 3, 4]
Output = [1, 3, 6, 10]

Solution Explanation:

Solution is very simple.

Traverse the given array.

Then for each index add the value of the current element to the previous value of the prefix sum array.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

vector<int> prefixSum(vector<int> &arr) 
{
    int n = arr.size();
    
    vector<int> prefixSumRes(n);

    prefixSumRes[0] = arr[0];

    for (int i = 1; i < n; i++)
        prefixSumRes[i] = prefixSumRes[i - 1] + arr[i];
    
    return prefixSumRes;
}

int main() 
{
    vector<int> arr = {1, 2, 3, 4};
    vector<int> prefixSumRes = prefixSum(arr);
    for(auto i: prefixSumRes) 
    {
        cout << i << " " ;
    }
    return 0;
}

Output

1 3 6 10