UPDATE – This post has been updated.
A lot of good things are happening in my work life. I will continue to comment in future posts.
Today I discussed an idea regarding a new service which will extract data from a huge set of files and will be able to allow access to users. Sorry I will not be able to comment much more on this. I have committed to have a first pass of the architecture and high level design documents first thing Monday morning.
Periodically I take a look at YouTube videos from JAVAAID. I first figure out the requirements and then attempt to implement the code. JAVAAID typically covers solutions for HackerRank challenges. The Prefix Sum Algorithm | Prefix Sum Array | Difference Array | EP2 YouTube video does not seem to cover one. It discusses the Prefix Sum algorithm. If you are interested in learning more about it you can read here.
In a nutshell if multiple sets of results are required from a specified array, 
then by first computing the prefix sum array which takes O(n) you can respond to the queries in O(1).
Allow me to present the test cases that I used while experimenting with this subject:
7 6 3 -2 4 -1 0 -5 0 4 main <<< sum: 10 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] main <<< sum: 10 7 6 3 -2 4 -1 0 -5 -1 4 Exception in thread "main" java.lang.Exception: f: -1 OutOfRange at Solution.sumValues(Solution.java:15) at Solution.main(Solution.java:66) 7 6 3 -2 4 -1 0 -5 11 4 Exception in thread "main" java.lang.Exception: f: 11 OutOfRange at Solution.sumValues(Solution.java:15) at Solution.main(Solution.java:66) 7 6 3 -2 4 -1 0 -5 0 -1 Exception in thread "main" java.lang.Exception: l: -1 OutOfRange at Solution.sumValues(Solution.java:19) at Solution.main(Solution.java:66) 7 6 3 -2 4 -1 0 -5 0 11 Exception in thread "main" java.lang.Exception: l: 11 OutOfRange at Solution.sumValues(Solution.java:19) at Solution.main(Solution.java:66) 7 6 3 -2 4 -1 0 -5 2 6 main <<< sum: -4 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] main <<< sum: -4 7 6 3 -2 4 -1 0 -5 1 5 main <<< sum: 4 prefixSum <<< ar: [9, 7, 11, 10] main <<< sum: 4 7 6 3 -2 4 -1 0 -5 0 6 main <<< sum: 5 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] main <<< sum: 5 7 6 3 -2 4 -1 0 -5 0 1 main <<< sum: 9 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] main <<< prefixSum: 9 7 6 3 -2 4 -1 0 -5 2 6 main <<< sum: -4 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] main <<< prefixSum: -4 7 6 3 -2 4 -1 0 -5 5 6 main <<< sum: -5 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] main <<< prefixSum: -5 7 6 3 -2 4 -1 0 -5 3 5 main <<< sum: 3 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] main <<< prefixSum: 3 7 6 3 -2 4 -1 0 -5 0 1 main <<< sum: 9 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] main <<< prefixSum: 9 7 6 3 -2 4 -1 0 -5 0 1 main <<< sum: 9 prefixSum <<< ar: [6, 9, 7, 11, 10, 10, 5] Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Solution.prefixSum(Solution.java:60) at Solution.main(Solution.java:87)
For simplicity I have used the same sequence of numbers to populate the array. I just changed the value of the first (f) and last (l) elements.
At this point please disregard the last two test cases.
If you do not use a prefix sum the following code can be used to sum the values in the array between the specified range:
// **** ****
static int sumValues(int[] ar, int f, int l) throws Exception {
int sum = 0;
// **** perform sanity checks ****
if ((f < 0) || (f > ar.length)) {
throw new Exception("f: " + f + " OutOfRange");
}
if ((l < 0) || (l > ar.length)) {
throw new Exception("l: " + l + " OutOfRange");
}
// **** compute the sum ****
for (int i = f; i <= l; i++)
sum += ar[i];
// **** ****
return sum;
}
After some sanity checks the code loops and generates the correct sum. This algorithm runs in O(n) time.
// **** ****
static int prefixSum(int[] ar, int f, int l) throws Exception {
// **** perform sanity checks ****
if ((f < 0) || (f > ar.length)) {
throw new Exception("f: " + f + " OutOfRange");
}
if ((l < 0) || (l > ar.length)) {
throw new Exception("l: " + l + " OutOfRange");
}
// **** compute the prefix sum array ****
for (int i = 1; i < ar.length; i++ ) {
ar[i] += ar[i - 1];
}
// ???? display the prefix array ????
System.out.print("prefixSum <<< ar: [");
for (int i = 0; i < ar.length; i++) {
if (i < ar.length - 1)
System.out.print(ar[i] + ", ");
else
System.out.print(ar[i] + "]");
}
System.out.println();
// **** return the proper sum ****
if (f == 0)
return ar[l];
else
return ar[l] - ar[f - 1];
}
This method illustrates the generation and use of the prefix sum algorithm. We first perform some sanity checks and follow with the generation in place of the prefix sum array. To visualize what is going on, the updated array is displayed.
The last step is to return in O(1) the result which should always match the value returned by the sumValues() method.
In practice, the idea would be to have a method compute the prefix sum array once and have multiple calls to a method that returns the sums for different ranges.
// **** ****
public static void main(String[] args) throws Exception {
// **** used to read input ****
Scanner sc = new Scanner(System.in);
// **** read the number of elements in the array ****
int n = sc.nextInt();
// **** read an array or numbers ****
int[] ar = new int[n];
for (int i = 0; i < n; i++)
ar[i] = sc.nextInt();
// **** read the first element ****
int f = sc.nextInt();
// **** read the last element ****
int l = sc.nextInt();
// **** generate and display the sum ****
System.out.println("main <<< sum: " + sumValues(ar, f, l));
// **** generate and display the prefix sum ****
System.out.println("main <<< prefixSum: " + prefixSum(ar, f, l));
// **** close the scanner ****
sc.close();
}
The test code reads the arguments to generate and query the sum.
I mentioned above to disregard the last two test cases. If you watch the video, it seems that the code as specified works except when the lower bound for the query is zero (0). That is the case that throws an exception. You can replicate the issue by commenting out the code in the prefixSum() method as follows:
// **** return the proper sum **** // if (f == 0) // return ar[l]; // else return ar[l] - ar[f - 1];
I did leave JAVAAID a comment. I will check for a response tomorrow.
UPDATE – UPDATE – UPDATE
I received the following response from JavaAid:
What I understand from your query is - first is your actual result which is the exception and 2nd one is your expected result which you are looking for but your formula is not giving a correct result- you need to modify your code a little bit instead of I index use f, the operation should be addition instead of subtraction .here is the modify code- // ** return the proper sum ** if (f == 0) return ar[f]; else return ar[f] + ar[f - 1];
The issue is with the following statement when converted to code:
o Range sum query formula- A[I, j] = A[j] – A[I – 1]
When implemented we would have something like this:
// **** return the sum **** // if (i == 0) // return A[j]; // else return A[j] - A[i - 1];
If the value of i is zero (0) the second term would be out of range (0 – 1 == -1; A[-1]) and would throw an exception.
// **** return the sum **** if (i == 0) return A[j]; else return A[j] - A[i - 1];
When I wrote the original code I used different names for the arguments. I refactored them to match the names used by JavaAid.
My entire refactored code follows:
import java.util.Scanner;
/*
*
*/
public class Solution {
// **** ****
static int sumValues(int[] A, int i, int j) throws Exception {
int sum = 0;
// **** perform sanity checks ****
if ((i < 0) || (i > A.length)) {
throw new Exception("i: " + i + " OutOfRange");
}
if ((j < 0) || (j > A.length)) {
throw new Exception("j: " + j + " OutOfRange");
}
// **** compute the sum ****
for (int k = i; k <= j; k++)
sum += A[k];
// **** ****
return sum;
}
// **** ****
static int prefixSum(int[] A, int i, int j) throws Exception {
// **** perform sanity checks ****
if ((i < 0) || (i > A.length)) {
throw new Exception("i: " + i + " OutOfRange");
}
if ((j < 0) || (j > A.length)) {
throw new Exception("j: " + j + " OutOfRange");
}
// **** compute the prefix array ****
for (int k = 1; k < A.length; k++ ) {
A[k] += A[k - 1];
}
// ???? display the prefix sum array ????
System.out.print("prefixSum <<< A: [");
for (int k = 0; k < A.length; k++) {
if (k < A.length - 1)
System.out.print(A[k] + ", ");
else
System.out.print(A[k] + "]");
}
System.out.println();
// **** return the sum ****
if (i == 0)
return A[j];
else
return A[j] - A[i - 1];
}
// **** ****
public static void main(String[] args) throws Exception {
// **** used to read input ****
Scanner sc = new Scanner(System.in);
// **** read the number of elements in the array ****
int n = sc.nextInt();
// **** read an array or numbers ****
int[] A = new int[n];
for (int k = 0; k < n; k++)
A[k] = sc.nextInt();
// **** read the first element ****
int i = sc.nextInt();
// **** read the last element ****
int j = sc.nextInt();
// **** generate and display the sum ****
System.out.println("main <<< sum: " + sumValues(A, i, j));
// **** generate and display the prefix sum ****
System.out.println("main <<< prefixSum: " + prefixSum(A, i, j));
// **** close the scanner ****
sc.close();
}
}
The entire refactored code for this project can be found in my GitHub repository.
END OF UPDATE – END OF UPDATE – END OF UPDATE
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa