Problem Statement

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Constraints:

• 1 <= nums.length <= 1000

• -10^6 <= nums[i] <= 10^6

Explanation

Here we have given an array nums, we need to find its running sum

To understand running Sum consider the following example,
Suppose we have an array nums = [1,3,4,6]
let's denote the elements as
x1 = 1
x2 = 3
x3 = 4
x4 = 6

the running sum means as we traverse the array current element should have the sum of its own element with the previous element

Like the output will be something like this,
[x1, x1+x2, x1+x2+x3, x1+x2+x3+x4]

Suppose we are on nums[2] means 4 then nums[2] will have the sum of 4 (its own element) and its previous elements 3 (nums[1]) and 1 (nums[0])

Now if the question is clear then let's see how we can find the running sum

Solution

Let's see how we can solve this

• Brute Force Approach

  What we can do is use two loops
  - i will traverse the array from 0 to n-1 (n -> size of the array)
  - j will find the sum of previous elements by traversing from 0 to i
  - use an extra array arr of size n to store the sum

public int[] runningSum(int[] nums) {
        int arr[] = new int[nums.length];
        for (int i=0; i<nums.length; ++i) {
            for (int j=0; j <= i; ++j) {
                arr[i] += nums[j];
            }
        }

        return arr;
    }

Time Complexity - O(n^2)
Space Complexity - O(n) [becoz we are using an extra array of size n]

• Optimized Solution

  Let's Optimize the above solution, so what we can do
  - we can use only 1 loop to reduce the time complexity
  - we can remove the extra array arr to reduce the space complexity

  What if we store the sum in the same array? 🤔
  If we store the sum in the same array then we don't need to run the second loop.
  the second loop was to find the sum of previous elements but we store the sum in the current array then we just need to add the previous element in the current element because it already has the sum of its previous elements.

  Hard to understand, Don't worry Let's see the example

Suppose we have nums = [1,2,4] and the pointer(it's not C++ pointer) is on num[0] means 2 then according to the above logic we store the sum(1+2) in the current position so nums will be [1,3,4]
When the pointer moves to the next position nums[2] then we just need to add the previous element nums[1] because it already has the sum of the previous elements so now nums = [1,3,7]

Let's see the code

    public int[] runningSum(int[] nums) {
            for (int i=1; i<nums.length; ++i) {
                nums[i] = nums[i] + nums[i-1];
            }
            return nums;
        }

Here i=1 because if the i=0 then i-1 will create the out-of-bounds exception

Thanks for reading this blog, I Hope it helped you in understanding the question better.
If you want more solutions like this then subscribe to my newsletter, I am making a series of DSA-Days in which I will post one solution a day of leetcode question. The series will cover all types of questions like Easy/Medium/Hard and they will be topic-wise.