This content originally appeared on DEV Community 👩‍💻👨‍💻 and was authored by Piyush Acharya
Intuition
My first thought on how to solve this problem is to iterate through the array and add the current element to the previous element. This will give us a running sum of the elements in the array.
Approach
To implement this approach, I will use a for loop to iterate through the array. I will check if the current index is not equal to 0, as we do not want to add the element at index 0 to itself. If the current index is not 0, I will update the value at the current index to be the sum of the current element and the previous element.
Complexity
-
Time complexity: O(n)
- The time complexity of this solution is O(n), as we are iterating through the array once and performing a constant number of operations on each element.
-
Space complexity: O(1)
- The space complexity of this solution is O(1), as we are not using any additional data structures or variables to store the running sum.
Code
class Solution {
public int[] runningSum(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (!(i == 0)) {
nums[i] = nums[i - 1] + nums[i];
}
}
return nums;
}
}
For more details: https://leetcode.com/problems/running-sum-of-1d-array/solutions/2916215/highly-efficient-java-solution-beats-100-in-runtime-and-94-in-memory-usage/
This content originally appeared on DEV Community 👩‍💻👨‍💻 and was authored by Piyush Acharya
Piyush Acharya | Sciencx (2022-12-16T02:18:05+00:00) LeetCode’s Running Sum of 1d Array – Highly Efficient Java Solution (Beats 100% In Runtime And 94% in Memory Usage). Retrieved from https://www.scien.cx/2022/12/16/leetcodes-running-sum-of-1d-array-highly-efficient-java-solution-beats-100-in-runtime-and-94-in-memory-usage/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.