Hello! Today, I would like to take an in-depth look at one of the algorithms frequently featured in Java coding tests, which is calculating the range sum. In particular, this course will select a problem related to computing the range sum and explain the solution process in detail.
Problem Definition
Given an integer array arr, several queries are provided. Each query includes two integers start and end, and the task is to calculate arr[start] + arr[start + 1] + ... + arr[end]. What is required in this problem is to efficiently compute the range sum for each query.
Example Problem
Input:
arr = [1, 2, 3, 4, 5]
queries = [[0, 2], [1, 3], [2, 4]]
Output:
[6, 9, 12]
Solution Algorithm
To solve this problem, we must efficiently handle multiple range sums on the array. Essentially, repeating the sum of parts of the array for each query may be inefficient. To reduce this inefficiency, I will introduce an approach using the “prefix sum array.”
Explanation of Prefix Sum Array
A prefix sum array is a method of preprocessing the elements of a given array by accumulating them. This allows for the calculation of each range sum in O(1) time complexity. The definition of the prefix sum array is as follows:
prefix[i] = arr[0] + arr[1] + ... + arr[i]
In other words, the sum of the range arr[i] ~ arr[j] can be computed as prefixSum[j] - prefixSum[i-1]. Here, prefixSum[-1] is assumed to be 0.
Implementation Steps
- Create the Prefix Sum Array: Generate the prefix sum array using the given array.
- Process Queries: Calculate the range sum for each query with O(1) complexity.
Java Code Implementation
public class RangeSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int[][] queries = {{0, 2}, {1, 3}, {2, 4}};
int[] result = rangeSum(arr, queries);
for (int sum : result) {
System.out.println(sum);
}
}
public static int[] rangeSum(int[] arr, int[][] queries) {
int n = arr.length;
int[] prefixSum = new int[n];
prefixSum[0] = arr[0];
// Create the cumulative sum array
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int[] results = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int start = queries[i][0];
int end = queries[i][1];
// Calculate the range sum
results[i] = (start > 0) ? (prefixSum[end] - prefixSum[start - 1]) : prefixSum[end];
}
return results;
}
}
Code Explanation
The Java code above creates a user-defined class RangeSum and defines the array and queries in the main method. The rangeSum method generates the prefix sum array from the given array and calculates the range sum for each query.
1. Creating the Cumulative Sum Array
First, we initialize the first element, then create the cumulative sum array through a loop. This process has a time complexity of O(n), where n is the length of the array.
2. Processing Queries
For each query, we use the cumulative sum array to compute the range sum in O(1). This method should perform well in terms of efficiency, especially when there is a large amount of data or many queries.
Complexity Analysis
The time complexity of this code is O(n + m), where n is the length of the array and m is the number of queries. Thus, it consumes O(n) time complexity during the initialization process, and O(1) for each query, making the total time complexity O(n + m). This ensures satisfactory performance.
Conclusion
Today, we dealt with the problem of calculating range sums in Java coding tests. We learned that utilizing a cumulative sum array allows for efficient calculations of range sums for multiple queries. This is a useful algorithm to remember for actual coding tests! I will prepare more algorithm problem-solving courses in the future. Thank you!