How to use Prefix Sum Technique In Javascript
This approach involves precomputing prefix sums for the array. We can create an auxiliary array where each element represents the sum of elements from the beginning of the array up to that index. Then, we can calculate the sum between two indices by subtracting the prefix sum at the start index from the prefix sum at the end index + 1.
Example: Implementation to Find the sum of elements between two given indices in an array using Prefix Sum Technique.
function sum(arr, start, end) {
let prefixSum = [0];
for (let i = 0; i < arr.length; i++) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
return prefixSum[end + 1] - prefixSum[start];
}
const array = [1, 3, 5, 7, 9, 11];
const startIndex = 2;
const endIndex = 4;
console.log(sum(array, startIndex, endIndex));
Output
21
Time Complexity: O(n), where n is the number of elements between startIndex and endIndex.
Space Complexity: O(1), constant space used.
JavaScript Program to Find the Sum of Elements Between Two Given Indices in an Array
In JavaScript programming, there are often scenarios where we need to calculate the sum of elements within a specific range in an array. This can be useful in various applications, such as calculating subarray sums in algorithms or performing range-based calculations in data analysis.
Example:
Input: const array = [1, 2, 3, 4, 5];
const startIndex = 1;
const endIndex = 3;
Output: 9
Table of Content
- Naive Approach
- Using Prefix Sum Technique