Prefix Sum & Suffix Techniques

Creating a Prefix Sum Array

Formula:

• `prefix[0] = arr[0]`
• `prefix[i] = prefix[i-1] + arr[i]` for `i > 0`

Visualization

Original Array `arr`:

Prefix Sum Array `prefix`:

public class PrefixSumCreator {
    public static int[] createPrefixSum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        int n = arr.length;
        int[] prefix = new int[n];
        prefix[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }
        return prefix;
    }
}
            

Problem 1: Range Sum Query

Problem: Given an array `arr`, handle multiple queries where each query asks for the sum of elements from index `L` to `R` (inclusive).

Optimization with Prefix Sum

Formula: `sum(L, R) = prefix[R] - prefix[L-1]`. This gives an O(1) query time after an initial O(N) setup.

public class RangeSumQuery {
    private int[] prefix;
    public RangeSumQuery(int[] arr) { 
        if (arr == null || arr.length == 0) return;
        prefix = new int[arr.length];
        prefix[0] = arr[0];
        for(int i = 1; i < arr.length; i++) {
            prefix[i] = prefix[i-1] + arr[i];
        }
    }
    public int getSum(int L, int R) {
        if (L == 0) {
            return prefix[R];
        }
        return prefix[R] - prefix[L - 1];
    }
}
            

Problem 2: Subarray with Zero Sum

Problem: Given an array of integers, find if there is a subarray with a sum equal to 0.

Approach with Prefix Sum & HashMap

If a prefix sum `X` appears at two different indices `i` and `j`, the sum of the elements between them must be 0. We use a HashSet to track sums we've already seen.

import java.util.HashSet;
import java.util.Set;
public class ZeroSumSubarray {
    public static boolean hasZeroSumSubarray(int[] arr) {
        Set<Long> sums = new HashSet<>();
        long currentSum = 0;
        sums.add(0L); 
        for (int val : arr) {
            currentSum += val;
            if (sums.contains(currentSum)) {
                return true;
            }
            sums.add(currentSum);
        }
        return false;
    }
}
            

Problem 3: Find Pivot Index

Problem: Given an array of integers `nums`, find the "pivot index." This is the index where the sum of all numbers to the left of the index is equal to the sum of all numbers to the right of the index. If no such index exists, return -1.

Approach using a Running Prefix Sum

Instead of creating two separate prefix and suffix sum arrays, we can do this in one pass. First, calculate the `totalSum` of the entire array. Then, iterate through the array keeping track of a `leftSum`. For each index `i`, the `rightSum` is simply `totalSum - leftSum - nums[i]`. If `leftSum` equals `rightSum`, we've found our pivot.

public class PivotIndexFinder {
    public int pivotIndex(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            int rightSum = totalSum - leftSum - nums[i];
            if (leftSum == rightSum) {
                return i; // Found the pivot index
            }
            leftSum += nums[i];
        }

        return -1; // No pivot index found
    }
}
            

Creating a Suffix Sum Array

Formula:

• `suffix[n-1] = arr[n-1]`
• `suffix[i] = suffix[i+1] + arr[i]` for `i < n-1`

public class SuffixSumCreator {
    public static int[] createSuffixSum(int[] arr) {
        int n = arr.length;
        int[] suffix = new int[n];
        suffix[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + arr[i];
        }
        return suffix;
    }
}
            

Interview Problem: Product of Array Except Self

Problem: Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`. You must solve this in O(N) time and without using the division operator.

Approach using Prefix and Suffix Products

This is a classic problem that beautifully demonstrates the power of combining prefix and suffix computations. For any index `i`, the desired product is `(product of all elements to the left) * (product of all elements to the right)`.

1. Create a `prefixProduct` array (we can use the `answer` array for this to save space). `answer[i]` will store the product of all elements before `i`.
2. Calculate a `suffixProduct` on the fly. Iterate from the end of the array, multiply the current `answer[i]` by the `suffixProduct`, and then update the `suffixProduct`.

public class ProductExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // Step 1: Calculate prefix products and store in the answer array
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // Step 2: Calculate suffix products and multiply with the prefix products
        int suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * suffixProduct;
            suffixProduct *= nums[i];
        }

        return answer;
    }
}
            

Interview Problem: Trapping Rain Water

Problem: Given `n` non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Approach using Prefix and Suffix Maximums

The amount of water trapped above any single bar depends on the height of the walls to its left and right. Specifically, the water level will be the `minimum` of the tallest bar to the left and the tallest bar to the right. The water trapped is this level minus the current bar's height.

1. Create a `leftMax` array (prefix max): `leftMax[i]` stores the maximum height of a bar from index 0 to `i`.
2. Create a `rightMax` array (suffix max): `rightMax[i]` stores the maximum height of a bar from index `i` to `n-1`.
3. Iterate through the map. For each bar `i`, the trapped water is `min(leftMax[i], rightMax[i]) - height[i]`. Sum this up for all bars.

public class TrappingRainWater {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        int n = height.length;
        
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int totalWater = 0;
        for (int i = 0; i < n; i++) {
            int waterLevel = Math.min(leftMax[i], rightMax[i]);
            totalWater += waterLevel - height[i];
        }

        return totalWater;
    }
}