📍Introduction
A Prefix array is a simple yet effective tool in computer programming. It helps to minimize the repeated calculations done in an array and reduces the time complexity of your program.
📍What is a Prefix Array?
A Prefix Sum Array is a cumulative sum of another array. Example:
Suppose we have an array A = [-3, 6, 2, 4, 5, 2, 8, -9, 3, 1]. Let us define a new array PA[ ] which has the same size as array A. The elements at ith index in PA[ ] will contain the sum of all the elements from A[0] to A[ i ]. Example:
PA[0] = A[0]
PA[1] = A[0] + A[1]
PA[2] = A[0] + A[1] + A[2]
PA[ i ] = A[0] + A[1] + A[2] + ........ + A[i]
PA[N-1] = A[0] + A[1] + A[2] + ......... + A[N-1]
So the prefix sum array of the given array A[ ] will be:
PA[ ] = [-3, 3, 5, 9, 14, 16, 24, 15, 18, 19]
From the above example, we can easily spot the general formula for prefix sum array:
PA[ i ] = PF[i - 1] + A[ i ], where i > 0.
//Below is the code to create a Prefix Sum Array in Java
int PA[N]; // Declare prefix array with size N
PA[0] = A[0]; // As per our general formula index 0 has an exception
for (int i = 0; i < N; i ++) {
PA[i] = PF[i - 1] + A[i];
}
Time complexity:
The time complexity of creating a prefix sum array is O(N), where N is the length of the input array A. This is because we need to traverse the entire input array once to compute the prefix sum array.
Space complexity:
The space complexity of the prefix sum array is O(N) since it requires an additional array of the same size as the input array A.
📍How to use Prefix Array in a Coding Problem?
Let's pick a coding problem that can be solved with a prefix array:
Q. Range Sum Query
Problem Description
You are given an integer array A of length N.
You are also given a 2D integer array B with dimensions M x 2, where each row denotes a [L, R] query.
For each query, you have to find the sum of all elements from L to R indices in A (0 - indexed).
More formally, find A[L] + A[L + 1] + A[L + 2] +... + A[R - 1] + A[R] for each query.Input Format
The first argument is the integer array A.
The second argument is the 2D integer array B.Output Format
Return an integer array of length M where ith element is the answer for ith query in B.
//Below is the code to solve the above Problem using Prefix Sum in Java
public class Solution {
public ArrayList<Long> rangeSum(ArrayList<Integer> A, ArrayList<ArrayList<Integer>> B) {
ArrayList<Long> pf = new ArrayList<Long>();
ArrayList<Long> ans = new ArrayList<Long>();
pf.add(A.get(0).longValue());
// Below for loop creates an Prefix Sum Array
for (int i = 1; i < A.size(); i ++) {
long temp = pf.get(i - 1) + A.get(i).longValue();
pf.add(temp);
}
// Below for loop solves the problem using Prefix Sum Array
for (int i = 0; i < B.size(); i ++) {
int L = B.get(i).get(0);
int R = B.get(i).get(1);
if (L == 0) {
ans.add(pf.get(R));
}
else {
ans.add(pf.get(R) - pf.get(L - 1));
}
}
return ans;
}
}
Time complexity:
The time complexity to precompute the prefix sum array is O(N), and the time complexity to answer each query using the prefix sum array is O(1) since we only need to perform two lookups and a subtraction operation. Therefore, the overall time complexity of the solution using the prefix sum array is O(N+M), where M is the number of queries.
Space complexity:
The space complexity of the "Range Sum Query" problem using a prefix sum array is O(N) since it requires an additional prefix sum array PF[ ] of the same size as the input array A[ ]. We are not including the ans[ ] in calculating the space complexity as we are returning ans[ ] as the output of our function rangeSum().
📍Advance Techniques
We have used Prefix 'Sum' Array till now but we can also use this logic and create Prefix 'Count' Array with an IF condition, we can also create a Prefix 'Product' Array. These prefix array variations would depend upon the problem statement.
📍When to use Prefix Array
One easiest way to identify is -> let's say you want to calculate the sum/count/product of a range in an array. This kind of problem statement can be solved using a prefix array.
📍Disadvantages of Prefix Array
Although prefix arrays are a powerful tool for optimizing the time complexity of certain coding problems, they do have some disadvantages that are worth considering.
- Space Complexity
One of the main disadvantages of prefix arrays is that they increase the space complexity of your code. This is because you are essentially creating a new array to store the prefix sums of your original array. Depending on the size of your input array, this can result in a significant increase in memory usage.
- Limited Applicability
Prefix arrays are not a universal solution for all coding problems. They are most useful when you need to perform repeated calculations on a subarray of the original array. In other situations, other algorithms or data structures may be more appropriate.
- Updates to the Original Array
If you need to update the values in the original array, you may need to recalculate the entire prefix array. This can be a time-consuming process, especially if your input array is large.
- Preprocessing Time
Creating a prefix array requires an initial preprocessing step, which can add additional overhead to your code. Depending on the size of your input array, this preprocessing step can take a significant amount of time.
Despite these disadvantages, prefix arrays remain a useful tool in many coding problems, and understanding their strengths and weaknesses can help you to use them more effectively in your code.
📍Conclusion
The prefix array is a simple yet effective technique that can help minimize repeated calculations and reduce the time complexity of a program. It is particularly useful when solving problems that involve calculating the sum, count, or product of a range of values in an array. With a time complexity of O(N) and space complexity of O(N), a prefix array is an efficient tool that can significantly boost the performance of a program. Additionally, there are variations of the prefix array that can be used to solve different types of problems, such as prefix count or prefix product arrays. While there are some disadvantages to using prefix arrays, such as increased space complexity and a need for precomputation, the benefits often outweigh the drawbacks. Overall, the prefix array is a valuable tool to add to any programmer's toolkit for optimizing the performance of their code.
Leetcode Problems on Prefix Sum Array
Happy coding!