Javascript Coding Test Course, Interval Sum

Hello! In this tutorial, we will explore the “range sum” problem, which is frequently featured in JavaScript coding tests, in depth. The range sum problem involves efficiently calculating the sum of a specific range within a given sequence, and it can be solved using various optimization techniques. The range sum problems we will discuss can be particularly time-consuming when the size of the array is large, so it’s essential to design a more efficient algorithm.

Problem Introduction

Here is a problem related to range sums:

Problem Description

An array of integers arr and several pairs of integers (l, r) are given. Each pair represents the starting point l and endpoint r of a range. Write a program to calculate the sum of arr[l] + arr[l + 1] + ... + arr[r]. The length of the array and the number of pairs are as follows:

  • 1 ≤ arr.length ≤ 106
  • 1 ≤ l, r ≤ arr.length
  • 0 ≤ arr[i] ≤ 109

For example, if the array is arr = [1, 2, 3, 4, 5] and the pair (1, 3) is given, the range sum is arr[1] + arr[2] + arr[3] = 2 + 3 + 4 = 9.

Approach to the Problem

To solve this problem efficiently, simply using loops to calculate the sum for each range is not appropriate. The reason is that in the worst-case scenario, it would have a time complexity of O(N * M), which can lead to exponential time increases if the size of the data is large. Instead, we can use a more effective approach.

Preprocessing Technique: Prefix Sum Array

One way to solve the range sum problem is to create a Prefix Sum Array. Using a prefix sum array allows us to calculate the sum of a range in O(1) time. The definition of the prefix sum array is as follows:

prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

Thus, the sum of the range (l, r) can be calculated as:

sum(l, r) = prefix[r + 1] - prefix[l]

This allows us to compute the range sum for each pair in O(1) time. The overall time complexity of the algorithm is O(N + M), where N is the size of the array and M is the number of pairs.

Implementation Steps

Now, let’s implement the JavaScript code that solves the problem using the prefix sum array.

Step 1: Create the Prefix Sum Array


function createPrefixSum(arr) {
    const prefix = new Array(arr.length + 1).fill(0);
    for (let i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

Step 2: Calculate the Range Sum


function rangeSum(prefix, l, r) {
    return prefix[r + 1] - prefix[l];
}

Step 3: Implement the Main Function


function calculateRangeSums(arr, queries) {
    const prefix = createPrefixSum(arr);
    const results = [];
    for (let [l, r] of queries) {
        results.push(rangeSum(prefix, l - 1, r - 1)); // 1-based to 0-based
    }
    return results;
}

// Example usage
const arr = [1, 2, 3, 4, 5];
const queries = [[1, 3], [2, 5], [0, 2]];
const results = calculateRangeSums(arr, queries);
console.log(results); // [9, 14, 6]

Results Analysis

The above code is a program that efficiently calculates and outputs the range sum for each query based on the given array and queries. As a result, it can quickly compute range sums and does not suffer performance degradation depending on the size of the array or the number of queries.

Time Complexity

The time complexity of this algorithm is as follows:

  • Creating the prefix sum array: O(N)
  • Processing each query: O(1) (If you combine processing all M queries, it becomes O(M))

As a result, the overall time complexity is O(N + M), which is very efficient.

Conclusion

Now we have learned how to efficiently solve the range sum problem using a prefix sum array. Since range sum problems are frequently featured topics in coding tests, understanding and utilizing optimization techniques like this is important. Practice solving various types of problems!

Additional Practice Problems

Try practicing the following variant problems:

  • Problems that find the maximum value of the range instead of the sum
  • Problems that find the product of the range (note that division operations may need to be considered)
  • Consider how to handle different queries (e.g., range increment, decrement, etc.)

Based on the above content, I hope you solve various problems. Thank you!