# Auxiliary Array - 1

I hope you're getting some idea about the thought process involved while solving different problems. We're going to move to a new type of problems now, where a new array needs to be created, that stores some information about the original array.

This newly created array comes in handy whenever that information is required as we don't need to find that information again and again, and can simply access this `auxiliary array`

for that information.

Inthis article specifically, we'll look at how to create one of the most used auxiliary arrays i.e. prefix sum / running sum array.

## Running Sum of 1d Array

For those who didn't understand the problem clearly, it basically says that given an integer array, let's say *arr*, you've to create a new array, let's say *pre *(*pre* because I'd like to call it prefix sum array)*.*

Now, for this *pre *array:

- The length has to be equal to the length of
*arr.* - pre[i] = arr[0] + arr[1] + arr[2] + .... + arr[i-1] + arr[i]

In other words, the value ofpre[i]has to be equal to the sum of the elements of the prefixarr[0....i].

### How to solve?

A straight-forward way that comes to my mind is to do exactly what's asked of in the problem.

- Create an array
*pre*, of size equal to the size of*arr.* - Iterate over the values of
*pre*:- For each value of
*i*, calculate*cur_sum =*sum(*arr[0] + arr[1] + .. arr[i-1] + arr[i]*) using a nested loop. - Assign
*pre[i] = cur_sum*

- For each value of
- Return
*pre.*

## Implementation

```
vector<int> runningSum(vector<int>& arr) {
vector<int> pre(arr.size());
for(int i = 0; i < arr.size(); ++i) {
// Calculate cur_sum
int cur_sum = 0;
for(int id = 0; id <= i; ++id)
cur_sum += arr[id];
// Assign
pre[i] = cur_sum;
}
return pre;
}
```

## Time and Space Complexity

- Time Complexity: O(N
^{2}) - Because of the nested loop. - Space Complexity: O(N) - Because we created the auxiliary array.

### Isn't O(N^{2}) time too much?

Well, I think it is. Let's get rid of that extra N and try to reduce the time complexity to O(N).

## Hint 1

When trying to calculate *pre[i]*, we basically need *arr[0] + arr[1] + arr[2] + .. arr[i-1] + arr[i]*, right?

In other words, *pre[i] = (arr[0] + arr[1] + ... + arr[i-1]) + arr[i]*, rings any bells?

## Hint 2

Read the last sentence of the preious hint carefully. There, *pre[i]* was basically divided into 2 parts: *(arr[0] .. arr[i-1])* being the 1st one, and *arr[i]* being the 2nd one.

The 2nd part is fine, it's just *arr[i]* only, but what about the 1st part? Do you think calculating that if required? Isn't already calculated?

## Hint 3

Still didn't get it? :/

Okay, all I'll say is that if you observe, *arr[0] + arr[1] + ...arr[i-1])* is nothing but equal to *pre[i-1]*.

Now, think. No further hints.

## Intuition & Solution

As already explained in the above hints, when we're calculating the value for *pre[i]*, we don't really need to calculate it from scratch.

From Hint 3, it's not hard to deduce that *arr[0] + arr[1] + arr[2] + ... arr[i-1]* is equal to *pre[i-1]*. Therefore, *pre[i] = pre[i-1] + arr[i]*

Now, using the above observation, we can simple iterate over different valid indices, and easily calculate *pre[i]* in O(1) each.

## Implementation

```
vector<int> runningSum(vector<int>& nums) {
vector<int> pre(nums.size());
for(int i = 0; i < nums.size(); ++i)
pre[i] = i? pre[i-1] + nums[i] : nums[i];
return pre;
}
```

## Time and Space Complexity

- Time Complexity: O(N) - All we're doing is a simple array traversal.
- Space Complexity: O(N) - Because we created the auxiliary array.