CODEWITHSUNDEEP
algorithmdata-structurestime-complexitybig-o
Top Cat
Top Cat

Reputation: 351

How can I make this Algorithm more efficient?

I've got an Algorithm that produces a 2D array containing the sum of all possible values. For example, for the array [1,5,8,4,5], the 2D array sums[1][3] should return the sum of index 1-3 in the original array (17). I believe that in terms of big O, the efficiency is O(N2). Is there any way I can make this algorithm more efficient? 

public static int[][] sum(int[] values){
    int[][] sums = new int[values.length][values.length];
    for(int x = 0; x < values.length; x++){
        int total = 0;
        for(int y = x; y < values.length; y++) {
            total += values[y];
            sums[x][y] = total;
        }
    }
    return sums;
}

Upvotes: 1

Views: 174

Answers (2)

User_Targaryen
User_Targaryen

Reputation: 4225

Calculate prefix sum in the following way:

public static int[] sum(int[] values){
    int[] prefix_sums = new int[values.length];
    prefix_sums[0] = values[0];
    for(int x = 1; x < values.length; x++){
        prefix_sums[x] = prefix_sums[x-1] + values[x];
    }
    return prefix_sums;
}

As per your query, you want to find the sum from index x to index y (0 based indexing), this is how to get the sum:

if(x==0)
    result = prefix_sums[y];
else
    result = prefix_sums[y] - prefix_sums[x-1];

Hope it helps!!!

Upvotes: 0

גלעד ברקן
גלעד ברקן

Reputation: 23945

You can solve this in O(n) time and space with a prefix-sum array:

array    = [1, 5, 8, 4, 5]
prefixes = [1, 6,14,18,23]

sums(1,3) = prefixes[3] - prefixes[0] = 18 - 1 = 17

Upvotes: 4

Related Questions