JavaScript Coding Test Course, Calculating Interval Sum 1

Hello! Today we will tackle the problem of calculating the range sum using JavaScript. The range sum problem is very helpful in learning how to efficiently process data and manipulate arrays. This topic frequently appears in coding tests and algorithm problem-solving, so I encourage you to thoroughly understand it through this opportunity.

Problem Description

Implement a function rangeSum(array, start, end) that efficiently calculates the sum of a specific range in the given array. Here, array is an array of integers, and start and end represent the indices of the array. The sum of the range is defined as array[start] + array[start + 1] + ... + array[end].

Input

  • 1 ≤ array.length ≤ 105
  • -109 ≤ array[i] ≤ 109
  • 0 ≤ start ≤ end < array.length

Output

Returns an integer that represents the sum of the range.

Example

Input: rangeSum([1, 2, 3, 4, 5], 1, 3)
Output: 9 // 2 + 3 + 4 = 9

Solution

To compute the range sum, it is essential to understand the array and the starting and ending indices of the range. The problem we need to solve is to sum all the numbers within a specified index range in the given array. However, as the size of the array may increase, it is important to use an efficient method.

Simple Loop Approach

The simplest and most intuitive way is to calculate the sum of the range directly using a loop within the given index range. The time complexity of this method is O(n).

function rangeSum(array, start, end) {
        let sum = 0;
        for (let i = start; i <= end; i++) {
            sum += array[i];
        }
        return sum;
    }

The above code sums all the values in the range using the given array and start and end indices. However, this method is inefficient because it requires recalculating from the beginning every time the range changes.

More Efficient Method: Prefix Sum Array

One approach is to scan the array once and store the cumulative sum. This method consists of the following steps:

  1. Create a prefix sum array.
  2. Calculate the cumulative sum based on the original array.
  3. To find the range sum, simply calculate sum[end] - sum[start - 1].

The implementation code is as follows:

function rangeSum(array, start, end) {
        const prefixSum = new Array(array.length).fill(0);
        prefixSum[0] = array[0];
        for (let i = 1; i < array.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + array[i];
        }
        return start > 0 ? prefixSum[end] - prefixSum[start - 1] : prefixSum[end];
    }

This method goes through an initialization process with a time complexity of O(n), after which the range sum can be calculated in O(1). By scanning the array once to obtain the prefix sum, it operates very efficiently based on the number of ranges that need to be calculated afterwards.

Time Complexity

The time complexity for the simple loop approach, which is the first method, remains O(n) regardless of the size of the range. However, using the prefix sum method allows each range sum to be calculated in O(1) after the initial O(n) time complexity, thus becoming advantageous as the number of queries increases.

Conclusion

Today, we learned how to calculate the range sum using JavaScript. By learning to solve problems efficiently, you will develop the ability to overcome frequently encountered challenges in coding tests. Now, practice with different arrays and test them yourself!

References