algoadvance

Leetcode 1480. Running Sum of 1d Array

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: [10,14,18,22]
Explanation: The running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1, 2, 3, 4, 5]
Explanation: The running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3, 4, 6, 16, 17]

Clarifying Questions:

1. Input Constraints:
   • What is the maximum size of the array?
   • What range of values can the array elements take?
2. Output Requirements:
   • Should the output be a new array or can it modify the input array in-place?

Strategy:

1. Initialize the first element of the running sum array to the first element of the input array.
2. Iterate through the input array starting from the second element.
3. For each element, calculate the running sum by adding the current element to the running sum of the previous element.
4. Store the result in a new array.

Time Complexity:

• The algorithm runs in O(n) time, where n is the length of the input array since we only make a single pass through the array.

Code:

#include <vector>
#include <iostream>

std::vector<int> runningSum(const std::vector<int>& nums) {
    // Initialize the result vector with the same size as nums
    std::vector<int> result(nums.size());
    
    // Set the first element of the result to be the first element of nums
    result[0] = nums[0];
    
    // Iterate through the rest of the nums array to calculate the running sum
    for(size_t i = 1; i < nums.size(); ++i) {
        result[i] = result[i-1] + nums[i];
    }
    
    return result;
}

// Helper function for printing the vector
void printVector(const std::vector<int>& vec) {
    for(int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    // Test cases
    std::vector<int> nums1 = {1, 2, 3, 4};
    std::vector<int> nums2 = {1, 1, 1, 1, 1};
    std::vector<int> nums3 = {3, 1, 2, 10, 1};

    std::vector<int> result1 = runningSum(nums1);
    std::vector<int> result2 = runningSum(nums2);
    std::vector<int> result3 = runningSum(nums3);

    std::cout << "Running sum of {1, 2, 3, 4}: ";
    printVector(result1);

    std::cout << "Running sum of {1, 1, 1, 1, 1}: ";
    printVector(result2);

    std::cout << "Running sum of {3, 1, 2, 10, 1}: ";
    printVector(result3);

    return 0;
}

Explanation:

• runningSum function computes the running sum of the elements in nums.
• printVector is a helper function to print the contents of the vector for testing.
• In main, we define several test cases and print their running sums.

This approach ensures the solution is clear, efficient, and easy to understand.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?