Introduction Prefix Sum Pattern

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Introduction Prefix Sum Pattern

Table of Contents

Contents are not accessible

What is Prefix Sum?

A prefix sum is the cumulative sum of elements in an array up to a certain index. It is a powerful tool for efficiently solving range sum queries and various subarray problems. By precomputing the prefix sums of an array, we can quickly calculate the sum of any subarray in constant time. This technique is widely used in algorithmic problems to improve performance and reduce time complexity, making it essential for handling large datasets and multiple queries efficiently.

For example, if we have an array ([1, 2, 3, 4]), the prefix sums would be calculated as follows:

Prefix sum at index 0: (1)
Prefix sum at index 1: (1 + 2 = 3)
Prefix sum at index 2: (1 + 2 + 3 = 6)
Prefix sum at index 3: (1 + 2 + 3 + 4 = 10)

So, the prefix sum array for ([1, 2, 3, 4]) is ([1, 3, 6, 10]).

Algorithm to Calculate Prefix Sum

Initialize an array prefix of the same length as the input array.
Set prefix[0] to arr[0].
For each subsequent element, set prefix[i] to prefix[i-1] + arr[i].
Return the prefix array.

Code

Python3

. . . .

Complexity Analysis

Time Complexity

Computation: The for-loop runs (n-1) times, where (n) is the length of the input array, resulting in $O(n)$ time.

Therefore, the overall time complexity is $O(n)$ .

Space Complexity

Prefix Array: The prefix array requires $O(n)$ space, where (n) is the length of the input array.
Input Array: The input array itself requires $O(n)$ space.

Thus, the overall space complexity is $O(n)$ .

Why Use Prefix Sums?

Prefix sums are used to improve the efficiency of range sum queries. Without a prefix sum, calculating the sum of elements between two indices (i) and (j) in an array requires iterating through the elements from (i) to (j), which takes $O(n)$ time. By precomputing the prefix sums, we can answer these queries in $O(1)$ time.

Example: Range Sum Query

Given an array nums and a range query (i, j), find the sum of elements between indices i and j.

Example

Input: arr = [1, 2, 3, 4], i = 1, j = 3
Output: 9
Justification: The sum of 2, 3 and 4 is 9.

Step-by-Step Algorithm

Compute the Prefix Sum Array:
- Initialize a prefix array prefix of the same length as the input array.
- Set prefix[0] to the first element of the input array.
- Iterate through the input array starting from index 1:
  - Set prefix[i] to prefix[i-1] + arr[i].
- The prefix sum array is now ready to be used for range sum queries.
Answer the Range Sum Query:
- For a given range ([i, j]):
  - If (i = 0), the sum is prefix[j].
  - Otherwise, the sum is prefix[j] - prefix[i-1].

Code

Python3

. . . .

Complexity Analysis

Time Complexity:

Computation: The for-loop runs (n-1) times, resulting in $O(n)$ time.
Range Sum Query: Answering a range sum query takes $O(1)$ time.

Therefore, the overall time complexity is $O(n)$ for preprocessing and $O(1)$ for each query.

Space Complexity:

Prefix Array: The prefix array requires $O(n)$ space.
Input Array: The input array itself requires $O(n)$ space.

Thus, the overall space complexity is $O(n)$ .

Applications of Prefix Sums

Range Sum Queries: As explained above, prefix sums can quickly answer the sum of elements between any two indices in an array.
Subarray Problems: Prefix sums are used to find subarrays with a given sum, maximum sum subarray, and other subarray-related problems.
2D Prefix Sums: Extending the concept to two-dimensional arrays helps in efficiently calculating the sum of elements in sub-matrices.
Frequency Counting: Prefix sums can be used to maintain cumulative frequencies, helping in statistical calculations and data analysis.
Balancing Loads: In distributed systems, prefix sums can help in balancing workloads evenly across multiple servers.

By understanding and utilizing prefix sums, you can solve many algorithmic problems more efficiently, making your solutions both faster and more elegant.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible