Elegant Algorithmic Crush – USing 1) difference array & 2) prefix sum

Today, I got a chance to come across a pretty elegant solution, involving 1) calculating difference array and 2) find ongoing prefix sum, in order to solve one problem from hackerrank.com

First, here comes the problem.

  
/*
You are given a list of size N, initialized with zeroes. You have to perform M operations on the list and output the maximum of final values of all the N elements in the list. For every operation, you are given three integers a, b and k and you have to add value k to all the elements ranging from index a to b(both inclusive).

Input Format
First line will contain two integers N and M separated by a single space.
Next M lines will contain three integers a, b and k separated by a single space.
Numbers in list are numbered from 1 to N.

Output Format
A single line containing maximum value in the updated list.

Constraints
3<=N<=10^7
1<=M<=2*10^5
1<=a<=b<=N
0<=k<=10^9

Sample Input #00
5 3
1 2 100
2 5 100
3 4 100

Sample Output #00
200

Explanation
After first update list will be 100 100 0 0 0.
After second update list will be 100 200 100 100 100.
After third update list will be 100 200 200 200 100.
So the required answer will be 200.
*/

Speaking as an average level programmer, he/she or I could naturally start from a nested loop to read each input line and update each element in the array, and calculate the carrying max. Therefore, it cost O(N * T). But after I solve this "easy" problem, I just feel it could/should be improved to linear complexity somehow. I will talk this later.

(N is array size, T is total test count #)

Let's

    
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n+1];
        int t = sc.nextInt();
        int a, b;
        long val;
        long max = 0l;

        for (int i = 0; i < t; i++) {
            a = sc.nextInt(); b = sc.nextInt(); val = sc.nextLong();
            arr[a] += val;
            if((b+1)<=n)
                arr[b+1]-= val;
        }

        long x = 0l;
        for (int i = 0; i <= n ; i++) {
            x += arr[i];
            max = Math.max(max, x);
        }

        System.out.println(max);
    }

Here comes the greater part to improve time complexity to O(M + N)

1) Use difference array.
2) Find max of all prefix sum.

For this problem, I would employ a max prefix sum scan on a difference array. To generate a set of range differences, we adjust arr[a] += val and arr[b+1] −= val. Going back to your sample data, your difference array would look like this:

1

To calculate the max prefix sum, accumulate the difference array to NN while taking the maximum accumulated prefix. (*) denotes new max found.

2

Building a difference array in O(M)O(M) and finding the max prefix sum in O(N)O(N) results in a O(M+N)O(M+N) linear algorithm.

  
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n+1];
        int t = sc.nextInt();
        int a, b;
        long val;
        long max = 0l;

        for (int i = 0; i < t; i++) {
            a = sc.nextInt(); b = sc.nextInt(); val = sc.nextLong();
            arr[a] += val;
            if((b+1)<=n)
                arr[b+1]-= val;
        }

        long x = 0l;
        for (int i = 0; i <= n ; i++) {
            x += arr[i];
            max = Math.max(max, x);
        }

        System.out.println(max);
    }

In conclusion, I can imagine the most possible practical usage in trading could be applying same parameter addition to back test or optimize final output or just to control overhead of each parameter.

Leave a Reply