Leetcode 5453. Running Sum of 1d Array

In this Leetcode problem, we are asked to return the sum array given an nums array where sum[i] = sum(nums[0],…, nums[i])

Problem statement

Solution

A few ideas for this problem:

1. We will use the input array and modify it, and return it as the solution. That way, we don’t have to create a new array.
2. We will build a loop such that after each step i, nums[i] contains the expected value for sum[i]
3. Given that nums[i] contains the sum value, and nums[i+1] wasn’t modified, we assignnums[i+1] = nums[i+1] + nums[i] at the step i+1.

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

This solution runs in O(n) time, with n the size of the input array, and beats 100% of the Java solutions.

Submission results

Happy coding :)

What’s next:

• Checkout the solution for another problem: Rearrange words in a sentence
• Contact me: poitevinpm@gmail.com
• Looking to interview for a software engineer position? Contact me :)