Skip to main content

Arrays Hands-On: Warming Up

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.

In this 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:

  1. The length has to be equal to the length of arr.
  2. pre[i] = arr[0] + arr[1] + arr[2] + .... + arr[i-1] + arr[i]
In other words, the value of pre[i] has to be equal to the sum of the elements of the prefix arr[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.

  1. Create an array pre, of size equal to the size of arr.
  2. Iterate over the values of pre:
    1. For each value of i, calculate cur_sum = sum(arr[0] + arr[1] + .. arr[i-1] + arr[i]) using a nested loop.
    2. Assign pre[i] = cur_sum
  3. 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(N2) - Because of the nested loop.
  • Space Complexity: O(N) - Because we created the auxiliary array.

Isn't O(N2) 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.