algoadvance

Leetcode 1480. Running Sum of 1d Array

Problem Statement

The problem asks for the running sum of a 1D array. The running sum of a given array is defined as a new array where the i-th element is the sum of the first i+1 elements of the original array.

For example, if the input is nums = [1, 2, 3, 4], the running sum would be [1, 3, 6, 10].

Clarifying Questions

  1. Input Constraints: What is the range of values for the elements in the array?
  2. Array Size: What is the maximum and minimum size of the array?
  3. Input Types: Should the function handle non-integer values or is it guaranteed to have integer inputs only?

Assuming standard constraints:

Code

public class Solution {
    public int[] runningSum(int[] nums) {
        // Handling edge cases with input constraints
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        // Create an array to store the running sum
        int[] runningSumArray = new int[nums.length];
        // Initialize the first element of runningSumArray
        runningSumArray[0] = nums[0];

        // Loop through the array starting from the second element
        for (int i = 1; i < nums.length; i++) {
            // Calculate running sum by adding the current element to the previous running sum
            runningSumArray[i] = runningSumArray[i - 1] + nums[i];
        }

        return runningSumArray;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 3, 4};
        int[] result = sol.runningSum(nums);
        // Printing the result should give [1, 3, 6, 10]
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

Strategy

  1. Create Running Sum Array: Create a new array to store the running sum.
  2. Initial Value: Initialize the first element of the running sum array with the first element of the input array.
  3. Calculate Running Sum: Iterate through the input array starting from the second element, calculating the running sum for each position by adding the current element to the last value in the running sum array.
  4. Edge Cases: Handle edge cases where the array is null or empty.

Time Complexity

The algorithm has a time complexity of (O(n)), where (n) is the number of elements in the input array. This is because we iterate through the array once to calculate the running sum.

Space Complexity

The space complexity is (O(n)) due to the additional array used to store the running sums.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI