Welcome Reader!
We hope that you are doing great with Arrays so far. In the last article, we shared the Rotate Array problem. In this article, we will discuss the next problem based on “Arrays” i.e. “Running Sum of 1D Array”.
Before you move any further, it is advised that you give this problem a fair try. Let’s jump to the problem.
Important Link: Problem Link
Problem Statement
You are given a large integer represented as an integer array of digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
For example:
Sample Input -> [1,2,3,4]
Sample Output -> [1,3,6,10]
Sample Input -> [1,1,1,1,1]
Sample Output -> [1,2,3,4,5]
Approach:
1.) Create a pointer and place it on 1th index of the array.
2.) Traverse the array from 1th index of the array.
3.) For every element, add the previous element and current element and store it inside the current element.
Let's take an example -:
Let’s take an example where input is,
[1,2,3,4]
Place the pointer on 1st index of the array and start traversing.
For the 1st index, add the 0th index and 1st index and place the sum inside 1st index.
For the 2nd index, add the 1st index and 2nd index and place the sum inside the 2nd index.
For the 3rd index, add the 2nd index and 3rd index and place the sum inside the 3rd index.
Let’s try to code this!
1.) Traverse the array from 1st index of the array.
2.) For every element, add the previous element and current element and store them inside the current element.
3.) Return the updated array after the whole array is traversed.
Complexities:
Time Complexity: O(N)
Where N = length of the array. As we are traversing every array element for one time, the time complexity is O(N).
Space Complexity: O(1)
As we have created no extra space, space complexity is O(1).
Complete Code:
class Solution {
public int[] runningSum(int[] nums) {
for(int i=1; i<nums.length; i++)
{
nums[i] = nums[i] + nums[i-1];
}
return nums;
}
}
We hope that this article was helpful. You can contact us via our website. Doubts, suggestions, and feedback are always welcomed. You are also advised to follow the sequence of modules and questions on our website. Keep practicing more and more problems daily. Meditate enough on each step of each problem.
“Don’t let the fear of losing be greater than the excitement of winning.”
-Robert Kiyosaki
All the best for an exciting future!
Happy Coding!
Contributed by: Parth Mathur
Regards,
The Daily Code Team