• ← Previous
• Next →

Let us go through some of the common problems related to prefix-sum technique.

Range Sum Queries

Given an array of numbers, you may need to find the sum of elements within a given range [l, r]. With prefix sums, you can compute the sum of elements between any two indices by subtracting the prefix sum at the left index from the prefix sum at the right index. This allows you to answer such queries in constant time.

Problem: https://leetcode.com/problems/range-sum-query-immutable/

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Here is an Example:

 Given nums = [-2, 0, 3, -5, 2, -1]

 sumRange(0, 2) -> 1
 sumRange(2, 5) -> -1
 sumRange(0, 5) -> -3

Note:

Maintain a prefix sum, where sum[i] includes a[i]. So, if a= {4, 2, 8, 10, 2}, then the prefix sum = {4, 6, 14, 24, 26}. Now, sum from i till j (inclusive both) is sum[j] - sum[i-1]. Take care of the corner case, where i is 0.

Here is the code in C:

 typedef struct {
     int *sum;
     int len;
 } NumArray;

 NumArray* numArrayCreate(int* nums, int len) {
     int i, sum = 0;

     NumArray *obj = malloc(sizeof(NumArray));
     obj->len = len;
     obj->sum = malloc(sizeof(int) * len);

     for (i = 0; i < len; i++) {
         sum += nums[i];
         obj->sum[i] = sum;
     }
     return obj;
 }

 int numArraySumRange(NumArray* obj, int i, int j) {
     if (i < 0 || j > obj->len) return 0;

     return obj->sum[j] - (i > 0 ? obj->sum[i-1] : 0);
 }

Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

We can use a prefix sum approach here as well. For the left-side, we can get the products so far and excluding the self. Now, walk from right side and do the same. Then take product.

For the case of O(1) space (assuming that the output does not count), we can use the same prefix-sum array to also return. Start the prefix-sum in the return array itself. Next, walk from the back and keep on applying the product till a[i+1] to i.

 class Solution {
     public int[] productExceptSelf(int[] nums) {

         int[] ret = new int[nums.length];
         ret[0] = 1;

         for (int i = 1; i < nums.length; i++) {
             ret[i] = ret[i-1] * nums[i-1];
         }

         int rightProd = 1;
         for (int i = nums.length-2; i >=0 ; i--) {
             rightProd = rightProd * nums[i+1];
             ret[i] = ret[i] * rightProd;
         }

         return ret;
     }
 }

Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

 Example 1:
 Given nums = [1, -1, 5, -2, 3], k = 3,
 return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

 Example 2:
 Given nums = [-2, -1, 2, 1], k = 1,
 return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

The idea here is to use prefix sum. The difference that we are looking for can be checked by adding k to the prefix-sum of the current index and checking if that value exists in the hashtable.

If the array is [1, -1, 5, -2, 3],

then the prefix sum is [1, 0, 5, 3, 6].

Now, we build a hashtable such that it has the following key->value mapping 1 --> 0 0 --> 1 3 --> 3 5 --> 2 6 --> 4

Now, we walk the array again. Note that to take into account the first element, we have to start with index -1. At each index, we take the prefix-sum again (for index -1, the sum would be 0), and check if the k+prefix-sum exists. If it does, then we get the index. We keep a running counter of the hash-table-index - the current_index.

Here is the code:

Basically, when you get the sum, you check if (sum-k) exists (quite similar to Has2Sum(), where as we insert an element, we also look for its complement in the same pass). Note that, to get a longer value, if we already have a sum inserted in the hashtable, then we should not insert it again. With that, the hashtable would look like: 0 --> -1 1 --> 0 3 --> 3 5 --> 2 6 --> 4

But, if we were to not check, then we would have a hashtable like the following.

0 --> 1 1 --> 0 3 --> 3 5 --> 2 6 --> 4

Clearly, a value of 0 is being pointed by 1, since even at index 1, the sum is zero. But, then this would give us the maximum length of 2 and not 4.

 int maxSubArrayLen(int* a, int len, int k) {
     hasht_t ht;

     int i, sum = 0, *indx, ret_len = 0, lookup_val;

     if (!len) return 0;

     hasht_init(&ht, int_compare_func, int_get_hash);

     hasht_insert(&ht, get_int(0), get_int(-1));

     for (i = 0; i < len; i++) {
         sum += a[i];
         lookup_val = sum - k;
         if (hasht_lookup(&ht, &lookup_val, (void **)&indx)) {
             ret_len = max(ret_len, (i - *indx));
         }

         if (!hasht_lookup(&ht, &sum, (void **)&indx)) {
             hasht_insert(&ht, get_int(sum), get_int(i));
         }
     }

     return ret_len;
 }

• ← Previous
• Next →