Prefix sum is a very useful technique which can be used for some subarray questions. Let’s look at how it works. PrefixSum[i] stands for the sum of first i elements, which means the sum from array[0] to array[i - 1]. PrefixSum[0] is 0 (first 0 elements’ sum value is 0). When we want to calculate the sum from array[i] to array[j], we can calculate with O(1) time by PrefixSum[j + 1] - PrefixSum[i]. For example:
array: [1, 2, 3, 4]
prefixSum: [0, 1, 3, 6, 10]
array[1] + array[2] + array[3] = prefixSum[4] - prefixSum[1] = 10 - 1 = 9For the interview questions, we don’t have to create the prefix sum array, but most likely we’ll apply its idea into the final solution. A classic coding question is Maximum Subarray. Let’s take one of the question’s input as example:
nums: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
prefixSum: [0, -2, -1, -4, 0, -1, 1, 2, -3, 1]If we look at nums array, we may feel less intuitive to find our the subarray with maximum sum. However, since we know that sum(i...j) = prefixSum[j + 1] - prefixSum[i], we need to let prefixSum[j + 1] as big as possible, and let prefixSum[i] as small as possible. So now when we loop through the prefixSum array, we keep track of the smallest prefix sum, and keep updating the final results.
So why we need to know this technique? Even though we allocate extra O(n) space (maybe you don’t have to, depending on the question), we optimize the time complexity to improve the performance. During the interview, we first throw out a brute force solution, and later, we can “do better” by using prefix sum technique.
Thanks for reading. Have a nice day!